Le Gomoku est-il résolu ?
Ce que veut dire « résolu »
Un jeu est résolu quand on connaît son issue si les deux joueurs ne commettent aucune erreur. Le morpion est résolu : c'est une partie nulle. Le Puissance 4 l'est aussi : celui qui commence gagne. Les échecs et le jeu de Go ne le sont pas.
Pour le Gomoku, la démonstration fournit une stratégie gagnante depuis le plateau vide : à chaque réponse possible des blancs correspond un coup noir qui mène au gain. Elle ne dit pas ce que vaut n'importe quelle position prise au hasard ; les spécialistes parlent de résolution « faible ».
La démonstration de 1993
Elle est décrite dans l'article « Go-Moku and Threat-Space Search », signé par L. V. Allis et H. J. van den Herik (université du Limbourg, à Maastricht) et M. P. H. Huntjens (Vrije Universiteit, à Amsterdam), puis reprise dans la thèse de doctorat d'Allis, soutenue en 1994. Voici ce qu'on y lit.
- Le soupçon était ancien. Les auteurs rappellent que les joueurs professionnels japonais affirmaient depuis des décennies que les noirs gagnent, sans que personne l'ait prouvé.
- Deux règles ont été résolues : celle où une ligne de six pierres ou plus gagne, et celle où il faut exactement cinq pierres. Dans les deux cas, un arbre de gain complet pour les noirs a été construit et vérifié.
- Le programme s'appelle Victoria. Il combine deux techniques de recherche mises au point pour l'occasion.
- La ligne de jeu la plus longue dure 35 coups, en comptant ceux des deux joueurs : face à la meilleure défense, les noirs alignent cinq pierres à leur dix-huitième pierre au plus tard.
- Les moyens : dix stations de travail tournant la nuit, environ 5 millions de positions examinées pour la première règle et 6 millions pour la seconde. L'arbre de gain final compte un peu moins de 140 000 positions pour l'une, un peu plus de 150 000 pour l'autre.
Victoria a aussi joué en public : en août 1992, à Londres, le programme a remporté le tournoi de Gomoku de la quatrième Olympiade des ordinateurs en gagnant toutes ses parties jouées avec les noirs.
L'idée qui a rendu le calcul possible
Le Gomoku est trop vaste pour être exploré coup par coup : la thèse d'Allis estime le nombre de positions à environ 10105 et le nombre de parties possibles à environ 1070. Aucune machine n'énumère cela.
L'astuce consiste à ne regarder que les menaces. Quand les noirs font un quatre, les blancs n'ont qu'une réponse ; quand ils font un trois ouvert, deux ou trois. Une suite de menaces est donc une ligne presque droite dans l'arbre du jeu, que l'ordinateur suit très loin en très peu de calculs, jusqu'à trouver une double menace. C'est la « recherche dans l'espace des menaces », inspirée de la façon dont raisonnent les joueurs experts que les auteurs avaient observés. Une seconde technique, la recherche par nombres de preuve, choisit quelles positions examiner quand aucune suite de menaces ne gagne encore.
C'est exactement ce que tu fais à ton échelle quand tu cherches un 4-3 : les formes en question sont expliquées dans le guide Stratégie au Gomoku.
Ce que la preuve ne dit pas
- Elle porte sur le plateau de 15 lignes sur 15. Le plateau de 19 lignes sur 19, celui du jeu de Go, n'a pas fait l'objet de la même démonstration. Les auteurs citent des joueurs japonais pour qui un plateau plus grand avantage encore davantage les noirs.
- Elle ne vaut pas avec une règle d'ouverture. Dès que les premières pierres ne sont plus choisies librement par les noirs, il faut tout recalculer.
- Elle ne rend pas le jeu injouable. Personne ne retient un arbre de 140 000 positions. Entre humains, les noirs ont l'initiative, et une seule imprécision suffit à rendre la partie aux blancs.
Un raisonnement beaucoup plus simple, dit du vol de stratégie, montrait déjà que les blancs ne peuvent pas avoir de stratégie gagnante en Gomoku libre : si elle existait, les noirs poseraient une pierre quelconque puis l'appliqueraient à leur place, une pierre de plus ne pouvant pas nuire. Mais cet argument laisse ouverte la possibilité d'une partie nulle, et ne donne aucun coup à jouer. La démonstration de 1993, elle, donne les coups.
Le Renju n'est pas né de cette preuve
On lit souvent que le Renju et ses coups interdits auraient été inventés après la démonstration, pour sauver le jeu. C'est l'inverse. Les joueurs japonais avaient constaté l'avantage des noirs bien avant : le nom Renju est adopté en 1899, et les interdits faits aux noirs (double-trois, double-quatre, ligne de six pierres ou plus) se sont fixés dans les premières décennies du XXe siècle. L'article de 1993 décrit d'ailleurs le Renju comme une variante déjà existante, et note que les noirs semblent y garder l'avantage.
La suite lui a donné raison : en 2001, Wágner et Virág ont publié « Solving Renju », qui établit que les noirs gagnent aussi au Renju quand aucune règle d'ouverture ne s'applique.
La réponse de la compétition : Swap2
Si une couleur gagne, la seule façon de rendre la partie équitable est d'empêcher un joueur de choisir à la fois la position et la couleur. Depuis 2009, les championnats du monde de Gomoku utilisent l'ouverture Swap2 : le premier joueur pose trois pierres (noire, blanche, noire), le second choisit sa couleur ou pose deux pierres de plus et rend le choix. Le détail est dans le guide des variantes du Gomoku.
Sur ce site, le Gomoku libre reste la règle par défaut, parce qu'elle s'apprend en une phrase. Contre l'ordinateur, tu choisis qui commence, et celui qui commence prend les noirs : laisse-lui la main de temps en temps, tu verras ce que vaut l'initiative. À deux, sur le même écran ou en ligne, la règle de compétition (Swap2 et exactement cinq pierres) est proposée.
Et les ordinateurs d'aujourd'hui ?
Résoudre un jeu et bien y jouer sont deux choses différentes. Les programmes de Gomoku continuent de s'affronter, notamment au tournoi Gomocup, organisé chaque année depuis 2000. Sur le plan théorique, on sait depuis 1980, par un résultat de Stefan Reisch, que le Gomoku généralisé à un plateau de taille quelconque appartient à une classe de problèmes réputés très difficiles (il est « PSPACE-complet ») : il n'existe sans doute pas de raccourci général, seulement des résolutions plateau par plateau.
Questions fréquentes
Sources
- L. V. Allis, H. J. van den Herik et M. P. H. Huntjens, « Go-Moku and Threat-Space Search », 1993 : texte de l'article (PDF, en anglais).
- L. V. Allis, Searching for Solutions in Games and Artificial Intelligence, thèse de doctorat, université du Limbourg, 1994 (estimations du nombre de positions et de parties).
- J. Wágner et I. Virág, « Solving Renju », ICGA Journal, 2001.
- S. Reisch, « Gobang ist PSPACE-vollständig », Acta Informatica, 1980.
- Wikipédia en anglais, articles Gomoku, Renju et Game complexity (Swap2 depuis 2009, Gomocup, date du nom Renju).