LA RÈGLE DU GO QUI CHANGE LA RÉPONSE

Résoudre un jeu, c’est connaître son issue quand les deux camps jouent parfaitement. Au go, cette issue est une valeur : le nombre de points d’avance de Noir quand les deux camps jouent parfaitement — 28 sur un plateau 4×7 veut dire que Noir possède les 28 intersections. Les dames ont été résolues en 2007, le Hex aussi sur de petits plateaux. Pour le go, des preuves par ordinateur existent pour de nombreux plateaux jusqu’à 30 intersections, surtout grâce à un programme nommé MIGOS (2003 et 2009).

Il y a un piège. Ces résultats classiques utilisent une règle simplifiée pour les positions répétées — une règle de « ko » de base — on ne peut pas reprendre aussitôt une pierre isolée qui vient d’en capturer une, ce qui ferait tourner les deux mêmes coups en boucle —, plus des conventions spéciales : une passe lève l’interdiction de ko, une partie s’arrête sur une position répétée, etc. Ces conventions servaient à ce que la valeur d’une position ne dépende pas du chemin pour y arriver.

La règle qu’on joue vraiment

Les règles chinoises telles qu’écrites, et le go par ordinateur, utilisent le superko positionnel : aucun coup ne peut recréer une position du plateau entier déjà apparue dans la partie. Résoudre sous cette règle est bien plus dur, car la légalité d’un coup dépend désormais de toute l’histoire de la partie. Trois outils qui rendent la résolution possible s’effondrent :

• réutiliser les résultats d’une même position atteinte par un autre chemin — les deux chemins peuvent interdire des coups différents ;
• reconnaître sans calcul les groupes sûrs et le territoire, ce qui suppose que le propriétaire peut toujours capturer les intrus — sous superko, cette capture peut être interdite ;
• élaguer les coups qui ne servent jamais, comme remplir son propre œil — l’une des cases vides dont un groupe a besoin pour rester en vie — : sous superko, un tel coup peut devenir décisif.

Le coût était énorme : avec une variante du superko, MIGOS mettait 1,1 heure pour le plateau 4×4, contre 3,3 secondes en ko simple. La première résolution du 5×5 sous superko, en 2024, a pris 5,25 heures sur six processus. Au-delà du 5×5, aucun plateau d’au moins deux rangées n’avait été résolu sous superko.

Un raccourci qui reste juste

Sami Kharma et Florian Schintke, de l’institut Zuse de Berlin, ont construit Sanko. Son cœur est un théorème de transfert de preuve simple : une preuve stockée qu’un joueur gagne reste valable sur un nouveau chemin sauf si une position que le gagnant doit créer est déjà apparue. Seules les positions du gagnant comptent — si le perdant ne peut plus recréer une position, il perd juste une option. Le vérifier prend un temps proportionnel à la longueur du chemin, pas à la taille de la preuve. Sur le plateau 3×7, ce seul raccourci fait passer le travail de 664 milliards d’étapes à 112 millions.

Ils ont aussi adapté la reconnaissance classique des groupes sûrs pour qu’elle reste correcte sous superko, et n’élaguent que du côté qu’on cherche à prouver gagnant : une recherche ratée est déclarée « inconnue », jamais comme une victoire de l’autre camp.

De nouvelles valeurs

• Le 5×5 en 15,7 minutes sur six fils de calcul — environ 20 fois plus vite qu’avant, en partie grâce à un meilleur matériel ; sur un seul fil, le 4×4 est résolu 58 fois plus vite. Sur une machine à 192 fils, le 5×5 prend environ une minute et demie.
• Les premières valeurs sous superko de 23 plateaux de plus ; 11 n’avaient jamais été résolus sous aucune règle. Le 3×10 vaut 8 points pour Noir — MIGOS n’avait prouvé qu’« au moins 6 », et deux mois de recherche n’avaient trouvé aucune borne supérieure.
• Sur les plateaux d’une seule rangée, les valeurs de 1×9 à 1×15 se répètent 0, 1, 2, 2 — mais le 1×16 casse le motif : il vaut 1 et non 2.

La surprise du 4×7

Avec les anciennes règles, le 4×7 est une victoire totale : Noir capture tout, 28 à 0. Sous superko, il vaut 12. Les auteurs ont rejoué la ligne optimale de 31 coups publiée pour MIGOS : chaque coup est légal, et Noir prend encore tout le plateau. En résolvant la ligne à rebours, ils ont trouvé la cassure juste après le coup 25 : dans la position laissée par le coup 25, joué par Noir, Blanc doit jouer G2 (ou C1) au lieu de A2.

S’ensuit un ko étrange. Blanc capture ; la reprise de Noir recréerait une position antérieure — interdit. Tout autre coup de Noir met son propre groupe en danger. Noir doit passer, Blanc passe, et la partie s’arrête avec le groupe blanc vivant : ce que les auteurs de MIGOS appelaient déjà la « vie au clair de lune ». Avec les anciennes règles, la passe lèverait l’interdiction et Noir reprendrait pour tout gagner. Sous superko, le mieux pour Noir dans cette ligne est une vie partagée (seki) qui ne rapporte que 3 points : le jeu parfait quitte donc la ligne publiée plus tôt, et le mieux que Noir puisse garantir depuis le plateau vide est 12.

Aucune des deux recherches n’avait tort. L’écart vient de règles qui ne comptent qu’à la toute fin d’une partie. Le conseil des auteurs : les valeurs calculées sous des conventions qui rendent la répétition inoffensive ne doivent pas être citées comme valeurs du go sous superko sans vérification.

Vérifiable par tous

Chaque valeur repose sur deux preuves indépendantes, et le solveur a passé des dizaines de milliers de contrôles croisés sans un seul désaccord. Contrairement aux résolutions antérieures de plateaux de go vides, le code source et la commande exacte derrière chaque résultat sont publics ; la chaîne de preuves du 4×7 se rejoue en moins de vingt secondes. Les preuves ne sont pas encore des certificats qu’un tiers puisse vérifier seul, et le 6×6 reste hors de portée — selon l’extrapolation des auteurs, environ 50 jours sur une de leurs machines, voire plus.