Au go, la règle anti-répétition ramène le 4×7 de 28 à 12 points

Sur un plateau de go de 4 lignes sur 7, Noir, qui joue le premier, peut s’emparer de toute la surface, soit 28 points : c’est le résultat calculé en 2008-2009 par le programme du chercheur Erik van der Werf. Mais ce calcul reposait sur une règle simplifiée. Avec la règle employée en Chine et couramment par les programmes de go, qui interdit de reproduire une position déjà vue dans la partie, Blanc sauve un groupe et Noir ne gagne plus que de 12 points. C’est l’un des résultats d’une prépublication déposée le 21 octobre sur arXiv, c’est-à-dire non encore relue par d’autres chercheurs, par Sami Kharma et Florian Schintke, du Zuse Institute Berlin, un institut de recherche en mathématiques appliquées et en calcul haute performance.

Leur programme, baptisé Sanko, donne aussi les premières valeurs exactes sous cette règle pour 23 petits plateaux, dont onze « qui n’avaient été résolus sous aucune règle ». Et il refait en 16 minutes un calcul qui en demandait plus de cinq heures.

Résoudre un jeu, c’est connaître le score parfait

Au go, deux joueurs posent à tour de rôle des pierres noires et blanches sur les intersections d’une grille. Une pierre ou un groupe de pierres encerclé sans aucune case libre adjacente est capturé et retiré. Dans le décompte retenu par les auteurs, chacun compte à la fin ses pierres et les zones vides entourées par les siennes seules.

« Résoudre » un plateau, au sens des chercheurs, ne veut pas dire jouer bien : c’est établir avec certitude le résultat d’une partie où les deux camps ne commettent aucune erreur. L’article définit la valeur d’un plateau comme « l’avance de Noir avec un jeu optimal ». Pour l’établir, Sanko produit deux preuves. Il ajoute d’abord des points au score de Blanc (c’est le komi, la compensation habituelle du second joueur) et démontre que Noir gagne malgré 11,5 points de handicap, puis que Blanc gagne avec 12,5. La valeur du 4×7 est donc exactement 12. Le demi-point empêche toute égalité.

Le procédé est celui qui a permis de résoudre d’autres jeux : les dames anglaises en 2007, le hex sur de petits plateaux, rappellent les auteurs. Au go, Erik van der Werf a ouvert la voie : son programme MIGOS a résolu le 5×5 en 2002, une victoire de Noir de 25 points, « tout le plateau appartient à Noir », en commençant au centre. Il a ensuite calculé, en 2008 et 2009, la plupart des rectangles jusqu’à 30 intersections.

Le ko, ou comment une partie peut tourner en rond

Ces résultats anciens utilisent la règle dite du ko simple. Le ko est une situation où chaque joueur pourrait reprendre indéfiniment une pierre que l’autre vient de lui prendre. La règle du ko simple interdit seulement de reprendre aussitôt, c’est-à-dire de recréer la position qui suivait son propre coup précédent. Les règles japonaises s’en contentent : un cycle plus long, comme le « triple ko », y laisse la partie sans résultat.

Le superko va plus loin. Dans sa forme dite positionnelle, la plus stricte, un coup ne peut pas recréer une position du plateau entier apparue n’importe quand auparavant dans la partie, quel que soit le joueur dont c’était le tour. C’est la règle chinoise ; les règles américaines et néo-zélandaises ne l’appliquent que si c’est au même joueur de jouer, précise l’article. Les programmes de go utilisent couramment la forme chinoise, par exemple dans les règles dites Tromp-Taylor.

Erik van der Werf l’écrivait lui-même en 2002 : son résultat sur le 5×5 « est indépendant de toute règle de superko », mais cela « ne signifie pas que le superko est sans importance », seulement qu’il existe depuis le plateau vide une suite de coups forcée qui évite les longs cycles. Le 5×5 vaut bien 25 points sous superko, Sanko le confirme. Le 4×7 montre que ce n’est pas toujours le cas.

Ce qui se passe sur le 4×7

Les auteurs ont rejoué, sous superko positionnel, la ligne de jeu parfait de 31 coups publiée par MIGOS en 2009. Après le 25^e coup de Noir, Blanc la réfute. Le nœud est une capture : sous superko, la reprise par Noir recréerait une position antérieure et devient interdite. Sous les règles de MIGOS, il suffisait de passer son tour une fois pour lever l’interdiction ; Noir reprenait alors la pierre, capturait le grand groupe blanc et gagnait tout. Sous superko, le mieux que Noir puisse obtenir est un seki, une situation où deux groupes adverses survivent côte à côte sans pouvoir se capturer l’un l’autre. Blanc garde ses pierres et l’avance de Noir, dans cette ligne, tombe à 3 points. En jouant autrement dès le début, Noir peut obtenir mieux : 12 points, la nouvelle valeur du plateau.

Pour les douze autres plateaux de l’étude dont la valeur en ko simple était connue, rien ne change ; le 3×10, pour lequel on savait seulement que Noir gagnait d’au moins 6 points, vaut 8. Dans la table des auteurs, le 4×7 est le seul plateau où la règle modifie le résultat.

Les 24 plateaux de la prépublication et leur valeur

Valeur = avance de Noir, qui joue le premier, avec un jeu parfait des deux côtés, en points. Le 5×5 avait déjà été résolu sous superko en 2024.

Plateau	Sous superko positionnel (Sanko, 2026)	Sous ko simple (MIGOS)
1×10	1	1
1×11	2	2
1×12	2	2
1×13	0	non résolu
1×14	1	non résolu
1×15	2	non résolu
1×16	1	non résolu
1×17	0	non résolu
1×18	1	non résolu
2×10	4	4
2×11	6	6
2×12	4	non résolu
2×13	6	non résolu
2×14	4	non résolu
2×15	6	non résolu
3×7	21	21
3×8	24	24
3×9	5	5
3×10	8	au moins 6
4×5	20	20
4×6	8	8
4×7	12	28
5×5	25	25
5×6	4	4

Source : table 2 de la prépublication ; valeurs en ko simple recoupées avec la table d’Erik van der Werf.

Pourquoi l’historique de la partie complique tout

Le superko n’est pas une nouveauté pour les solveurs de go, mais il les ralentit considérablement. Les auteurs rappellent qu’avec la variante américaine du superko, un solveur antérieur mettait 1,1 heure pour le 4×4 contre 3,3 secondes en ko simple. Le 5×5 sous superko positionnel n’a été résolu pour la première fois qu’en 2024, par Owen Randall, Martin Müller, Ting Han Wei et Ryan Hayward, avec un algorithme nommé Expected Work Search : 5,25 heures sur six processus. Sanko fait le même calcul en 16 minutes sur six fils d’exécution.

La difficulté tient à ce que la légalité d’un coup dépend désormais de toute la partie écoulée. Trois outils classiques des solveurs s’en trouvent faussés.

Le premier est la table de transposition, une mémoire où le programme range les positions déjà résolues pour ne pas les recalculer quand il y revient par un autre chemin ; c’est elle, écrivent les auteurs, qui rend les grandes preuves possibles. Sous superko, deux chemins menant à la même position n’ont pas le même passé : une reprise permise sur l’un est interdite sur l’autre, et la position n’a plus forcément la même valeur. Le résultat stocké devient suspect. La réponse de Sanko est un théorème dit de transfert : une preuve stockée reste valable sur un nouveau chemin, sauf si le camp qui gagne dans cette preuve doit recréer une position antérieure. Seules les positions produites par le gagnant peuvent invalider la preuve, et cinq petites informations attachées à chaque preuve suffisent à le vérifier.

Le deuxième est la reconnaissance immédiate des groupes définitivement vivants et des territoires acquis, inspirée de l’algorithme dit de Benson. Elle suppose que le propriétaire d’un territoire peut toujours capturer une pierre adverse qui s’y glisse ; sous superko, cette capture peut être interdite. Les auteurs en proposent une version plus exigeante, valable sous cette règle.

Le troisième est l’élagage, qui consiste à ne pas examiner des coups jugés inutiles, comme jouer dans son propre territoire déjà acquis ou boucher ses propres « yeux », les cases vides isolées à l’intérieur de ses groupes. Sanko ne retire ces coups que pour le camp dont il cherche à prouver la victoire : retirer des options au gagnant ne peut pas rendre sa victoire fausse. Si la preuve échoue, le résultat est déclaré inconnu, jamais attribué à l’adversaire.

Le programme, écrit en Rust, est publié sous licence libre Apache 2.0, avec la documentation complète des calculs. Les auteurs ont travaillé sur une seule machine équipée de deux processeurs AMD Epyc 9475F (192 fils d’exécution, 1,5 téraoctet de mémoire). La preuve en faveur de Noir sur le 4×7 a demandé 66 milliards d’étapes de calcul et 44 minutes ; celle du 2×15, 14,3 heures.

Le 19×19 reste hors de vue

Le plateau de compétition compte 19 lignes sur 19, soit 361 intersections. Les auteurs ne s’en approchent pas. Selon eux, la taille d’une preuve est multipliée par dix environ chaque fois qu’on ajoute deux ou trois intersections : le 6×6, avec 36 intersections, demanderait de l’ordre de cent mille milliards d’étapes ou davantage et reste « hors de portée sans avancée qualitative ». Au-delà de 30 intersections, écrivent-ils, il faut même allonger les « clés » qui identifient chaque position en mémoire, au-delà de 64 bits. La barre des 30 intersections est pourtant déjà franchie : depuis la mise en ligne de la prépublication, le dépôt du programme annonce, sans publication à l’appui, trois plateaux de 32 et 33 intersections résolus, sans valeur connue jusque-là sous aucune règle : le 4×8 (Noir gagne de 6 points), le 3×11 (9) et le 2×16 (4).

Les travaux qui citent le 7×7 portent sur un autre problème, le « Killall-Go », où Noir doit capturer toutes les pierres adverses, précise l’article. Et une réserve demeure sur les résultats eux-mêmes : les preuves de Sanko « ne sont pas des certificats vérifiables de l’extérieur ». Un tiers ne peut pas les contrôler sans refaire le calcul, puisque encoder une preuve qui dépend du chemin suivi reste, sous superko, un problème ouvert. Le code publié permet en revanche à d’autres équipes de relancer les calculs du 4×7 et des 23 autres plateaux.

Les citations, en anglais dans les sources, sont traduites par la rédaction.