Détermination des coups gagnants aux jeux de plateau

Déterminer si un jeu de plateau possède une « stratégie gagnante » (ou une stratégie pour faire match nul) relève, en mathématiques et en informatique, du domaine de la théorie des jeux combinatoires (Combinatorial Game Theory). Pour déterminer et trouver une stratégie gagnante, il faut généralement examiner les propriétés du jeu et appliquer les théorèmes et algorithmes mathématiques correspondants.

Voici les théories et méthodes couramment utilisées pour déterminer et prouver si un jeu de plateau a une stratégie gagnante :

1. Vérifier si le jeu satisfait les conditions préalables du théorème de Zermelo

Avant de discuter d'une stratégie gagnante, il faut d'abord confirmer si ce jeu de plateau appartient à la catégorie des « jeux finis à deux joueurs, à somme nulle et à information parfaite ».

• Deux joueurs : Il n'y a que deux joueurs.
• Somme nulle (ou victoire/défaite/nul) : La victoire d'un camp implique la défaite de l'autre, pas de double gain.
• Information parfaite : Pas d'information cachée (comme les cartes cachées au poker), les deux joueurs voient tout l'état du plateau.
• Déterministe : Pas d'élément aléatoire comme le lancer de dés.
• Fini : Le jeu se termine en un nombre fini de coups, sans boucle infinie.

Le théorème de Zermelo (Zermelo's Theorem) énonce que : Pour tout jeu satisfaisant les conditions ci-dessus, si les deux joueurs jouent de manière optimale, il y a nécessairement un résultat clair :

1. Le premier joueur gagne ;
2. Le second joueur gagne ;
3. Match nul (si les règles le permettent, comme aux échecs ou au morpion).

Autrement dit, tant que ces conditions sont remplies (par exemple aux échecs, au go, au gomoku, à l'othello), il existe théoriquement toujours une certaine stratégie gagnante ou une stratégie pour ne pas perdre (assurer le nul). Le défi est maintenant de « déterminer précisément de quel type il s'agit » et « comment la trouver ».

2. Recherche exhaustive et déduction inverse (arbre de jeu)

Pour les jeux dont l'espace d'états est petit, on peut énumérer toutes les positions possibles et générer un « arbre de jeu ».

• Méthode (induction à rebours) : Partir des états finaux (perte, gain, nul) et remonter jusqu'à la position initiale.
• Algorithme (Minimax) : En supposant que les deux joueurs ne commettent jamais d'erreur, le premier joueur choisit toujours le coup le plus avantageux pour lui (Max), et le second choisit toujours le coup le plus défavorable pour le premier (Min).
• Applications :
  • Morpion (Tic-Tac-Toe) : L'espace d'états est très petit, il est facile de déduire qu'avec des coups optimaux des deux côtés, le résultat est match nul.
  • Puissance 4 (Connect Four) : A été complètement résolu par ordinateur, prouvant que le premier joueur gagne.

3. Argument de vol de stratégie (Strategy-Stealing Argument)

C'est une méthode de preuve d'existence très ingénieuse (par l'absurde). Elle peut prouver que le premier joueur gagne, mais ne dit pas comment jouer concrètement.

• Logique : Supposons que le second joueur ait une stratégie gagnante. Alors, au premier coup, le premier joueur joue n'importe où, puis « vole » la stratégie gagnante du second joueur, se comportant comme s'il était le second joueur. Si, dans ce jeu, avoir un coup supplémentaire est toujours bénéfique (ou jamais nuisible), alors le premier joueur, en suivant la stratégie gagnante du second, gagnera forcément. Ceci contredit l'hypothèse que « le second joueur gagne » !
• Conclusion : Dans ce type de jeu, puisqu'il est impossible que le second joueur gagne et qu'il n'y a pas de match nul, alors c'est nécessairement le premier joueur qui gagne.
• Applications :
  • Hex : Les règles ne permettent pas le match nul, et placer un pion supplémentaire n'est jamais nuisible. Le mathématicien John Nash a donc utilisé cet argument pour prouver qu'à Hex, le premier joueur gagne.
  • Gomoku libre (sans interdictions) : A également prouvé que le premier joueur gagne (plus tard, l'ordinateur a trouvé des coups gagnants spécifiques, ce qui a conduit à l'introduction de « coups interdits » dans le gomoku pour équilibrer le jeu).

4. Recherche de symétrie (Symmetry / Pairing Strategy)

Si le plateau possède une certaine symétrie et que les règles le permettent, un joueur peut obtenir une stratégie gagnante en « imitant » les mouvements de l'adversaire.

• Exemple (jeu des pièces) : Sur une table ronde, les joueurs placent à tour de rôle des pièces plates ; celui qui ne peut plus placer une pièce perd. Le premier joueur place simplement sa première pièce au centre exact de la table, puis, où que le second joueur place la sienne, le premier place la sienne à la position symétrique par rapport au centre. Cette stratégie garantit que le premier joueur gagne.

5. Théorème de Sprague-Grundy (pour les jeux combinatoires impartiaux)

Si le jeu est « impartial » (Impartial Game) — c'est-à-dire que pour une même position, les coups légaux et les règles sont exactement les mêmes quel que soit le joueur dont c'est le tour (par exemple le jeu de Nim) — alors on peut utiliser le théorème SG.

• Méthode : Convertir toute position complexe en un jeu de Nim équivalent (calculer la fonction SG / somme XOR).
• Conclusion : Si le Nim-Sum (ou la valeur SG) de la position initiale est non nul, alors le premier joueur gagne ; s'il est nul, alors le second joueur gagne.

Résumé

• Théoriquement : Tant qu'il s'agit d'un jeu fini à deux joueurs, à information parfaite et sans hasard, il existe nécessairement une stratégie parfaite (gagner ou faire match nul).
• Comment la trouver :
  1. Plateau très petit : déduction manuelle à rebours.
  2. Modèle mathématique (ex. jeu de Nim) : calculer la valeur SG ou trouver une symétrie.
  3. Propriété spéciale : utiliser le « vol de stratégie » pour prouver que le premier joueur gagne.
  4. Plateau immense (ex. go, échecs) : actuellement, humains et IA ne peuvent calculer qu'une « solution optimale » infiniment proche de la victoire, mais au sens mathématique rigoureux, pour ces jeux complexes, savoir si c'est « le premier joueur qui gagne » ou « match nul » reste une question ouverte, car la puissance de calcul actuelle ne permet pas une énumération exhaustive complète.

Avant de discuter de la stratégie gagnante au gomoku, il faut clarifier une prémisse absolue : nous parlons ici du gomoku traditionnel « sans interdictions » (gomoku libre).

Dans le gomoku sans interdictions, le premier joueur (Noir) possède une stratégie gagnante. C'est d'ailleurs pourquoi les compétitions modernes de gomoku (renju) doivent introduire des « coups interdits pour Noir » (interdiction du double trois, double quatre, et des alignements de plus de cinq pions) ainsi que des règles d'ouverture complexes (comme la règle de Yamaguchi), dans le but de briser cette situation de victoire assurée pour le premier joueur et de rendre le jeu plus équitable.

Voici le contenu spécifique de la stratégie gagnante au gomoku libre et le processus de sa découverte :

I. Quelle est la stratégie gagnante au gomoku ?

La stratégie gagnante au gomoku ne consiste pas à mémoriser une « séquence de coups » fixe, car l'adversaire a des milliers de possibilités de défense. La stratégie gagnante est essentiellement un système tactique qui utilise l'« initiative absolue » pour presser continuellement l'adversaire, jusqu'à créer des menaces multiples (impossibles à défendre simultanément).

Plus précisément, la stratégie gagnante de Noir repose sur les éléments clés suivants :

1. Choix de l'ouverture :
   Sur un plateau 15×15, Noir joue son premier coup au tengen (centre). Si, après la défense de Blanc au deuxième coup, Noir choisit certaines formations spécifiques pour son troisième coup (comme les ouvertures « Hana-getsu » ou « Ura-getsu »), alors Noir peut garantir la victoire.
2. Tactiques clés : VCT et VCF
   • VCF (Victory by Continuous Four - Victoire par quatre consécutifs) : Chaque coup de Noir est un « quatre » (Blanc doit immédiatement le bloquer). Dans ce processus continu de création de quatre, les pions de Noir se connectent imperceptiblement, aboutissant finalement à un coup fatal (par exemple, un quatre-trois).
   • VCT (Victory by Continuous Threats - Victoire par menaces continues) : Chaque coup de Noir est un « trois vivant » ou un « quatre », forçant Blanc à se défendre passivement sans pouvoir contre-attaquer.
3. Créer des points de croisement (préparer le coup fatal) :
   Grâce aux attaques continues ci-dessus, Noir vise finalement à créer sur le plateau une situation de « double trois », « double quatre » ou « quatre-trois ». Comme Blanc ne peut défendre qu'un seul point à la fois, face à des menaces multiples, il sera inévitablement en retard, et Noir gagne.

II. Comment cette stratégie gagnante a-t-elle été découverte et prouvée ?

1. Accumulation d'expérience et d'intuition (phase humaine ancienne)

Pendant des siècles, les maîtres du gomoku ont constaté dans la pratique que l'avantage du premier joueur était énorme. À la fin du 19e siècle, les Japonais avaient déjà clairement conscience que, sans restrictions, un joueur Noir de haut niveau était presque imbattable. Ils ont donc progressivement développé les règles du « renju » avec des coups interdits. Mais à cette époque, la victoire du premier joueur n'était qu'un « consensus empirique », sans preuve par calcul rigoureux.

2. Preuve mathématique d'existence : le vol de stratégie (Strategy-Stealing)

Les mathématiciens peuvent utiliser une preuve logique appelée « vol de stratégie » pour démontrer que le premier joueur gagne au gomoku sans interdictions.
La logique est simple : supposons que le second joueur (Blanc) ait une méthode gagnante. Alors Noir joue n'importe où au premier coup, puis fait comme s'il était Blanc (considérant le pion noir déjà placé comme inexistant ou comme un coup supplémentaire) et adopte la méthode gagnante de Blanc. Comme au gomoku, avoir un pion supplémentaire sur le plateau n'est jamais un désavantage, mais toujours un avantage. Par conséquent, Noir peut gagner. Ceci contredit notre hypothèse que « le second joueur gagne ».
Par conséquent, le gomoku sans interdictions est soit un match nul, soit une victoire du premier joueur. Comme il est extrêmement difficile de remplir le plateau de gomoku pour faire match nul, la conclusion penche vers la victoire du premier joueur. Mais ce n'est qu'une théorie, elle ne donne pas de coups spécifiques.

3. Résolution informatique exhaustive (1992, L. Victor Allis)

Le véritable « terminateur » de la stratégie gagnante au gomoku est l'informaticien néerlandais L. Victor Allis.

En 1992, lors de la rédaction de sa thèse de doctorat, il a écrit un programme informatique nommé Victoria.

• Sa méthode : L'arbre de jeu du gomoku est extrêmement vaste, une recherche exhaustive traditionnelle (comme pour le morpion) était impossible à l'époque. Allis a intelligemment intégré la connaissance humaine du gomoku (les tactiques VCF, VCT et les algorithmes de recherche de doubles menaces mentionnés ci-dessus) dans le système, inventant un algorithme basé sur la « recherche par nombre de preuves (Proof-number search) ».
• Son résultat : Le programme a réussi à énumérer et calculer exhaustivement chaque branche clé du gomoku libre sur un plateau 15×15, prouvant pour la première fois dans l'histoire humaine, non seulement que Noir gagne, mais aussi en calculant le chemin gagnant spécifique. Il a également prouvé que, même avec certaines restrictions d'ouverture spécifiques, certaines ouvertures restent gagnantes pour Noir.

Résumé :
La victoire du premier joueur au gomoku, consensus empirique des joueurs humains depuis des millénaires, a finalement été résolue de manière exhaustive en 1992 par un informaticien grâce à un algorithme spécialisé. Le gomoku libre est donc considéré en informatique comme un « jeu faiblement résolu (Weakly Solved Game) » — c'est-à-dire que tant que Noir ne commet pas d'erreur, quelle que soit la défense de Blanc, Noir a un chemin de coups assurant la victoire.

Avant de présenter quels autres jeux ont été résolus, faisons un petit rappel des trois niveaux de définition de la « résolution » (Solved) en informatique, ce qui aidera à mieux comprendre :

1. Résolution ultra-faible (Ultra-weakly solved) : Prouve mathématiquement qui gagne (ou fait match nul), mais ne donne pas les coups spécifiques. (Exemple : le « vol de stratégie » mentionné dans la réponse précédente).
2. Résolution faible (Weakly solved) : L'ordinateur a trouvé une ligne de jeu spécifique gagnante (ou faisant match nul) à partir de la position initiale du jeu. En suivant cette ligne, on ne peut pas perdre, mais si l'on place les pions dans une position étrange, l'ordinateur pourrait ne pas connaître la solution optimale.
3. Résolution forte (Strongly solved) : Quelle que soit la position légale sur le plateau, l'ordinateur connaît la solution optimale absolue. (Exemple : le morpion).

Voici quelques jeux célèbres qui ont été faiblement résolus (voire fortement résolus), ainsi que des jeux qui ne le sont toujours pas.

---

I. Jeux célèbres qui ont été « résolus »

Outre le gomoku libre, d'autres jeux de plateau célèbres ont été complètement percés à jour par l'ordinateur :

1. Puissance 4 (Connect Four)

• Résultat : Le premier joueur gagne (faiblement résolu).
• Processus : C'est le même informaticien qui a résolu le gomoku, L. Victor Allis, qui a résolu Puissance 4 en 1988 (presque simultanément et indépendamment avec un autre mathématicien, James Dow Allen). Si le premier joueur place son premier pion dans la colonne centrale et adopte une stratégie parfaite, il gagne. Si le premier pion est placé dans une colonne adjacente au centre, c'est match nul ; s'il est placé sur le bord, le second joueur gagne.

2. Dames (Checkers / Draughts)

• Résultat : Match nul avec un jeu parfait (faiblement résolu).
• Processus : Ce fut une étape majeure retentissante. Le professeur Jonathan Schaeffer de l'Université de l'Alberta (Canada) a dirigé une équipe qui a développé le programme Chinook. Ils ont calculé pendant 18 ans (de 1989 à 2007), énumérant $5 \times 10^{20}$ (500 milliards de milliards) de positions de fin de partie, pour finalement annoncer en 2007 dans la revue Science que les dames étaient complètement résolues. Si les deux joueurs ne commettent pas d'erreur, le résultat est forcément un match nul.

3. Jeu du moulin (Nine Men's Morris)

• Résultat : Match nul avec un jeu parfait (fortement résolu).
• Processus : Ce jeu ancien (que l'on voit dans certains films classiques occidentaux) a été fortement résolu en 1993 par Ralph Gasser. Il a prouvé que, que ce soit en ouverture ou à n'importe quelle phase de milieu de partie, si les deux joueurs ne commettent pas d'erreur, le résultat est forcément un match nul.

4. Othello / Reversi — Une percée récente !

• Résultat : Match nul avec un jeu parfait (faiblement résolu).
• Processus : C'est une percée très récente ! En octobre 2023, le chercheur japonais Hiroki Takizawa, utilisant la puissance de calcul de superordinateurs modernes et des algorithmes optimisés, a officiellement annoncé après plusieurs jours de calcul que l'Othello standard sur plateau 8×8 était faiblement résolu. La conclusion est que, si les deux joueurs adoptent une stratégie parfaite, le score final est un match nul direct.

---

II. Jeux qui n'ont « pas été résolus » à ce jour

Vous pourriez demander : puisque l'IA est si forte (comme AlphaGo), tous les jeux de plateau ne sont-ils pas résolus ?
La réponse est non.

« L'IA bat les humains » et « résoudre mathématiquement un jeu » sont des concepts complètement différents. L'IA bat les humains parce qu'elle peut, par calcul probabiliste, trouver de très bons coups avec un taux de victoire de 99 % ; alors que la « résolution » exige une énumération exhaustive à 100 % et une preuve sans aucun doute.

Parce que la « complexité de l'espace d'états » (nombre de positions possibles) et la « complexité de l'arbre de jeu » (nombre de branches de tous les coups possibles) de ces jeux sont tout simplement trop grandes, dépassant de loin la puissance de calcul totale de tous les superordinateurs existants, et même celle des siècles à venir.

1. Échecs (Chess)

• Pourquoi non résolu : Le nombre de positions légales aux échecs est d'environ $10^{43}$, et le nombre de parties possibles est estimé à $10^{120}$ (ce nombre est appelé le « nombre de Shannon »). Le nombre total d'atomes dans l'univers observable n'est que d'environ $10^{80}$. Même en transformant tous les atomes de l'univers en ordinateurs, on ne pourrait pas calculer toutes les variations des échecs.
• État actuel : Bien que Deep Blue et les moteurs actuels comme Stockfish écrasent tous les maîtres humains, les échecs sont mathématiquement encore inconnus. Nous ne savons pas si une partie d'échecs parfaite est une victoire pour les Blancs (premier joueur) ou un match nul (la plupart des experts penchent pour le match nul).

2. Xiangqi (Échecs chinois)

• Pourquoi non résolu : Le plateau du Xiangqi est plus grand, offrant plus d'espace de manœuvre. Sa complexité d'espace d'états est d'environ $10^{48}$, soit plusieurs ordres de grandeur de plus que les échecs internationaux.
• État actuel : Similaire aux échecs, les logiciels de Xiangqi de premier plan (comme Wang Zhong Wang, Pi Ka Yu, etc.) laissent les humains sans aucune chance, mais au sens mathématique rigoureux, il n'est toujours pas résolu.

3. Go

• Pourquoi non résolu : Le Go est le « roi de la complexité » des jeux de plateau. Sur le plateau standard 19×19, la complexité de l'espace d'états atteint le chiffre stupéfiant de $10^{170}$, et la complexité de l'arbre de jeu atteint $10^{360}$. Face au Go, la complexité des échecs internationaux est négligeable.
• État actuel : Même l'arrivée fracassante d'AlphaGo et de son successeur AlphaZero n'a pas « résolu » le Go. Ils utilisent des réseaux de neurones pour établir une « évaluation intuitive » extrêmement puissante, sachant quel coup offre la meilleure probabilité de gagner dans la grande majorité des positions. Mais si l'on demandait à AlphaGo de prouver « si au Go, le premier joueur gagne ou s'il y a match nul », il en serait incapable.

Résumé

• Si la complexité d'un jeu est inférieure à $10^{20}$ (1000 milliards de milliards), comme les dames, le gomoku, l'Othello, les humains peuvent utiliser des superordinateurs pour le « résoudre » complètement.
• Une fois que la complexité dépasse $10^{40}$ (c'est-à-dire les échecs internationaux, le Xiangqi, le Go), la résolution exhaustive devient physiquement impossible. Pour ces jeux, nous ne pouvons utiliser l'IA que pour nous approcher infiniment de cette « vérité parfaite », mais nous ne pourrons peut-être jamais l'atteindre complètement.

Cette question est très perspicace ! Votre logique est tout à fait correcte : étendre le plateau à l'infini rend effectivement le nombre de situations infini, et il est absolument impossible pour un ordinateur de « tout énumérer ».

Cependant, le gomoku libre sur un plateau infini est toujours « résolu » mathématiquement et logiquement, et la conclusion reste la même : le premier joueur (Noir) gagne.

Puisqu'il est impossible de tout énumérer, comment a-t-il été résolu ? On utilise ici une logique de « réduction de dimension » très simple mais aussi très imparable :

1. Stratégie du « cercle magique » (preuve par emboîtement)

En 1992, l'ordinateur avait déjà prouvé de manière exhaustive que, sur un plateau limité de 15×15, Noir a une ligne de jeu gagnante.

Alors, comment Noir peut-il gagner sur un plateau infini ?
C'est simple : Noir n'a qu'à tracer un carré invisible de 15×15 au centre du plateau infini, puis suivre exactement la méthode gagnante du plateau 15×15.

Tant que Blanc joue à l'intérieur de ce carré, Noir répond selon le programme gagnant connu ; si Blanc joue à des milliers de kilomètres dans l'espace infini, Noir l'ignore complètement et se contente de faire un alignement de cinq pions dans sa zone 15×15. Parce que la méthode gagnante au gomoku est une « pression constante (création continue de quatre et de trois vivants) », Blanc n'a tout simplement pas de tour libre pour aller s'amuser ailleurs ; il doit rester sur le champ de bataille principal pour défendre.

2. Plus le plateau est grand, plus c'est avantageux pour le premier joueur

Au gomoku, la « bordure du plateau » aide en fait le camp perdant (Blanc) à défendre.
Quand Noir attaque, sa plus grande crainte est de « buter contre le mur » alors qu'il est en train de former un alignement, ne pouvant pas atteindre cinq pions.
Puisque Noir, dans un espace restreint de 15×15 où il est facile de buter contre le mur, parvient déjà à gagner à 100 %, alors sur un plateau infini, n'ayant plus à craindre de buter contre le mur, il gagnera encore plus facilement.

Résumé :
Le gomoku infini n'a pas été résolu par une puissance de calcul informatique infinie, mais par un raisonnement mathématique logique emboîté de la part des humains. Tant que l'on peut gagner sur un plateau 15×15, alors sur tout plateau de taille supérieure (même infini), le premier joueur gagnera nécessairement.