Jeu résolu

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

Vue d'ensemble

Un jeu à deux (en) peut avoir plusieurs niveaux de « résolution » :

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 aux dames anglaises 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 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é 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 une vaste base de données pré-générées, et, en effet, rien de plus.

Comme exemple de résolution forte, 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 facilement déterminable à la main). 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 cipayes). 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.

Le jeu parfait

En théorie des jeux, le jeu parfait est le comportement où 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

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 appelée « checkers », dans laquelle la dame ne fait pas de déplacement long, 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. Le jeu de dames anglaises est le plus grand jeu qui ait été résolu à ce jour, avec un espace de recherche de 5×10²⁰. Le nombre de calculs à réaliser était de 10¹⁴, 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.

Dobutsu shogi

Fortement résolu. Le jeu aboutit à une victoire du joueur ne commençant pas.

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 ne peuvent pas être perdus par le premier joueur s'il joue convenablement. 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.

Hexapawn

La variante 3×3 est résolue comme une victoire pour le noir, plusieurs autres variantes plus grandes sont également résolues.

Le jeu des baguettes

Le second joueur peut toujours forcer une victoire.

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

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.

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). 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. Le premier joueur gagne.

Pentominos

Faiblement résolu par Hilarie K. Orman. C'est une victoire pour le premier joueur.

Puissance 4

Résolu d'abord par James D. Allen (1^er octobre 1988), et indépendamment par Victor Allis (en) (16 octobre 1988). Le premier joueur peut forcer une victoire. Fortement résolu avec la base de données de John Tromp (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) (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.

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

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.

Jeux partiellement résolus

É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émorisable de mouvements qui assure la victoire du joueur cipayes.

Go

Le plateau 5×5 est faiblement résolu pour tous les coups d'ouverture. 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.

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

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. 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 plateaux 10×10 et plus.

Voir aussi

• Programme d'échecs
• Go en informatique
• Programme d'Othello (en)
• Complexité du jeu (en)
• Algorithme de Dieu
• Le théorème de Zermelo

Références

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

Bibliographie

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

Liens externes

• (en) Computational Complexity of Games and Puzzles par David Eppstein.
• GamesCrafters la résolution de deux jeux à information parfaite et aucun hasard.