Jeu résolu

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Un jeu résolu est un jeu dont le résultat (gagner, perdre ou match nul) peut être correctement prédit à partir de n'importe quelle position, en supposant que les deux joueurs jouent à la perfection.

Vue d'ensemble[modifier | modifier le code]

Un jeu à deux (en) peut avoir plusieurs niveaux de « résolution »[1],[2] :

Ultra-faible
Prouve si le premier joueur va gagner, perdre ou faire match nul à partir de la position initiale, en supposant le jeu parfait des deux côtés. Cela peut être une preuve non-constructive (avec éventuellement une démonstration par vol de stratégie (en)) qui n'a pas besoin de réellement déterminer les mouvements du jeu parfait.
Faible
Fournit un algorithme qui garantit une victoire pour l'un des joueurs, ou un match nul, contre tous les mouvements possibles de l'adversaire, dès le début du jeu. C'est-à-dire que cette résolution produit au moins un complet jeu idéal (tous les déplacements du début à la fin) avec la preuve que chaque coup est optimal pour le joueur. Cela ne signifie pas nécessairement qu'un programme d'ordinateur utilisant cette résolution jouera de manière optimale contre un adversaire imparfait. Par exemple, le programme de jeu de dames Chinook ne transformera jamais une position de nul en une position perdante (puisque la résolution faible au jeu de dames prouve que c'est un match nul), mais il peut passer d'une position gagnante à une position de match nul parce que Chinook ne s'attend pas à ce que l'adversaire joue un coup qui ne va pas gagner, mais pourrait peut-être perdre, et il n'analyse pas complètement ces mouvements.
Forte
Fournit un algorithme qui peut produire les coups idéaux à partir de n'importe quelle position, même si des erreurs ont déjà été faites d'un côté ou de l'autre.

En dépit de leur nom, de nombreux théoriciens des jeux estiment que les preuves « ultra-faibles » sont les plus profondes, les plus intéressantes et utiles. Les preuves « ultra-faibles » nécessitent un raisonnement érudit sur les propriétés abstraites du jeu, et pour montrer comment ces propriétés mènent à des résultats certains si le jeu parfait est réalisé.[réf. nécessaire]

Par contre, les preuves « fortes » procèdent souvent par la force brute — à l'aide d'un ordinateur pour rechercher de manière exhaustive l'arborescence d'un jeu (en) pour comprendre ce qui se passerait si le jeu parfait était réalisé. La preuve résultant de cette recherche donne une stratégie optimale pour chaque position sur le plateau. Cependant, ces preuves ne sont pas utiles dans la compréhension plus profonde des raisons pour lesquelles certains jeux sont résolubles comme match nul, alors que d'autres jeux, en apparence très similaires, sont résolubles vers une victoire.

Étant données les règles de jeu à deux avec un nombre fini de positions, on peut toujours trivialement construire un algorithme minimax qui parcourrait de manière exhaustive l'arborescence du jeu. Cependant, du fait que pour beaucoup de jeux non-triviaux un tel algorithme aurait besoin d'une quantité trop importante de temps pour générer un mouvement dans une position donnée, un jeu n'est pas considéré comme résolu faiblement ou fortement, à moins que l'algorithme puisse être mis en œuvre avec le matériel existant dans un délai raisonnable. De nombreux algorithmes s'appuient sur un vaste base de données pré-générées, et, en effet, rien de plus.

Comme exemple de résolution solide, le jeu de tic-tac-toe est résoluble comme match nul pour les deux joueurs avec un jeu parfait (un résultat qui est même déterminable à la main par les élèves). Des jeux comme les jeux de Nim admettent aussi une analyse rigoureuse à l'aide de la théorie des jeux combinatoires.

Qu'un jeu soit résolu ne signifie pas nécessairement qu'il ne reste pas intéressant à jouer pour les humains. Même un jeu fortement résolu peut toujours être intéressant si sa solution est trop complexe pour être mémorisée ; à l'inverse, un jeu faiblement résolu peut perdre de son attrait si la réussite de la stratégie est assez simple à retenir (par exemple, Le Maharajah et les Sepoys). Une résolution ultra-faible (par exemple Chomp ou Hex sur un plateau suffisamment grand) n'affecte généralement pas la jouabilité.

En outre, même si le jeu n'est pas résolu, il est possible que l'algorithme donne une bonne approximation de la solution: par exemple, un article dans Science daté de janvier 2015 annonce que leur version poker Heads up (en) limite les garanties du robot Cepheus de Texas hold 'em poker que la vie d'un joueur humain n'est pas suffisante pour établir statistiquement de façon significative que sa stratégie n'est pas une solution exacte[3],[4],[5].

Le jeu parfait[modifier | modifier le code]

En théorie des jeux, le jeu parfait est le comportement ou la stratégie d'un joueur qui conduit au meilleur résultat possible pour le joueur, indépendamment de la réponse de l'adversaire. Sur la base des règles d'un jeu, chaque position finale peut être évaluée (comme une victoire, une perte ou un nul). En chaînage arrière, on peut évaluer de manière récursive une position  non finale comme étant identique à celle qui est à un coup de la meilleure valeur pour le joueur dont c'est le tour. Ainsi, une transition entre les positions ne peut jamais aboutir à une meilleure évaluation pour le joueur dont c'est le tour, et un parfait déplacement dans une position serait une transition entre des positions qui sont évaluées de façon égale. Comme exemple, un joueur parfait dans une position de match nul arrivera toujours à un nul ou une victoire, jamais une défaite. S'il y a plusieurs options offrant le même résultat, le jeu parfait est parfois considéré comme étant la méthode la plus rapide conduisant à un bon résultat, ou la méthode la plus lente conduisant à un mauvais résultat.

Le jeu parfait peut être généralisé à des jeux à information non-parfaite (en), comme la stratégie à même de garantir le résultat attendu minimal le plus élevé indépendamment de la stratégie de l'adversaire. Par exemple, la stratégie parfaite pour Pierre-feuille-ciseaux serait de choisir au hasard chacune des options avec une probabilité égale (1/3). L'inconvénient de cet exemple est que cette stratégie n'exploitera jamais des stratégies non-optimales de l'adversaire, de sorte que les résultats attendus de cette stratégie par rapport à toute stratégie sera toujours égale au résultat attendu minimal.

Bien que la stratégie optimale d'un jeu ne puisse pas (encore) être connue, un ordinateur jouant peut quand même bénéficier de solutions du jeu à partir de certains positions finales (via des tables de finale), ce qui va lui permettre de jouer parfaitement à partir d'un certain point dans le jeu. Les programmes d'échecs sont bien connus pour ce faire.

Jeux résolus[modifier | modifier le code]

Awalé (un jeu de la famille du Mancala )
La variante Oware permettant une fin de jeu "grand chelem" a été fortement résolue par Henri Bal (en) et Jean Romein à l'Université libre d'Amsterdam aux Pays-Bas (2002). Chaque joueur peut forcer le jeu vers un match nul. Il est à noter que le maître espagnol d'Oware Viktor Bautista i Roca a annoncé sur son ancienne page d'accueil manqala.org que le "Awari Oracle" (entièrement fondé sur les recherches de Bal et Romein) avait plusieurs défauts dans la phase finale et qu'on peut donc douter que la solution de Bal et Romein soit valide. Cependant, les deux sites (manqala.org et l'Oracle) ont été retirés d'internet et aucune nouvelle recherche ne semble possible. Cela révèle un problème majeur : la plupart des recherches effectuées dans le domaine de la résolution des jeux n'est pas entièrement revue par les pairs. Des petites erreurs dans la programmation, qui néanmoins peuvent donner des résultats très différents, passent généralement inaperçues.
Dames anglaises
Cette variante 8×8 du jeu de dames a été faiblement résolue le 29 avril 2007 par l'équipe de Jonathan Schaeffer, connu pour Chinook, le « Champion du Monde de dames Homme-Machine ». À partir de la position standard de départ, les deux joueurs peuvent garantir un nul avec le jeu parfait[6]. Le jeu de Dames est le plus grand jeu qui ait été résolu à ce jour, avec un espace de recherche de 5×1020[7]. Le nombre de calculs à réaliser était de 1014, qui ont été réalisés sur une période de 18 ans. Le processus a impliqué de 200 ordinateurs de bureau à son apogée, jusqu'à environ 50[8].
Dobutsu shogi
Fortement résolu. Le jeu aboutit à une victoire du joueur ne commençant pas[9].
Fanorona
Faiblement résolu par Maarten Schadd. Le jeu aboutit à un nul.
Gomoku libre
Résolu par Victor Allis (en) (1993). Le premier joueur peut forcer une victoire sans les règles d'ouverture.
Ghost (en)
Résolu par Alan Frank à l'aide du Dictionnaire officiel du jeu de Scrabble (en) en 1987.
Hex
  • Une démonstration par vol de stratégie (comme utilisée par John Nash) montre que tous les plateaux de taille carrée peuvent ne pas être perdus par le premier joueur. Combiné avec une preuve de l'impossibilité d'un nul, cela montre que le jeu est ultra-faiblement résolu comme une victoire du premier joueur.
  • Fortement résolu par plusieurs ordinateurs pour des plateaux de taille allant jusqu'à 6×6.
  • Jing Yang a démontré une stratégie gagnante (résolution faible) pour les plateaux de tailles 7×7, 8×8 et 9×9.
  • Une stratégie gagnante pour Hex avec la Règle du gâteau est connue pour le plateau de taille 7×7.
  • Une résolution forte de hex sur un plateau de taille N×N est peu probable vu que le problème a été montré comme étant PSPACE-complet.
  • Si le jeu de Hex est joué sur un plateau de taille N × N+1, alors le joueur qui a la plus courte distance pour se connecter peut toujours gagner par une simple stratégie d'appariement, même avec le désavantage de jouer en second.
  • Une résolution faible est connue pour tous les coups de l'ouverture sur un plateau 8×8[10].
Hexapawn
La variante 3×3 est résolue comme une victoire pour le noir, plusieurs autres variantes plus grandes sont également résolues[11].
Le jeu des baguettes (en)
Le second joueur peut toujours forcer une victoire[12].
Kalah
La plupart des variantes ont été résolues par Geoffrey Irving, Jeroen Donkers et Jos Uiterwijk (2000) à l'exception de Kalah (6/6). La variante (6/6) a été résolue par Anders Carstensen (2011). Un avantage fort pour le premier joueur a été prouvé dans la plupart des cas[13],[14]. Mark Rawlings a quantifié l'ampleur de la première victoire de joueur dans la variante (6/6) (2015). Après la création d'une  bases de données de finales d'une taille de 39 giga-octets, et des recherches totalisant 106 jours de temps de processeur et de plus de 55 billions de nœuds, il a été prouvé que, avec le jeu parfait, le premier joueur gagne par 2. Il est à noter que tous ces résultats font référence à la variante "Empty-pit Capture" et sont donc d'un intérêt très limité pour le jeu standard. Une analyse du jeu avec la règle standard a été établie pour Kalah (6,4), qui est une victoire par 8 pour le premier joueur, et Kalah (6,5), qui est une victoire par 10 pour le premier joueur. L'analyse de Kalah (6,6) avec les règles standard est en cours, cependant, il a été prouvé que c'est une victoire par au moins 4 pour le premier joueur.
Jeu de L
Facilement résoluble. Chaque joueur peut forcer le jeu dans un nul.
Qui perd gagne
Faiblement résolu comme une victoire pour les blancs en commençant par 1.e3[15].
Maharadjah et cipayes
Ce jeu asymétrique garantit une victoire pour le joueur cipayes s'il joue correctement.
Jeux de Nim
Fortement résolu.
Jeu du moulin
Résolu par Ralph Gasser (1993). Chaque joueur peut forcer le jeu dans un nul[16].
Congklak
Faiblement résolu par des humains, mais prouvée par les ordinateurs. Dakon, toutefois, n'est pas identique à Congklak, le jeu qui avait effectivement été observé par de Voogt.
Pangki
Fortement résolu par Jason Doucette (2001)[17]. Le jeu est un nul. Il y a seulement deux premiers déplacements si vous ne tenez pas compte des positions symétriques. L'une force le nul, et l'autre donne à l'adversaire une victoire forcée en 15.
Pentago
Fortement résolu[18]. Le premier joueur gagne.
Pentominos
Faiblement résolu par Hilarie K. Orman[19]. C'est une victoire pour le premier joueur.
Puissance 4
Résolu d'abord par James D. Allen (1er octobre 1988), et indépendamment par Victor Allis (en) (16 octobre 1988)[20]. Le premier joueur peut forcer une victoire. Fortement résolu avec la base de données de John Tromp[21] (4 février 1995). Faiblement résolu pour tous les plateaux de taille où la somme de la largeur et de la hauteur est d'au plus quinze (15) (et même de taille 8x8 à la fin de 2015)[20] (18 février 2006).
Quarto
Résolu par Luc Goossens (1998). Deux joueurs parfaits font toujours match nul.
Tic-tac-toe 3D (en) (ou Qubic)
Faiblement résolu par Oren Patashnik (1980) et Victor Allis. Le premier joueur gagne.
Jeu de type Renju sans les règles d'ouverture
Prétendu comme étant résolu par János Wagner et István Virág (2001). Une victoire du premier joueur.
Sim
Faiblement résolu : victoire pour le second joueur.
Teeko
Résolu par Guy Steele (1998). Selon la variante, le premier joueur soit gagne soit obtient nul[22].
Three Men's Morris (en)
Trivialement résoluble. Chaque joueur peut forcer le jeu dans un nul.
Les Trois Mousquetaires
Fortement résolu par Johannes Laire en 2009. C'est une victoire pour les pièces bleues (les hommes du Cardinal de Richelieu, ou l'ennemi)[23].
Tic-tac-toe
Trivialement résoluble. Chaque joueur peut forcer le jeu dans un nul.
Bagh Chal
Faiblement résolu par Yew Jin Lim (2007). Le jeu est un nul[24].

Jeux partiellement résolus[modifier | modifier le code]

Échecs
La résolution complète du jeu d'échecs reste inatteignable, et il est conjecturé que la complexité du jeu peut empêcher qu'il soit jamais résolu. Par analyse rétrograde par ordinateur, des tables de finale (des solutions fortes) ont été trouvées pour toutes les finales comportant de trois à sept pièces, et certains à huit pièces, en comptant les deux rois parmi les pièces.
Certaines variantes du jeu d'échecs sur un plus petit plateau avec un nombre réduit de pièces (Mini-échecs) ont été résolues. Certaines autres variantes ont également été résolues ; par exemple une résolution faible de Maharadjah et cipayes est une série facilement mémorable de mouvements qui assure la victoire du joueur cipayes.
Go
Le plateau 5×5 est faiblement résolu pour tous les coups d'ouverture[25]. Les humains jouent d'habitude sur un  plateau 19×19, qui est d'un ordre de grandeur de complexité plus de 145 fois supérieur au plateau 7×7[26].
Jeu de dames
Toutes les positions de fin de partie comportant de deux à sept pièces ont été résolues, ainsi que des combinaisons en 4×4 et 5×3 pièces dont chaque côté avait une dame ou moins, les positions avec cinq pions et quatre pions, les positions avec cinq pions contre trois pions et une dame, ainsi que les positions avec quatre pions et un roi contre quatre pions. Les finales ont été résolues en 2007 par l'américain Ed Gilbert. Une analyse par ordinateur a montré qu'il était très probable de finir en nul si les deux joueurs ont joué à la perfection[27].
Morpion
Il est trivial de montrer que le deuxième joueur ne peut pas gagner ; voir la démonstration par vol de stratégie. Presque tous les cas ont été résolus faiblement pour k ≤ 4. Certains résultats sont connus pour k = 5. Les jeux sont nuls pour k ≥ 8.
Reversi (Othello)
Faiblement résolu sur un plateau 4×4 et 6×6 pour une victoire du second joueur, en juillet 1993 par Joel Feinstein[28]. Sur un plateau 8×8 (le standard), il n'est mathématiquement pas résolu, bien que l'analyse par ordinateur montre un probable nul. Il n'existe aucune estimation que les chances de gain du premier joueur (Noir) augmentent sur des plateau 10×10 et plus.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Solved game » (voir la liste des auteurs).
  1. V. Allis, Searching for Solutions in Games and Artificial Intelligence.
  2. H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games solved: Now and in the future, Artificial Intelligence 134 (2002) 277–311.
  3. « Heads-up limit hold’em poker is solved », Science, vol. 347,‎ , p. 145–9 (PMID 25574016, DOI 10.1126/science.1259433)
  4. Philip Ball, « Game Theorists Crack Poker », sur Scientific American, (DOI 10.1038/nature.2015.16683, consulté le 13 janvier 2015)
  5. (en-US) Robert Lee Hotz, « Computer Conquers Texas Hold 'Em, Researchers Say », Wall Street Journal,‎ (lire en ligne)
  6. Jonathan Schaeffer, « Checkers Is Solved », Science, (consulté le 20 juillet 2007)
  7. « Project - Chinook - World Man-Machine Checkers Champion » (consulté le 19 juillet 2007)
  8. Justin Mullins, « Checkers 'solved' after years of number crunching », NewScientist.com news service, (consulté le 20 juillet 2007)
  9. (ja) Données de résolution du dobutsu shogi.
  10. P. Henderson, B. Arneson, and R. Hayward[webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Solving 8×8 Hex ], Proc.
  11. Hexapawn
  12. « How to Always Win Chopsticks », wikiHow (consulté le 28 avril 2013)
  13. Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
  14. Solving (6,6)-Kalaha by Anders Carstensen.
  15. For all responses to 1. e3 except 1...c5 and 1...b6, see: Mark Watkins, « Solved Openings in Losing Chess », (consulté le 15 janvier 2015)
  16. Nine Men's Morris is a Draw by Ralph Gasser
  17. Pangki is strongly solved as a Draw by Jason Doucette
  18. Geoffrey Irving: "Pentago is a first player win" http://perfect-pentago.net/details.html
  19. Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344.
  20. a et b John's Connect Four Playground
  21. http://archive.ics.uci.edu/ml/datasets/Connect-4
  22. Teeko, by E. Weisstein
  23. Three Musketeers, by J. Lemaire
  24. Yew Jin Lim. On Forward Pruning in Game-Tree Search. Ph.D. Thesis, National University of Singapore, 2007.
  25. 5×5 Go is solved by Erik van der Werf
  26. Counting legal positions in Go, Tromp and Farnebäck, accessed 2007-08-24.
  27. Some of the nine-piece endgame tablebase by Ed Gilbert
  28. 6×6 Othello weakly solved « Copie archivée » (version du 1 novembre 2009 sur l'Internet Archive)

Lectures complémentaires[modifier | modifier le code]

  • Victor Allis, Beating the World Champion? The state-of-the-art in computer game playing. dans « New Approaches to Board Games Research ».

Liens externes[modifier | modifier le code]