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



+ Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 16 à 30 sur 30

Tout jeu est-il trivial ?

  1. HenriParisien1

    Date d'inscription
    mars 2016
    Messages
    174

    Re : Tout jeu est-il trivial ?

    Ce qui m'a fait réagir c'est cette phrase :
    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
    Tes 16 Mbits c'est la description d'une partie. Il n'y a aucune raison qu'une martingale d'un jeu soit du niveau de complexité d'une seule partie.

    Edit : Ah, je crois que j'ai compris : tu supposes implicitement qu'avec tes règles, il n'y a que 256 positions atteignables ?

    -----

    Dernière modification par HenriParisien1 ; 09/01/2018 à 18h39.
     


    • Publicité



  2. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par HenriParisien1 Voir le message
    Edit : Ah, je crois que j'ai compris : tu supposes implicitement qu'avec tes règles, il n'y a que 256 positions atteignables ?
    Oui, tu soulèves vraiment une erreur de ma part: j'ai oublié que le coup #2 doit tenir compte du coup #1, le coup #3 du coup #2 et du coup #1, etc..

    Donc en fait il faut bien 256^256 octets pour un dictionnaire stipulant une stratégie gagnante et 256^512 octets pour couvrir l'ensemble des parties possibles (en fait 256^128 et 256^256, mais ça dépend si on définit un tour comme deux coup ou un tour comme un coup).
    Dernière modification par Jiav ; 09/01/2018 à 19h24.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  3. Médiat

    Date d'inscription
    août 2006
    Âge
    67
    Messages
    17 098

    Re : Tout jeu est-il trivial ?

    Bonsoir,

    Citation Envoyé par Deedee81 Voir le message


    Précisons : tout jeu à deux personnes déterministe et à information parfaite (c'est le cas du go ou des échecs).
    Voir le théorème de Zermelo et celui de Sprague-Grundy
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse
     

  4. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 131

    Re : Tout jeu est-il trivial ?

    En ce qui concerne les jeux de Nim, la combinatoire de l'algorithme classique minimax est redoutable quand on fait croitre le nombre de tas d'allumettes.
    Toutefois, on a trouvé un algorithme astucieux qui permet d'appliquer en un temps raisonnable une stratégie optimale:
    https://interstices.info/jcms/i_6178...au-pays-de-nim

    La complexité d'un jeu n'est donc pas évidente a priori.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  5. Matmat

    Date d'inscription
    mai 2005
    Messages
    1 047

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par HenriParisien1 Voir le message
    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.
    Ceci est valable pour les humains comme pour les ordinateurs , plus l'adversaire est fort et plus il devient impossible de gagner avec les noirs .
    Le champion du monde a 35% de gain avec les noirs contre les humains .
    PS: alphaZero n'a pas perdu 3 parties avec les noirs , il les a gagné
    Dernière modification par Matmat ; 10/01/2018 à 09h50.
     


    • Publicité



  6. Médiat

    Date d'inscription
    août 2006
    Âge
    67
    Messages
    17 098

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Schrodies-cat Voir le message
    Toutefois, on a trouvé un algorithme astucieux qui permet d'appliquer en un temps raisonnable une stratégie optimale:
    cf. les nimbers.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse
     

  7. HenriParisien1

    Date d'inscription
    mars 2016
    Messages
    174

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Matmat Voir le message
    PS: alphaZero n'a pas perdu 3 parties avec les noirs , il les a gagné
    Exact : j'ai mal lu la légende du tableau des victoires.
     

  8. Juzo

    Date d'inscription
    janvier 2016
    Messages
    410

    Re : Tout jeu est-il trivial ?

    Bonjour,

    Citation Envoyé par Jiav
    Donc en fait il faut bien 256^256 octets pour un dictionnaire stipulant une stratégie gagnante et 256^512 octets pour couvrir l'ensemble des parties possibles (en fait 256^128 et 256^256, mais ça dépend si on définit un tour comme deux coup ou un tour comme un coup).
    Bonjour,

    Désolé je m'intéresse à cette discussion mais je n'ai pas de notions là-dessus, pourriez-vous expliquer comment vous calculez le nombre d'octets du dictionnaire ?
    J'obtiens un autre nombre en comptant un octet pour la racine et 2 octets par noeud de l'arbre d'une stratégie gagnante.
    Merci

    Citation Envoyé par Jiav
    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.

    Un autre moyen serait de montrer que tout jeu peut être décomposé en un nombre limité de sous-jeux triviaux, mais ça paraît peu probable...
    Pour le Go un début de décomposition pourrait être
    - défendre contre une attaque
    - renforcer un territoire de manière préventive
    - réduire l'influence d'un joueur
    - envahir un territoire
    -etc.
    Auxquels s'ajouteraient jongler entrer ces différents sous-jeux, feinter une stratégie...


    Le sujet de la discussion me fait penser au Jeu de la vie, où un nombre limité de règles permet de générer des structures complexes.
    -> https://www.youtube.com/watch?v=S-W0NX97DB0
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais
     

  9. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Juzo Voir le message
    comment vous calculez le nombre d'octets du dictionnaire ?
    Code:
    Si A joue 1/256 au tour 1 alors joue 125/256.
    Si A joue 2/256 au tour 1 alors joue 225/256.
    Si A joue 3/256 au tour 1 alors joue 025/256.
    ...256 octets pour le premier coup
    Si A avait joué 1 au tour 1 et qu'il joue 1/256 au tour 2 alors joue 155/256.
    Si A avait joué 1 au tour 1 et qu'il joue 2/256 au tour 2 alors joue 256/256.
    ...
    Si A avait joué 2 au tour 1 et qu'il joue 1/256 au tour 2 alors joue 132/256.
    Si A avait joué 2 au tour 1 et qu'il joue 2/256 au tour 2 alors joue 216/256.
    ...
    Si A avait joué 3 au tour 1 et qu'il joue 1/256 au tour 2 alors joue 105/256.
    Si A avait joué 3 au tour 1 et qu'il joue 2/256 au tour 2 alors joue 251/256.
    ...
    ...256X256 octets pour le second coup
    ....
    ....
    ....256X256X256 octets pour le troisième coup
    ....
    ....
    ....
    .... 256256 octets pour le coup #256
    L'information sur A est directement lié au numéro de ligne, donc elle peut rester implicite. Reste alors la série d'octet à droite, dont la somme est 2561 + 2562 +... 256256 == 256256 octets.

    Citation Envoyé par Juzo Voir le message
    J'obtiens un autre nombre en comptant un octet pour la racine et 2 octets par noeud de l'arbre d'une stratégie gagnante.
    Pas compris.

    Citation Envoyé par Juzo Voir le message
    Le sujet de la discussion me fait penser au Jeu de la vie, où un nombre limité de règles permet de générer des structures complexes.
    Oui, c'est Turing-complet.
    Dernière modification par Jiav ; 12/01/2018 à 23h24.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  10. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 131

    Re : Tout jeu est-il trivial ?

    On peut considérer la contraposée de la question du fil : existe-t-il un jeu non-trivial ?
    Il s'agit de trouver un jeu dont les règles sont assez simples et dont la résolution est intrinsèquement difficile.
    Par intrinsèquement, j'entends qu'il ne peut exister d'algorithme rapide de résolution.
    Quand on prend des algorithmes naïfs, genre minimax, on peut montrer qu'ils sont peu efficaces, mais le fait qu'on ne connaisse pas d'algorithme efficace ne prouve pas qu'il ne peut en exister.
    La complexité intrinsèque d'un problème est une autre question que la complexité d'un algorithme particulier le résolvant.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  11. Juzo

    Date d'inscription
    janvier 2016
    Messages
    410

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Jiav
    L'information sur A est directement lié au numéro de ligne, donc elle peut rester implicite.
    Ah oui je n'y avais pas pensé ! Merci pour l'explication, je ne comprends pas pourquoi cela est appelé un dictionnaire je vais me renseigner.

    Citation Envoyé par Jiav
    J'obtiens un autre nombre en comptant un octet pour la racine et 2 octets par noeud de l'arbre d'une stratégie gagnante.
    "
    Pas compris.
    C'est la même chose dans le cas ou l'adversaire joue second, on décrit le 1er coup à jouer (la racine de l'arbre stratégique) puis à chaque noeud du niveau suivant, le coup à jouer en fonction de la réponse de l'adversaire.
    Quand l'adversaire joue second, on est de l'ordre de 256^255, si on ne compte qu'un octet par noeud.
    Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne verront jamais
     

  12. Deedee81

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

    Re : Tout jeu est-il trivial ?

    Salut,

    Citation Envoyé par Schrodies-cat Voir le message
    La complexité intrinsèque d'un problème est une autre question que la complexité d'un algorithme particulier le résolvant.
    Attention, en théorie de la complexité (ça ne remet donc pas nécessairement en cause ce qui a été dit ci-dessus, c'est juste une remarque d'ordre générale), la complexité d'un problème est définie comme la complexité du meilleur algorithme exact (ça se formaliste rigoureusement, par exemple, si ça y est toujours, sur le site de l'institut Clay ils formalisent ça avec des machines de Turing). Donc si on dit qu'un problème est de complexité exponentielle (à nouveau, tous les jeux n'ont pas ce statut, ça ne remet pas en cause les remarques ci-dessus) alors le meilleur algorithme aura une complexité exponentielle.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  13. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 131

    Re : Tout jeu est-il trivial ?

    Il faut noter qu'une complexité exponentielle, polynomiale ou autre ne désigne pas la complexité d'une question particulière mais d'un ensemble de question.
    Il s'agit d'un résultat asymptotique en fonction de la taille de la question (le nombre de bits qu'il faut pour la poser).

    On peut parler de la complexité du sudoku n2*n2, c'est un problème NP-complet, ce qui veut dire que si vous prouvez qu'il y a un algorithme polynomial en n pour le résoudre, ou le contraire, vous gagnerez 1 M$.
    La conjecture étant qu'il n'y en a pas et que c'est un problème difficile.
    Cela ne préjuge en rien de la difficulté du sudoku classique 9*9.

    D'autres jeux se prêtent à se genre de généralisation, comme le reversi, le go : le go classique se joue sur un terrain 19*19 mais il pourrait se jouer sur un terrain n*n.
    J'avais lu que la complexité du jeu d'échec est exponentielle. J'ai un doute: il n'y a pas de moyen naturel de généraliser le jeux d'échecs à un terrain de taille arbitraire.

    19*19, cela commence déjà à faire beaucoup. Je crois que si on montre que la complexité asymptotique du jeu de go est forte, on pourrait en inférer raisonnablement que le jeu classique est difficile.
    Dernière modification par Schrodies-cat ; 15/01/2018 à 17h49.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  14. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : Tout jeu est-il trivial ?

    Citation Envoyé par Juzo Voir le message
    Ah oui je n'y avais pas pensé ! Merci pour l'explication, je ne comprends pas pourquoi cela est appelé un dictionnaire je vais me renseigner.
    Perso ça vient du python mais les racines sont probablement plus profondes, si tu trouves je serais curieux de la réponse.

    Citation Envoyé par Juzo Voir le message
    C'est la même chose dans le cas ou l'adversaire joue second, on décrit le 1er coup à jouer (la racine de l'arbre stratégique) puis à chaque noeud du niveau suivant, le coup à jouer en fonction de la réponse de l'adversaire.
    Quand l'adversaire joue second, on est de l'ordre de 256^255, si on ne compte qu'un octet par noeud.
    Ok

    Citation Envoyé par Schrodies-cat Voir le message
    Il faut noter qu'une complexité exponentielle, polynomiale ou autre ne désigne pas la complexité d'une question particulière mais d'un ensemble de question.
    Il s'agit d'un résultat asymptotique en fonction de la taille de la question (le nombre de bits qu'il faut pour la poser).
    Yep, c'est pour cela que j'ai voulu proposer une variante où la taille du jeu est fixe (fixée par le nombre de tour) et le problème est une famille de rêgles pouvant s'écrire avec n rêgles plutôt qu'une famille de jeu sur un tableau de taille n. Cela dit c'est possiblement boiteux quand même, parce que le nombre de tour max impose aussi un nombre de rêgles possibles fini.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  15. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 131

    Re : Tout jeu est-il trivial ?

    Un petit exercice est d'estimer le nombre de configurations possibles d'une planche de go:
    Il faut préciser si c'est aux noirs ou aux blancs de jouer et ...

    On peut obtenir une majoration en considérant qu'a une intersection il y a soit une pierre blanche, soit une pierre noire, soit pas de pierre, ce qui nous donne un nombre de configurations inférieur ou égal à 2*319*19
    Toutefois ces configurations ne sont pas toutes possibles compte tenu des règles du jeu.

    On peut aisément le minorer par 2* 312*19
    Saurez vous retrouver cette minoration ou en trouver une meilleure ?

    Cela montre en tous cas que la "force brute" ne marche pas pour résoudre parfaitement ce jeux.
    Il n'est pire sot que qui ne veut pas comprendre .
     


    • 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