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 peut avoir plusieurs niveaux de « résolution »V. Allis, Searching for Solutions in Games and Artificial Intelligence. 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. : 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 ) 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é.
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 annonce que leur version 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 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 à , 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 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 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×1020. 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.
Dobutsu shogi Fortement résolu. Le jeu aboutit à une victoire du joueur ne commençant pas Données de résolution du dobutsu shogi. .
Fanorona Faiblement résolu par Maarten Schadd. Le jeu aboutit à un nul.
Gomoku libre Résolu par (1993). Le premier joueur peut forcer une victoire sans les règles d'ouverture.
Résolu par Alan Frank à l'aide du 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×8P. Henderson, B. Arneson, and R. Hayward[webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Solving 8×8 Hex ], Proc. .
Hexapawn La variante 3×3 est résolue comme une victoire pour le noir, plusieurs autres variantes plus grandes sont également résoluesHexapawn.
Le jeu des baguettes Le second joueur peut toujours forcer une victoire.
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 casSolving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.Solving (6,6)-Kalaha by Anders Carstensen.. 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.e3For all responses to 1. e3 except 1...c5 and 1...b6, see: .
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 nulNine Men's Morris is a Draw by Ralph Gasser.
Congklak