Existe-t-il un jeu avec une infinité d'arrangements possibles du plateau (conditions d'expérience infinies ?), mais qui a été fortement résolu, c'est-à-dire dont le coup optimal à chaque étape du jeu a été résolu ?
Si un tel jeu existe et si son nom est donné, il me sera d'une grande aide. Je l'attends. Cela va me permettre de faire certaines conclusions dans d'autres domaines par analogie.
Vous demandez un jeu fortement résolu (en référence vraisemblablement au terme de la théorie des jeux combinatoires). Selon Wikipédia les jeux qui sont fortement résolus
Fournir un algorithme capable de 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 côtés.
Il ajoute que, dans de nombreux cas, cette décision est prise par force brute :
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 afin de déterminer ce qui se passerait si le jeu parfait était réalisé. La preuve qui en résulte donne une stratégie optimale pour chaque position possible sur l'échiquier.
Par exemple, nous pouvons fortement résoudre le morpion 3x3 parce que nous pouvons utiliser la force brute pour toutes les combinaisons possibles et déterminer les mouvements parfaits. Bien sûr, la force brute est impossible pour une taille de plateau infinie, et certains jeux ne sont fortement résolus que jusqu'à une certaine taille de plateau. Par exemple, Hex n'est résolu que jusqu'à un plateau de 6x6. Néanmoins, l'espoir est que cette force brute sur des jeux comme ceux-ci conduira à un algorithme pour le jeu parfait qui fonctionne pour une taille infinie (par exemple, un plateau de 6x6). N x N conseil).
Le jeu le mieux étudié et le plus résolu est Nim Un algorithme a été trouvé pour produire un jeu parfait à partir de n'importe quelle position de tas et d'objets de n'importe quelle taille. Ce jeu peut être joué sur un plateau (ou simplement en dessinant sur une feuille de papier), il est donc considéré comme un jeu de société.
La plupart des autres jeux combinatoires se jouent sur un plateau fixe et ne sont généralement pas étudiés à l'école. N x N tailles. Dans certains cas, un algorithme pour ces tailles n'est pas possible. Comme décrit ci-dessus, Hex a été fortement résolu pour un plateau 6x6. Cependant, un algorithme qui fonctionne pour N x N Il est peu probable que l'on trouve des cartes car le problème est PSPACE-complet Cela signifie que le nombre de coups possibles augmente de façon polynomiale par rapport à la taille du plateau, et qu'il faudrait un temps polynomial pour résoudre le jeu pour une taille donnée. On soupçonne que ce type de jeu est insoluble car le calcul pour une taille infinie prendrait un temps polynomial infini.
Notez que les jeux comme les échecs, les dames et le go sont EXPTIME-complet Ce qui signifie que le nombre de coups possibles augmente de manière exponentielle par rapport à la taille du plateau. Étant donné que la résolution d'un plateau infini prend un temps exponentiellement infini, les problèmes EXPTIME-complets comme celui-ci sont également soupçonnés d'être insolubles. Puisque le temps exponentiel est plus long que le temps polynomial, et que les problèmes PSPACE-complets sont soupçonnés d'être insolubles, les problèmes EXPTIME-complets sont généralement considérés comme totalement insolubles.
Pour référence, il a fallu 18 ans pour résoudre le jeu de dames 8×8 par force brute. . Il faudrait exponentiellement plus de travail pour résoudre un tableau de 9x9.
(Cela fait longtemps que je n'ai pas étudié ce genre de choses, mais je me souviens vaguement d'une recherche sur l'impact que les ordinateurs quantiques pourraient avoir sur ce type de problème. Si je me souviens bien, il pourrait être possible de réduire un problème PSPACE à un problème P qui peut être résolu efficacement en temps polynomial, quelle que soit la taille de l'entrée. Cela dit, je ne suis pas un expert dans ce domaine, alors prenez-le avec un grain de sel).
Avertissement : Je ne suis pas un expert dans ce domaine et cela fait des années que je ne l'ai pas étudié. Si j'ai fait des déclarations incorrectes à propos de PSPACE-Complet etc. dans cette réponse, veuillez le signaler dans les commentaires ou la corriger.
Un exemple non Nim est celui qui est habituellement présenté comme une énigme, tel que cette question de Puzzling.SE . Les règles du jeu sont :
Sur une table symétrique (normalement circulaire ou carrée), deux joueurs placent à tour de rôle des pièces de monnaie sur la table de façon à ce que deux pièces ne se chevauchent pas. Le joueur qui, le premier, ne parvient pas à placer une pièce perd.
Il existe un nombre infini de positions sur le plateau, car les pièces peuvent être placées n'importe où dans l'espace de la table, et (au moins dans une abstraction pure) tout changement de la taille d'un epsilon dans la position d'une pièce est techniquement un état différent du plateau.
Le jeu est résolu, car la stratégie optimale du premier joueur est :
Tant que le premier joueur fait cela, le second joueur perd toujours, quelle que soit sa stratégie (et si le premier joueur ne le fait pas, je soupçonne qu'il y a un moyen pour le second joueur de voler la victoire par stratégie dans de nombreux cas).
AlleGamers est une communauté de gamers qui cherche à élargir la connaissance des jeux vidéo.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
