Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 15 sur 30

Tout jeu est-il trivial ?

  1. Dattier

    Date d'inscription
    août 2017
    Localisation
    EnigmeLand
    Messages
    283

    Tout jeu est-il trivial ?

    Salut,

    Quand on voit l'aisance avec laquelle Alpha-Zero, avec une puissance de calcul moindre que son adversaire Stockfish, a gagné aux échecs, on peut se poser la question suivante :

    tout jeu à 2 joueurs est-il triviale ?

    C'est à dire tout jeu posséde-t-il une interprétation qui rende le jeu équivalent à un jeu trivial, c'est à dire dont les positions perdantes sont calculables en un temps polynomiale ?

    Y-a-t-il un argument décisive (que je ne connais pas) et qui permette de répondre par la négative à cette question ?

    Cordialement.

    -----

    Raisonnement empirique : A est EC si avec 10 exemples et pas de contre-exemples connus
     


    • Publicité



  2. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    28 921

    Re : Tout jeu est-il trivial ?

    Salut,

    Citation Envoyé par Dattier Voir le message
    Quand on voit l'aisance avec laquelle Alpha-Zero, avec une puissance de calcul moindre que son adversaire Stockfish, a gagné aux échecs, on peut se poser la question suivante :
    tout jeu à 2 joueurs est-il triviale ?
    Précisons : tout jeu à deux personnes déterministe et à information parfaite (c'est le cas du go ou des échecs).

    Ils sont triviaux au sens de la logique formelle.

    Mais toi tu en donnes une autre définition :

    Citation Envoyé par Dattier Voir le message
    dont les positions perdantes sont calculables en un temps polynomiale ?
    Il est fort plausible que non. Je donnerais deux arguments pour ça :
    - l'arbre des coups est exponentiel
    - certaines choses simples comme : soit une configuration de démineur donnée avec une partie des cases déjà sélectionnées. Existe-t-il une solution ou est-ce un cas impossible ? Et bien les algorithmes pour une telle question sont démontrés NP complet !!! (démonstration de Ian Steward, publié dans Scientific Amrican. Voir : http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
    Et on peut facilement imaginer un jeu utilisant ça.

    Le deuxième argument est blindé et montre que la réponse à ta question est NON.

    Mais il se peut que pour certains jeux il soit possible d'avoir des algorithmes infaillibles très rapides (go ? Echecs ?)
    En tout cas il y a une solution possible : stocker l'arbre de toutes les positions possibles et l'exploiter. Alors le programme devient rapide et infaillible. Cela a été fait au moins pour le morpion et le jeu de dames anglaises.
    (mais ce n'est pas possible pour tous les jeux comme montré plus haut)

    Note qu'il y a un défaut dans ta question (j'ai essayé de l'éviter dans ma réponse en disant "très rapide" ) : quand tu dis polynomial, c'est en fonction d'un paramètre d'ordre. C'est quoi le paramètre d'ordre dans ta question ????
    (pour démineur c'est la taille du tableau, au morpion aussi. Mais au go ou aux échecs, cette taille est invariable. Que signifie alors "polynomial" ????)
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  3. Dattier

    Date d'inscription
    août 2017
    Localisation
    EnigmeLand
    Messages
    283

    Re : Tout jeu est-il trivial ?

    Je vais reformuler ma question de manière plus précise :

    Existe-t-il une interprétation du jeu d'échec (qui pourrait s'apprendre en 1 jour) et qui si elle serait connue d'un novice, le rendrait impossible à battre ?

    Si une telle chose n'existe pas, j'aimerais en savoir la justification.
    Raisonnement empirique : A est EC si avec 10 exemples et pas de contre-exemples connus
     

  4. HenriParisien1

    Date d'inscription
    mars 2016
    Messages
    174

    Re : Tout jeu est-il trivial ?

    Et bien, disons que depuis le temps que l'on y travaille, depuis que le temps que nous avons des ordinateurs qui nous battent à ce jeu, on n'en a pas trouvé.
    C'est déjà une bonne justification, non ?

    Il y a une vingtaine d'année, sur les échecs, le consensus des joueurs étaient qu'en cas de joueur "parfait" (cad capable d'explorer l'intégralité de l'arbre du jeu), les deux joueurs arrivaient au nul.
    Les parties ordinateurs / ordinateurs ont cependant tendance à être gagner par les blancs. Et AlphaZéro versus Stockfish n'y fait pas exception. Avec les Blancs, AlphaZéro gagne 1 fois sur 2 et fait nulle les autres fois, avec les noirs, il en perds 3 et fait nulle le reste du temps.
     

  5. Dattier

    Date d'inscription
    août 2017
    Localisation
    EnigmeLand
    Messages
    283

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par HenriParisien1 Voir le message
    Et bien, disons que depuis le temps que l'on y travaille, depuis que le temps que nous avons des ordinateurs qui nous battent à ce jeu, on n'en a pas trouvé.
    C'est déjà une bonne justification, non ?
    Non, sinon ce que l'on serait incapable de faire aujourd'hui, on ne serait incapable de le faire demain, or il existe plein de chose que l'on savait pas faire hier, voir que l'on pensait impossible (comme voler) et que l'on peut faire aujourd'hui.
    Raisonnement empirique : A est EC si avec 10 exemples et pas de contre-exemples connus
     


    • Publicité



  6. HenriParisien1

    Date d'inscription
    mars 2016
    Messages
    174

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Dattier Voir le message
    Non, sinon ce que l'on serait incapable de faire aujourd'hui, on ne serait incapable de le faire demain, or il existe plein de chose que l'on savait pas faire hier, voir que l'on pensait impossible (comme voler) et que l'on peut faire aujourd'hui.
    Oui, enfin... Tu veux une martingale qui puisse s'apprendre en moins d'une journée et qui te permettrait de gagner dans tout les cas.
    On suppose que tu es humain, cette martingale pour que tu puisses la mettre en oeuvre, il ne faut pas qu'elle est plus d'une centaine de règles.

    En pratique, et pour rester sur les échecs, cela voudrait dire que l'on pourrait réduire les 10^43 position (10^50 pour certains auteurs) possibles à une centaine de schéma génériques. Si c'était possible, cela aurait déjà été fait. et AlphaGo n'aurait pas concédé 25 nul
     

  7. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    28 921

    Re : Tout jeu est-il trivial ?

    Salut,

    Il n'existe pas de "martingales" humainement utilisables pour la plupart des jeux. Mais informatiquement oui (j'ai cité le cas du morpion et des dames anglaises (*)).
    Mais il en existe pour des jeux sympas et pas si élémentaires comme le jeu de Nim (avec une méthode amusante consistant à additionner des nombres binaires comme s'ils étaient décimaux. Très curieux).

    (*) ce cas est assez intéressant. Un programme dans les années septante avait été conçu avec une méthode d'apprentissage assez simple : l'algorithme explore disons 5 coups à l'avance avec une heuristique d'évaluation. Et il stocke la position courante avec la valeur obtenue. Si au cours de son exploration il retombe sur une position connue, il réutilise cette valeur, ce qui donne indirectement une analyse à 10 coups d'avance (du moins si toutes les positions "feuilles" sont déjà stockées).
    Ils ont fait jouer le programme contre lui-même et contre de forts joueurs. Au bout d'un certain temps, il avait atteint le niveau champion du monde et là : il avait stocké presque toutes les positions possibles du jeu !!!!!
    Ce genre de chose donne une idée de la difficulté à pondre de bonnes martingales et autres heuristiques d'évaluation dans des jeux comme les dames, les échecs, l'othello-réversi, le go, le shogi ou bien d'autres.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  8. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    28 921

    Re : Tout jeu est-il trivial ?

    Je viens de trouver ça : http://www.les-mathematiques.net/pho...,124319,124328
    (en cherchant pour Nim, je vous laisse chercher, c'est facile)
    un cas assez extraordinaire de problème d'échec (pas évident) qui peut se résoudre comme pour le jeu de Marienbad.

    J'adore la composition aux échecs et il y a pas mal de temps j'avais pondu pas mal de problèmes, surtout des analyses rétrogrades. Je suis un grand admirateur de Sam Loyd.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  9. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Dattier Voir le message
    tout jeu posséde-t-il une interprétation qui rende le jeu équivalent à un jeu trivial
    C'est une question intéressante. Peut-être par principe du pigonnier?
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  10. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    28 921

    Re : Tout jeu est-il trivial ?

    Salut,

    Citation Envoyé par Jiav Voir le message
    C'est une question intéressante. Peut-être par principe du pigonnier?
    Je ne comprend pas comment tu appliques ce principe au jeu de manière à le rendre trivial ?
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  11. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Non, l'idée serait de démontrer que trivialiser un jeu quelconque est improbable en montrant que l'ensemble [jeu quelconque] est beaucoup plus grand que l'ensemble [jeu trivial] (ou l'ensemble [jeu trivialisable]). Mais ce n'est pas si trivial à montrer, en tout cas pour moi.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  12. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    28 921

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Jiav Voir le message
    Mais ce n'est pas si trivial à montrer, en tout cas pour moi.
    Oulà, d'accord, j'ai compris et en effet, c'est pas évident (déjà faudrait définir rigoureusement ce qu'on entend par jeu trivial ou trivialisable et même jeux pour savoir si on prend uniquement ceux déterministes à information parfaite... ou pas).
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  13. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Tentative pour bien définir le problème posé par Datier:

    Définissions un jeu à deux joueurs quelconque comme un jeu comportant 256 tours et à chaque tour un choix parmi 256 possibilités. Un jeu spécifique est alors l'ensemble des rêgles spécifiants à chaque tour quels coups sont autorisés parmi les 256 potentiels, et quelles transitions sont gagnantes. Avec cette définition il est clair que pour chaque jeu spécifique il existe une stratégie optimale qui peut être stipulée par un dictionnaire de longeur 256*256 octets, soit environ 16 Mbits.

    Évidement cette stratégie optimale n'est en soi pas nécessairement facile à trouver. La question de Dattier, si j'ai bien compris: est-il (im)possible ou (im)probable qu'il existe un algorithme de taille réduite (disons de taille similaire à la taille nécessaire à la description des rêgles) qui génère ce dictionnaire?
    Dernière modification par Jiav ; 09/01/2018 à 16h47.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  14. HenriParisien1

    Date d'inscription
    mars 2016
    Messages
    174

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Jiav Voir le message
    Tentative pour bien définir le problème posé par Datier:

    Définissions un jeu à deux joueurs quelconque comme un jeu comportant 256 tours et à chaque tour un choix parmi 256 possibilités. Un jeu spécifique est alors l'ensemble des rêgles spécifiants à chaque tour quels coups sont autorisés parmi les 256 potentiels, et quelles transitions sont gagnantes. Avec cette définition il est clair que pour chaque jeu spécifique il existe une stratégie optimale qui peut être stipulée par un dictionnaire de longeur 256*256 octets, soit environ 16 Mbits.

    Évidement cette stratégie optimale n'est en soi pas nécessairement facile à trouver. La question de Dattier, si j'ai bien compris: est-il (im)possible ou (im)probable qu'il existe un algorithme de taille réduite (disons de taille similaire à la taille nécessaire à la description des rêgles) qui génère ce dictionnaire?
    On n'est plutôt sur une problématique de 256^256 qui est de l'ordre de 10^1200 ; non ?
    Les 16 Mbits, c'est la taille d'une partie. Le problème, c'est qu'on suppose un jeu à deux joueurs. Et s'il existe une partie optimale pour un des deux joueurs, l'intérêt du deuxième joueur, c'est de sortir le plus vite possible de cette partie optimale.
    Pour rester aux échecs, il y a le coup du berger qui permet au blanc de gagner en 4 coups. Mais cela suppose la collaboration des noirs.

    Pour un jeu "trivial", comme les jeux de Nim, la stratégie optimale est d'extraire une information à partir de la position actuelle et de déterminer le meilleur coups à jouer. Le jeu de Nim est cool dans le sens ou l'information obtenu à partir de la position est binaire. Donc il suffit de deux règles :
    - si la valeur de la position est a 1, alors je passe dans une configuration à 0 ;
    - si la valeur de la position est a 0, alors je passe dans une configuration à 0 ; (Si le 0 est la configuration qui me permet de gagner).

    Mais si l'information qui permet le choix de la stratégie à partir de la position tient sur n bits, la règle aura une complexité minimale de 2^n.

    Si on considère que ce qui est humainement gérable c'est une complexité de l'ordre de 256 règles, cela nous fait ramener la position d'un jeu à un peu plus 16 configurations possibles.

    Pour rester aux échecs, est-il possible de réduire de 10^43 positions possibles à 16 configurations génériques ? Et surtout, comment allons nous concilier ces 16 configurations génériques avec la dizaine de fin de partie que tout bon joueurs apprends (R vs R + 1 ou 2 pièces adverses).

    Tiens d'ailleurs Didier, il y a une configuration aux échecs qui se ramène naturellement à un jeu de Nim : P + R vs R quand les deux R sont en opposition
    Dernière modification par HenriParisien1 ; 09/01/2018 à 17h46.
     

  15. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par HenriParisien1 Voir le message
    On n'est plutôt sur une problématique de 256^256 qui est de l'ordre de 10^1200 ; non ?
    Non, ça c'est la taille pour trouver une stratégie optimale (par force brute). La description de la stratégie est elle-même beaucoup plus courte (mais quand même plus grande, du moins quand elle est sous forme de dictionnaire, que la description des rêgles).
    Dernière modification par Jiav ; 09/01/2018 à 18h01.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     


    • Publicité







Sur le même thème :


    301 Moved Permanently

    301 Moved Permanently


    nginx/1.2.1



 

Discussions similaires

  1. Solution non trivial
    Par farfaoui92 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 27/05/2017, 21h35
  2. Contraintes Nominales (cas non trivial)
    Par mAx6010 dans le forum Physique
    Réponses: 0
    Dernier message: 23/09/2013, 18h09
  3. est ce trivial? je suis bête?
    Par spearhawk dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 02/12/2012, 10h11
  4. problème trivial avec redresseur à diode.
    Par noir_desir dans le forum Électronique
    Réponses: 2
    Dernier message: 05/03/2008, 19h54
  5. [Géom Diff] Fibré trivial
    Par Sephi dans le forum Mathématiques du supérieur
    Réponses: 16
    Dernier message: 03/04/2005, 16h31