Jeu résolu

Un article de Wikipédia, l'encyclopédie libre
Aller à la navigationAller à la recherche

Un jeu résolu est un jeu dont le résultat (gagnant, perdant ou nul ) peut être correctement prédit à partir de n'importe quelle position, en supposant que les deux joueurs jouent parfaitement. Ce concept est généralement appliqué aux jeux de stratégie abstraits , et en particulier aux jeux avec une information complète et sans élément de hasard ; la résolution d'un tel jeu peut utiliser la théorie des jeux combinatoires et/ou l'assistance informatique.

Aperçu

Une partie à deux joueurs peut être résolue à plusieurs niveaux : [1] [2]

Ultra-faible
Prouvez si le premier joueur va gagner, perdre ou faire match nul depuis la position initiale, étant donné un jeu parfait des deux côtés. Cela peut être une preuve non constructive (impliquant éventuellement un argument de vol de stratégie ) qui n'a pas besoin de déterminer réellement les mouvements du jeu parfait.
Faible
Fournissez un algorithme qui garantit une victoire pour un joueur, ou un match nul pour l'un ou l'autre, contre tous les mouvements possibles de l'adversaire, dès le début de la partie. C'est-à-dire, produire au moins un jeu idéal complet (tous les mouvements du début à la fin) avec la preuve que chaque mouvement est optimal pour le joueur qui le fait. Cela ne signifie pas nécessairement qu'un programme informatique utilisant la solution jouera de manière optimale contre un adversaire imparfait.
Fort
Fournissez un algorithme qui peut produire des mouvements parfaits à partir de n'importe quelle position, même si des erreurs ont déjà été commises d'un côté ou des deux.

Malgré leur nom, de nombreux théoriciens des jeux pensent que les preuves « ultra-faibles » sont les plus profondes, les plus intéressantes et les plus précieuses. Les preuves « ultra-faibles » demandent à un érudit de raisonner sur les propriétés abstraites du jeu et de montrer comment ces propriétés conduisent à certains résultats si un jeu parfait est réalisé. [ citation nécessaire ]

En revanche, les preuves "fortes" procèdent souvent par force brute - en utilisant un ordinateur pour rechercher de manière exhaustive un arbre de jeu pour comprendre ce qui se passerait si un jeu parfait était réalisé. La preuve qui en résulte donne une stratégie optimale pour chaque position possible sur le tableau. Cependant, ces preuves ne sont pas aussi utiles pour comprendre les raisons plus profondes pour lesquelles certains jeux peuvent être résolus comme un match nul, et d'autres jeux apparemment très similaires peuvent être résolus comme une victoire.

Étant donné les règles de tout jeu à deux personnes avec un nombre fini de positions, on peut toujours construire de manière triviale un algorithme minimax qui parcourrait de manière exhaustive l' arbre du jeu . Cependant, étant donné que pour de nombreux jeux non triviaux, un tel algorithme nécessiterait un temps infaisable 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 ne puisse être exécuté par le matériel existant dans un temps raisonnable. De nombreux algorithmes reposent sur une énorme base de données pré-générée et ne sont en réalité rien de plus.

A titre d'exemple de solution forte, le jeu de morpion est résoluble comme un match nul pour les deux joueurs avec un jeu parfait (un résultat même manuellement déterminable par les écoliers). Des jeux comme nim admettent également une analyse rigoureuse utilisant la théorie des jeux combinatoires .

Qu'un jeu soit résolu n'est pas nécessairement la même chose que s'il reste intéressant pour les humains à jouer. 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 stratégie gagnante est suffisamment simple à retenir (par exemple, Maharajah et les Cipayes ). Une solution ultra-faible (par exemple, Chomp ou Hex sur un plateau suffisamment grand) n'affecte généralement pas la jouabilité.

De plus, même si le jeu n'est pas résolu, il est possible qu'un algorithme donne une bonne solution approximative : par exemple, un article de Science de janvier 2015 affirme que leur heads-up limit Texas hold'em poker bot Cepheus garantit qu'une vie humaine de jeu n'est pas suffisant pour établir avec une signification statistique que sa stratégie n'est pas une solution exacte. [3] [4] [5]

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 ce joueur, quelle que soit la réponse de l'adversaire. Le jeu parfait pour un jeu est connu lorsque le jeu est résolu. [1] Sur la base des règles d'un jeu, chaque position finale possible peut être évaluée (comme une victoire, une défaite ou un match nul). Par raisonnement à rebours, on peut évaluer récursivement une position non finale comme identique à la position qui est à un coup et la mieux valorisée pour le joueur dont c'est le coup. Ainsi, une transition entre des positions ne peut jamais aboutir à une meilleure évaluation pour le joueur en mouvement, et un mouvement parfait dans une position serait une transition entre des positions qui sont également évaluées. Par exemple, un joueur parfait dans une position nulle obtiendrait toujours un match nul ou une victoire, jamais une défaite. S'il existe plusieurs options avec le même résultat, le jeu parfait est parfois considéré comme la méthode la plus rapide menant à un bon résultat, ou la méthode la plus lente menant à un mauvais résultat.

Le jeu parfait peut être généralisé aux jeux d' information non parfaits , en tant que stratégie qui garantirait le résultat minimal attendu le plus élevé, quelle que soit la stratégie de l'adversaire. À titre d'exemple, la stratégie parfaite pour les ciseaux à papier rock serait de choisir au hasard chacune des options avec une probabilité égale (1/3). L'inconvénient dans cet exemple est que cette stratégie n'exploitera jamais les stratégies non optimales de l'adversaire, de sorte que le résultat attendu de cette stratégie par rapport à n'importe quelle stratégie sera toujours égal au résultat minimal attendu.

Bien que la stratégie optimale d'un jeu ne soit pas (encore) connue, un ordinateur de jeu peut tout de même bénéficier des solutions du jeu à partir de certaines positions de fin de partie (sous la forme de bases de table de fin de partie ), ce qui lui permettra de jouer parfaitement après quelques point dans le jeu. Les programmes d' échecs informatiques sont bien connus pour faire cela.

Jeux résolus

Awari (un jeu de la famille Mancala )
La variante d' Oware permettant de terminer le jeu en "grand chelem" a été fortement résolue par Henri Bal et John Romein à la Vrije Universiteit à Amsterdam , Pays - Bas (2002). L'un ou l'autre joueur peut forcer le jeu à un match nul.
Baguettes
Le deuxième joueur peut toujours forcer une victoire. [ citation nécessaire ]
Connectez quatre
Résolu d'abord par James D. Allen le 1er octobre 1988 et indépendamment par Victor Allis le 16 octobre 1988. [6] Le premier joueur peut forcer une victoire. Fortement résolu par la base de données à 8 plis de John Tromp [7] (4 février 1995). Faiblement résolu pour toutes les tailles de planches où largeur+hauteur est au maximum de 15 (ainsi que 8×8 fin 2015) [6] (18 février 2006).
Brouillons anglais (dames)
Cette variante de brouillons 8×8 a été faiblement résolue le 29 avril 2007, par l'équipe de Jonathan Schaeffer . À partir de la position de départ standard, les deux joueurs peuvent garantir un match nul avec un jeu parfait. [8] Checkers est le plus grand jeu qui a été résolu à ce jour, avec un espace de recherche de 5×10 20 . [9] Le nombre de calculs impliqués était de 10 14 , qui ont été effectués sur une période de 18 ans. Le processus impliquait de 200 ordinateurs de bureau à son apogée à environ 50. [10]
Fanorona
Faiblement résolu par Maarten Schadd. Le jeu est un match nul. [ citation nécessaire ]
Gomoku gratuit
Résolu par Victor Allis (1993). Le premier joueur peut forcer une victoire sans ouvrir les règles.
Fantôme
Résolu par Alan Frank à l'aide du dictionnaire officiel des joueurs de Scrabble en 1987. [ citation nécessaire ]
Devine qui?
Fortement résolu par Mihai Nica en 2016. [11] Le premier joueur a 63% de chances de gagner sous un jeu optimal des deux côtés.
Hex
  • Un argument de vol de stratégie (tel qu'utilisé par John Nash ) montre que toutes les tailles de plateau carré ne peuvent pas être perdues par le premier joueur. Combiné à une preuve de l'impossibilité d'un match nul, cela montre que le jeu est résolu ultra-faible en tant que premier joueur gagnant.
  • Fortement résolu par plusieurs ordinateurs pour des tailles de carte jusqu'à 6×6.
  • Jing Yang a démontré une stratégie gagnante (solution faible) pour les tailles de planche 7×7, 8×8 et 9×9.
  • Une stratégie gagnante pour Hex avec échange est connue pour le tableau 7×7.
  • Résoudre fortement Hex sur une carte N × N est peu probable car il a été démontré que le problème est PSPACE-complet .
  • Si Hex est joué sur un plateau N × ( N +1) alors le joueur qui a la distance la plus courte pour se connecter peut toujours gagner par une simple stratégie d'appariement, même avec l'inconvénient de jouer le deuxième.
  • Une solution faible est connue pour tous les coups d'ouverture sur le plateau 8×8. [12]
Hexapawn
Variante 3 × 3 résolue comme une victoire pour le noir, plusieurs autres variantes plus grandes également résolues. [13]
Kalah
La plupart des variantes résolues par Geoffrey Irving, Jeroen Donkers et Jos Uiterwijk (2000) sauf Kalah (6/6). La variante (6/6) a été résolue par Anders Carstensen (2011). Le fort avantage du premier joueur a été prouvé dans la plupart des cas. [14] [15] Mark Rawlings, de Gaithersburg, MD, a quantifié l'ampleur de la victoire du premier joueur dans la variante (6/6) (2015). Après la création de 39 Go de bases de données de fin de partie, des recherches totalisant 106 jours de temps CPU et plus de 55 000 milliards de nœuds, il a été prouvé qu'avec un jeu parfait, le premier joueur gagne par 2. Notez que tous ces résultats se réfèrent à la Capture à fosse vide. variante et sont donc d'un intérêt très limité pour le jeu standard. L'analyse du jeu de règles standard a maintenant été publiée pour Kalah (6,4), qui est une victoire de 8 pour le premier joueur, et Kalah (6,5), qui est une victoire de 10 pour le premier joueur. L'analyse de Kalah (6,6) avec les règles standard est en cours, cependant, il a été prouvé qu'il s'agit d'une victoire d'au moins 4 pour le premier joueur.
L jeu
Facilement résolvable. L'un ou l'autre joueur peut forcer le jeu à un match nul.
Perdre les échecs
Faiblement résolu comme une victoire pour les blancs commençant par 1. e3. [16]
Maharajah et les Cipayes
Ce jeu asymétrique est une victoire pour le joueur de cipayes avec un jeu correct.
Nim
Fortement résolu.
Morris neuf hommes
Résolu par Ralph Gasser (1993). L'un ou l'autre joueur peut forcer le jeu à un match nul. [17]
Ordre et chaos
L'ordre (premier joueur) gagne. [18]
Ohvalhu
Faiblement résolu par les humains, mais prouvé par les ordinateurs. (Dakon n'est cependant pas identique à Ohvalhu, le jeu qui avait en réalité été observé par de Voogt)
Pangki
Fortement résolu par Jason Doucette (2001). [19] Le jeu est un match nul. Il n'y a que deux premiers coups uniques si vous supprimez les positions en miroir. L'un force le tirage au sort, et l'autre donne à l'adversaire une victoire forcée en 15.
Pentominos
Faiblement résolu par HK Orman. [20] C'est une victoire pour le premier joueur.
Poddavki (" Jeu de dames russes")
Résolu par Osipov et Morozev en 2011. Une victoire blanche. [ citation nécessaire ]
Quarto
Résolu par Luc Goossens (1998). Deux joueurs parfaits feront toujours match nul.
Qubique
Faiblement résolu par Oren Patashnik (1980) et Victor Allis . Le premier joueur gagne.
Jeu de type Renju sans règles d'ouverture impliquées
Prétendument résolu par János Wagner et István Virág (2001). Une victoire du premier joueur.
Sim
Faiblement résolu : victoire pour le deuxième joueur.
Teeko
Résolu par Guy Steele (1998). Selon la variante, soit une victoire du premier joueur, soit un match nul. [21]
Morris trois hommes
Trivialement soluble. L'un ou l'autre joueur peut forcer le jeu à un match nul.
Trois Mousquetaires
Fortement résolu par Johannes Laire en 2009, et faiblement résolu par Ali Elabridi en 2017. [22] C'est une victoire pour les pièces bleues (les hommes du cardinal Richelieu, ou, l'ennemi). [23]
Tic-tac-toe
Trivialement fortement soluble à cause du petit arbre à gibier. [24] Le match est nul si aucune erreur n'est commise, aucune erreur n'étant possible sur le coup d'ouverture.
Tigres et chèvres
Faiblement résolu par Yew Jin Lim (2007). Le jeu est un match nul. [25]
Le jeu de Wythoff
Fortement résolu.

Jeux partiellement résolus

Jeu d'échecs
Résoudre complètement les échecs reste insaisissable, et il est supposé que la complexité du jeu peut empêcher sa résolution. Grâce à une analyse informatique rétrograde , des bases de table de fin de partie (solutions solides) ont été trouvées pour toutes les finales de trois à sept pièces , en comptant les deux rois comme des pièces.
Certaines variantes d'échecs sur un échiquier plus petit avec un nombre réduit de pièces ont été résolues. Certaines autres variantes populaires ont également été résolues ; par exemple, une solution faible à Maharajah et aux Cipayes est une série de coups facilement mémorables qui garantit la victoire au joueur "cipayes".
Aller
Le plateau 5 × 5 a été faiblement résolu pour tous les coups d'ouverture en 2002. [26] Le plateau 7 × 7 a été faiblement résolu en 2015. [27] Les humains jouent généralement sur un plateau 19 × 19 qui est plus complexe de plus de 145 ordres de grandeur. que 7×7. [28]
Brouillons internationaux
Toutes les positions de fin de partie avec deux à sept pièces ont été résolues, ainsi que les positions avec 4 × 4 et 5 × 3 pièces où chaque camp avait un roi ou moins, les positions avec cinq hommes contre quatre hommes, les positions avec cinq hommes contre trois hommes et un roi, et des positions avec quatre hommes et un roi contre quatre hommes. Les positions finales ont été résolues en 2007 par Ed Gilbert des États-Unis. L'analyse informatique a montré qu'il était très probable que les deux joueurs jouaient parfaitement. [29] [ une meilleure source nécessaire ]
m,n,k-jeu
Il est trivial de montrer que le deuxième joueur ne peut jamais gagner ; voir argument de 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 tirés pour k 8.
Reversi (Othello)
Faiblement résolu sur un plateau 4×4 et 6×6 en tant que deuxième joueur remporté en juillet 1993 par Joel Feinstein. [30] Sur un tableau 8 × 8 (le standard), il est mathématiquement non résolu, bien que l'analyse informatique montre un tirage probable. Il n'existe pas d'estimations fortement supposées autres que des chances accrues pour le premier joueur (Noir) sur des tableaux 10×10 et plus.

Voir aussi

  • Échecs informatiques
  • Ordinateur aller
  • Ordinateur Othello
  • Complexité du jeu
  • L'algorithme de Dieu
  • Théorème de Zermelo (théorie des jeux)

Références

  1. ^ un b Victor Allis (1994). "Thèse de doctorat: Recherche de solutions dans les jeux et l'intelligence artificielle" (PDF) . Département d'informatique . Université du Limbourg . Récupéré le 14/07/2012 .
  2. ^ H. Jaap van den Herik , Jos WHM Uiterwijk, Jack van Rijswijck, Jeux résolus : maintenant et à l'avenir , Intelligence artificielle 134 (2002) 277-311.
  3. ^ Bowling, M.; Burch, N.; Johanson, M. ; Tammelin, O. (janvier 2015). "Le poker Hold'em Limit Hold'em est résolu" (PDF) . Sciences . 347 (6218) : 145-9. CiteSeerX 10.1.1.697.72 . doi : 10.1126/science.1259433 . PMID 25574016 . S2CID 3796371 .    
  4. ^ Philip Ball (2015-01-08). "Les théoriciens du jeu crackent le poker" . Nature . La nature. doi : 10.1038/nature.2015.16683 . S2CID 155710390 . Récupéré le 13/01/2015 . 
  5. ^ Robert Lee Hotz (2015-01-08). "L'ordinateur conquiert le Texas Hold 'Em, disent les chercheurs" . Wall Street Journal .
  6. ^ un b "John's Connect Four Playground" . tromp.github.io .
  7. ^ "Référentiel d'apprentissage automatique UCI : Ensemble de données Connect-4" . archive.ics.uci.edu .
  8. ^ Schaeffer, Jonathan (2007-07-19). "Les dames sont résolues" . Sciences . 317 (5844) : 1518-1522. doi : 10.1126/science.1144079 . PMID 17641166 . S2CID 10274228 . Récupéré le 2007-07-20 .  
  9. ^ "Projet - Chinook - Champion du monde de dames homme-machine" . Récupéré le 2007-07-19 .
  10. ^ Mullins, Justin (2007-07-19). "Les dames 'résolues' après des années de calculs chiffrés" . Service de nouvelles de NewScientist.com . Récupéré le 2020-12-06 .
  11. ^ Stratégie optimale dans « Devinez qui ? » : Au-delà de la recherche binaire par Mihai Nica.
  12. ^ P. Henderson, B. Arneson et R. Hayward [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Résolution 8 × 8 Hex ], Proc. IJCAI-09 505-510 (2009) Consulté le 29 juin 2010.
  13. ^ Prix, Robert. "Hexapawn" . www.chessvariants.com .
  14. ^ Résoudre Kalah par Geoffrey Irving, Jeroen Donkers et Jos Uiterwijk.
  15. ^ Résolution (6,6)-Kalaha par Anders Carstensen.
  16. ^ Watkins, Marc. "Perdre les échecs : 1. e3 gagne pour les blancs" (PDF) . Consulté le 17 janvier 2017 .
  17. ^ Morris de neuf hommes est un tirage au sort par Ralph Gasser
  18. ^ "Résolu : L'ordre gagne - L'ordre et le chaos" .
  19. ^ Pangki est fortement résolu en tirage au sort par Jason Doucette
  20. ^ Hilarie K. Orman : Pentominoes : A First Player Win in Games of No Chance , MSRI Publications – Volume 29, 1996, pages 339-344. En ligne : pdf .
  21. ^ Teeko , par E. Weisstein
  22. ^ Elabridi, Ali. "Résoudre faiblement le jeu des trois mousquetaires en utilisant l'intelligence artificielle et la théorie des jeux" (PDF) .
  23. ^ Trois mousquetaires , par J. Lemaire
  24. ^ Tic-Tac-Toe , par R. Munroe
  25. ^ If Jin Lim. Sur l'élagage vers l'avant dans la recherche Game-Tree . doctorat Thèse, Université nationale de Singapour , 2007.
  26. ^ 5×5 Go est résolu par Erik van der Werf
  27. ^ "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客" . blog.sina.com.cn . (ce qui dit que la solution 7x7 n'est que faiblement résolue et qu'elle est toujours en cours de recherche, 1. le komi correct est 9 (4,5 pierres); 2. il existe plusieurs arbres optimaux - les 3 premiers mouvements sont uniques - mais dans les 7 premiers mouvements là-bas sont 5 arbres optimaux ; 3. Il existe de nombreuses façons de jouer qui n'affectent pas le résultat)
  28. ^ Comptage des positions juridiques dans Go Archivé le 2007-09-30 à la Wayback Machine , Tromp et Farnebäck, consulté le 2007-08-24.
  29. ^ Une partie de la base de table de fin de jeu en neuf pièces par Ed Gilbert
  30. ^ "6×6 Othello faiblement résolu" . Archivé de l'original le 2009-11-01.

Lectures complémentaires

  • Allis, battre le champion du monde ? L'état de l'art en matière de jeu sur ordinateur. dans Nouvelles approches de la recherche sur les jeux de société.

Liens externes

  • Complexité computationnelle des jeux et énigmes par David Eppstein.
  • GamesCrafters résolvant des jeux à deux avec des informations parfaites et aucune chance