Résoudre un jeu

Quoi résoudre un jeu ? C'est possible ça ?
Oui, il s'agit d'une expression purement mathématiques.

Le plus simple pour comprendre ce que cela signifie est de commencer par considérer des jeux combinatoires abstraits, c'est à dire des jeux :

• opposant généralement deux joueurs ou deux équipes (ou bien un joueur humain seul contre un ordinateur « intelligent ») ;
• dans lequel les joueurs ou équipes jouent à tour de rôle ;
• dont tous les éléments sont connus (jeu à information complète) ;
• où le hasard n'intervient pas pendant le déroulement du jeu.

 Lorsque plus de deux joueurs ou équipes participent, un aspect diplomatique ou relationnel empêche le classement du jeu comme purement combinatoire.

Les échecs, les dames, le jeu de go, le puissance 4 sont des exemples de tels jeux... A l'inverse le backgammon, le tarot, le yams, le jungle speed ou le scrabble ne sont pas des jeux combinatoires abstraits.


On dit qu'un jeu est résolu lorsque l'on a trouvé une méthode pour gagner à coup sûr, ou que l'on a démontrer qu'il n'existe pas de telles méthodes. Grâce à l'essor de l'informatique et aux capacités de calculs toujours plus grande, beaucoup de jeux ont été résolu ces dernières années. Mais certains résistent encore !


Puissance 4

Le jeu qui date de 1974 a été résolu de façon exacte en 1988, indépendamment par James D. Allen et par Victor Allis avec des calculs informatiques.

Conclusion de leurs travaux : Le joueur qui commence gagne !
Si le premier coup est la colonne du milieu et que le premier joueur joue parfaitement, il gagnera à chaque fois ! Si le premier coup est la colonne 3 ou la colonne 5, alors le second joueur peut arracher le match nul et si le premier coup est dans une autre colonne, alors le second joueur peut gagner.

Le logiciel libre : Mustrum ( téléchargeable gratuitement ici : http://mustrum.updatestar.com/fr ) est un logiciel ayant une connaissance complète du jeu. Réglé en difficulté infini, le logiciel gagnera donc systématiquement s'il commence.


Awalé

Jeu de combinatoire très répandu sur le continent africain.
Ce jeu fut résolu en 2002 par John W. Romein and Henri E. Bal à l'aide d'une grappe de 144 processeurs.
Pour résoudre le jeu, il fut utilisé des bases de données correspondant à toutes les configurations possibles avec un nombre de graine fixé. La plus grosses base de donnée est celle correspondant à 48 graines avec plus de 200 billions de possibilités. Jamais une telle capacité de mémoire n'avait été utilisé en théorie des jeux jusque là.

Conclusion de leurs travaux : Si chaque joueur joue à la perfection, peut importe qui commence, il y aura toujours match nul.


Les dames, les échecs, le jeu de go...

Nous atteignons ici les limites de  l'informatique. Actuellement la question de la solvabilité du jeu de dames, des echecs ou encore du jeu de go sont totalement hors de portée des ordinateurs actuels.