Aller au contenu principal

Stratégies gagnantes dans les jeux finis : existence, construction et exécution

Dire qu’un joueur « possède une stratégie gagnante » peut répondre à trois questions différentes. Une preuve peut établir l’existence d’une stratégie, une construction peut indiquer le coup à jouer dans chaque position, et une mise en œuvre peut produire ces coups avec un temps et une mémoire réalistes. Résoudre le premier problème ne résout pas automatiquement les deux autres.

Ce que détermine un jeu fini​

Considérons un jeu dont le nombre de positions et la durée maximale sont finis. Deux joueurs jouent à tour de rôle, aucun hasard n’intervient, chacun connaît tout l’historique et la position actuelle, et leurs intérêts sont opposés. Le développement de toutes les suites légales donne un arbre de jeu fini. En remontant depuis les positions terminales, on attribue à chaque position antérieure son résultat sous jeu optimal.

Lorsque la partie nulle est possible, l’énoncé moderne affirme qu’un joueur peut forcer la victoire, ou que chacun peut garantir au moins la partie nulle. La détermination donne une valeur théorique à la position initiale ; elle ne fournit pas nécessairement un premier coup utilisable. Une formulation moderne de la détermination des jeux finis énonce le résultat dans ce cadre général.

L’article de Zermelo paru en 1913 étudiait des questions issues des échecs et a fourni une base importante à ce raisonnement. L’énoncé abstrait complet et ses conditions actuelles ont été formulés par la suite. Il ne faut donc pas attribuer mot pour mot le théorème moderne à cet article. Une étude historique distingue le résultat de Zermelo de ses formulations ultérieures.

Des stratégies directement constructibles​

Certains jeux admettent une règle courte qui prouve le résultat tout en indiquant les coups à jouer.

Une pile de 50 bonbons​

Une pile contient 50 bonbons. Chaque joueur en retire de 1 à 3, et celui qui prend le dernier gagne. Un multiple de 4 est une position perdante pour le joueur qui doit jouer : quel que soit son retrait, l’adversaire peut faire en sorte que les deux coups totalisent 4.

Le premier joueur retire 2 bonbons et en laisse 48. Si l’adversaire en retire ensuite xx, le premier en retire 4−x4-x. Après chaque paire de coups, le nombre restant est encore un multiple de 4 ; le premier joueur finit donc par prendre le dernier bonbon. L’invariant fournit à la fois la preuve d’existence, la construction et une procédure facile à exécuter.

Deux piles égales​

Partons de deux piles de 100 bonbons. Un coup retire un nombre positif quelconque de bonbons d’une seule pile, et celui qui prend le dernier bonbon gagne. Deux piles égales constituent une position perdante pour le joueur qui doit jouer.

Le second joueur gagne donc depuis la position initiale. Chaque fois que le premier retire des bonbons d’une pile, le second en retire autant de l’autre. En rétablissant l’égalité après chaque paire de coups, il finit par vider la dernière pile.

Ce que le vol de stratégie ne construit pas​

Un raisonnement par vol de stratégie commence généralement par supposer que le second joueur possède une stratégie gagnante. Si un coup d’ouverture supplémentaire ne peut pas nuire au premier joueur, celui-ci peut jouer ce coup puis adopter la stratégie supposée du second, ce qui produit une contradiction. Le raisonnement exclut ainsi une victoire forcée du second, mais il n’indique souvent pas le bon coup d’ouverture.

Chomp​

Dans le Chomp rectangulaire, un coup mange une case ainsi que la partie située au-dessus et à sa droite ; le joueur contraint de manger la case empoisonnée perd. Sauf sur le plateau 1×11 \times 1, le vol de stratégie prouve que le premier joueur gagne, mais il ne donne aucun premier coup général pour un rectangle quelconque. L’article original sur Chomp présente ce résultat non constructif. Le plateau 1×11 \times 1 est l’exception explicite : le premier joueur ne peut que manger la case empoisonnée et perdre.

Hex symétrique standard sans règle d’échange​

Le Hex standard ne peut pas se terminer par une partie nulle. Sur un plateau symétrique, échanger les bords cibles des joueurs conserve la structure du jeu, et une pierre supplémentaire de sa propre couleur ne peut pas gêner une connexion. Si le second joueur disposait d’une stratégie gagnante, le premier pourrait poser une pierre arbitraire, puis utiliser la symétrie pour adopter cette stratégie. La pierre supplémentaire ne pouvant pas lui nuire, l’hypothèse mène à une contradiction : le premier joueur gagne.

La preuve ne donne toujours aucun premier coup universel. Elle ne vaut que pour les règles indiquées. La règle d’échange, aussi appelée « pie rule », modifie les droits à l’ouverture ; on ne peut donc pas lui appliquer directement la même conclusion. Un exposé classique de Hex, de l’absence de partie nulle et du vol de stratégie donne l’argument complet.

Une stratégie existante peut rester inexécutable​

Un arbre de jeu fini peut être développable en principe tout en dépassant les budgets réalistes de temps et de mémoire. Les programmes et les joueurs humains n’explorent donc que certaines branches ou s’arrêtent à une profondeur limitée, puis évaluent les positions non développées. Regrouper les positions symétriques, éliminer des coups déjà prouvés sans effet et suivre les coups forcés sont des formes générales d’élagage de l’arbre de jeu.

L’élagage alpha-bêta a un sens plus précis. Dans une recherche minimax, il maintient une borne inférieure α\alpha et une borne supérieure β\beta sur le résultat que chaque camp peut garantir. Une branche n’est coupée que lorsque ces bornes prouvent qu’elle ne peut plus modifier le choix actuel. L’analyse de Knuth et Moore et les notes de cours de CMU en donnent des définitions précises. Dans la vidéo, le commentaire sur le morpion omet des branches au sens général de l’élagage d’un arbre de jeu ; cette narration ne suffit pas à constituer une démonstration stricte de l’algorithme alpha-bêta.

Le Gomoku dépend des règles​

Le vol de stratégie exige qu’une pierre alliée supplémentaire ne puisse pas dégrader une position. Dans le Gomoku libre, où une ligne de plus de cinq pierres gagne aussi, une pierre supplémentaire n’annule pas une ligne alliée existante. Le raisonnement peut donc exclure une victoire forcée du second joueur. Si la partie nulle reste possible, il prouve seulement que le premier peut gagner ou au moins éviter de perdre. Le vol de stratégie ne suffit pas à prouver sa victoire.

Le Go-Moku standard à cinq exactement exige une ligne d’exactement cinq pierres. Ajouter une pierre peut transformer cette ligne en surligne et annuler ce qui aurait été une victoire ; l’argument de monotonie ne s’applique donc plus. Le résultat résolu pour un plateau et des règles donnés demande une recherche informatique et une preuve distinctes. La synthèse des jeux résolus traite elle aussi le Go-Moku selon des règles précises.

Interpréter une affirmation de stratégie gagnante​

Trois vérifications permettent de préciser l’affirmation : les règles satisfont-elles les conditions du théorème, la preuve construit-elle les coups, et ces coups peuvent-ils être trouvés et joués avec les ressources disponibles ? Les jeux de bonbons franchissent ces trois niveaux. Chomp et le Hex symétrique standard sans règle d’échange établissent surtout l’existence. Dans les jeux plus grands, la recherche, la représentation et l’élagage traitent le coût de l’exécution.

Sources​