Tout jeu est-il trivial ?

[invite452d5a24]

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.
-----

[Deedee81]

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 ?

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 :

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" ????)

[invite452d5a24]

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.

[inviteef2ff547]

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.

[A voir en vidéo sur Futura]

[invite452d5a24]

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.

[inviteef2ff547]

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

[Deedee81]

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.

[Deedee81]

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.

[invite6c250b59]

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?

[Deedee81]

Salut,

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 ?

[invite6c250b59]

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.

[Deedee81]

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).

[invite6c250b59]

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?

[inviteef2ff547]

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

[invite6c250b59]

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).

[inviteef2ff547]

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 ?

[invite6c250b59]

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).

[Médiat]

Bonsoir,

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

[invite82078308]

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.

[Matmat]

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é

[Médiat]

Toutefois, on a trouvé un algorithme astucieux qui permet d'appliquer en un temps raisonnable une stratégie optimale:

cf. les nimbers.

[inviteef2ff547]

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.

[Juzo]

Bonjour,

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

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

[invite6c250b59]

comment vous calculez le nombre d'octets du dictionnaire ?

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 256¹ + 256² +... 256²⁵⁶ == 256²⁵⁶ octets.

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.

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.

[invite82078308]

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.

[Juzo]

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.

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.

[Deedee81]

Salut,

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.

[invite82078308]

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 n²*n², 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.

[invite6c250b59]

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.

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

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.

[invite82078308]

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*3^19*19
Toutefois ces configurations ne sont pas toutes possibles compte tenu des règles du jeu.

On peut aisément le minorer par 2* 3^12*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.