Le Gomoku et les mathématiques : pourquoi 5 pierres alignées fascinent les chercheurs en IA
Le Gomoku semble simple : deux joueurs posent alternativement des pierres sur un plateau, et le premier à en aligner cinq gagne. Pourtant, derrière cette règle élémentaire se cache un problème mathématique d’une complexité vertigineuse qui fascine les chercheurs en intelligence artificielle depuis des décennies. Comme le présente notre article sur les stratégies gagnantes au Gomoku, la maîtrise humaine du jeu repose sur l’intuition et l’expérience. Mais que se passe-t-il quand les machines s’en mêlent ?
Le Gomoku comme problème mathématique
En théorie de la complexité, les jeux de plateau sont classés selon la difficulté qu’ils représentent pour un ordinateur. Le Gomoku généralisé (sur un plateau de taille arbitraire n×n) appartient à la classe PSPACE-complet - l’une des classes de problèmes les plus difficiles connues. Cela signifie que déterminer le gagnant d’une position donnée nécessite, dans le pire des cas, une quantité de mémoire qui croît de manière polynomiale avec la taille du plateau.
Pour mettre cela en perspective, le morpion (3×3) a environ 255 168 parties possibles. Le Gomoku sur un plateau standard 15×15 a un nombre de parties estimé à plus de 1070 - un nombre qui dépasse le nombre d’atomes dans l’univers observable. Même les ordinateurs les plus puissants ne peuvent pas explorer toutes ces possibilités par force brute.
C’est cette explosion combinatoire qui rend le Gomoku si intéressant pour les chercheurs. Le jeu est suffisamment simple pour être compris par un enfant, mais suffisamment complexe pour résister à la puissance de calcul brute. C’est le terrain de jeu idéal pour développer et tester des algorithmes intelligents.
La preuve que le premier joueur gagne
En 1994, le mathématicien Victor Allis a prouvé dans sa thèse de doctorat un résultat remarquable : sur un plateau 15×15, le premier joueur a une stratégie gagnante en Gomoku libre (sans restrictions). Autrement dit, si le premier joueur joue parfaitement, il gagne toujours, quel que soit le jeu du second joueur.
Cette preuve a été réalisée par une combinaison de recherche exhaustive et de bases de menaces (threat-space search). Allis a identifié des séquences de menaces - des positions où le premier joueur force une réponse de l’adversaire - qui mènent inévitablement à un alignement de cinq. Le programme a exploré des millions de positions, mais la preuve tient en une série de coups forcés que le second joueur ne peut pas contrer.
Ce résultat a eu un impact profond sur le monde du Gomoku compétitif. Il a confirmé ce que les joueurs experts soupçonnaient depuis longtemps : le Gomoku libre est déséquilibré en faveur du premier joueur. C’est pour cette raison que les variantes compétitives (comme le Renju) ajoutent des restrictions au premier joueur - interdiction du double-trois, du double-quatre, et de la surcharge - pour rétablir l’équilibre.
Les programmes d’IA qui jouent au Gomoku
Les approches classiques : minimax et alpha-bêta
Les premiers programmes de Gomoku, dans les années 1980-1990, utilisaient l’algorithme minimax avec élagage alpha-bêta. Le principe est simple : l’ordinateur explore l’arbre des coups possibles, en supposant que chaque joueur joue de manière optimale. L’élagage alpha-bêta permet de couper les branches de l’arbre qui ne peuvent pas mener à un meilleur résultat, réduisant considérablement le nombre de positions à évaluer.
La difficulté réside dans la fonction d’évaluation. Comment attribuer un score à une position où personne n’a encore gagné ? Les programmeurs ont développé des heuristiques sophistiquées : compter les alignements de 2, 3 et 4 pierres, évaluer les menaces ouvertes (non bloquées des deux côtés) par rapport aux menaces fermées, et pondérer la position centrale du plateau.
Ces programmes jouaient déjà à un niveau supérieur à la plupart des humains. Mais ils avaient une faiblesse : leur horizon de recherche était limité. Sur un plateau 15×15 avec 225 intersections, l’arbre des possibilités explose si rapidement que même l’élagage le plus agressif ne permet d’explorer que 10 à 15 coups d’avance.
La révolution du deep learning
L’arrivée des réseaux de neurones profonds a bouleversé le monde du Gomoku comme celui de tous les jeux de plateau. L’approche pionnière de DeepMind avec AlphaGo (2016) - combinant réseaux de neurones et recherche Monte-Carlo - a été rapidement adaptée au Gomoku.
Le principe est radicalement différent des approches classiques. Au lieu de programmer des heuristiques, on laisse l’IA apprendre par elle-même. Le réseau de neurones joue des millions de parties contre lui-même, ajustant ses paramètres à chaque victoire et chaque défaite. Au fil du temps, il développe une compréhension intuitive du jeu qui dépasse tout ce que les programmeurs auraient pu coder manuellement.
Les résultats sont spectaculaires. Les IA modernes de Gomoku détectent des menaces que même les meilleurs joueurs humains ne voient pas. Elles identifient des séquences gagnantes à 20 ou 30 coups d’avance, là où un humain peine à calculer au-delà de 5 ou 6 coups.
Les approches heuristiques : quand la perfection est inaccessible
Malgré les avancées de l’IA, le Gomoku sur grand plateau reste non résolu de manière complète. La preuve d’Allis concerne le 15×15, mais sur un plateau 19×19 (celui du Go), le problème est encore ouvert. Les chercheurs doivent donc recourir à des heuristiques - des méthodes qui ne garantissent pas la solution optimale mais produisent de très bons résultats en temps raisonnable.
La recherche dans l’espace des menaces (threat-space search) est l’heuristique la plus puissante au Gomoku. Au lieu d’explorer tous les coups possibles, elle se concentre uniquement sur les menaces - les coups qui créent un alignement de 4 ou une double menace de 3. Cette réduction de l’espace de recherche permet d’explorer beaucoup plus profondément les lignes tactiques pertinentes.
L’approche Monte-Carlo Tree Search (MCTS), rendue célèbre par AlphaGo, est également très efficace au Gomoku. Au lieu d’évaluer chaque position avec une fonction heuristique, MCTS simule des milliers de parties aléatoires à partir de la position actuelle et utilise les statistiques de victoire pour guider la recherche. C’est une approche probabiliste qui converge vers la solution optimale avec suffisamment de temps de calcul.
Pourquoi le Gomoku fascine encore les chercheurs
Le Gomoku n’est pas le jeu le plus médiatisé en IA - cet honneur revient aux échecs et au Go. Mais il occupe une place unique dans la recherche. Sa simplicité règlementaire permet d’isoler des problèmes algorithmiques purs, sans les complications liées aux règles spéciales (roque, prise en passant, ko). C’est un laboratoire idéal pour tester de nouvelles approches.
Le Gomoku pose également des questions fondamentales en théorie des jeux combinatoires. La preuve que le premier joueur gagne est un résultat existentiel - on sait qu’une stratégie gagnante existe, mais la reproduire en pratique nécessite une mémoire et un calcul considérables. Cet écart entre l’existence théorique et la faisabilité pratique est l’un des problèmes les plus fascinants de l’informatique.
Enfin, le Gomoku rappelle une vérité profonde : la complexité peut naître de règles extrêmement simples. Cinq pierres alignées sur un plateau - il n’y a rien de plus élémentaire. Et pourtant, cette règle génère un univers de possibilités qui défie les meilleurs esprits - humains et artificiels. C’est cette élégance qui continue de fasciner les mathématiciens et les chercheurs en IA, des décennies après les premières analyses.