← Retour au blog

Ce que les mathématiques disent du go : positions, complexité, fins de partie

On lit que le go compte « plus de positions que d'atomes dans l'univers ». La phrase est vraie, mais elle cache des questions plus intéressantes. Combien de positions exactement, et qui les a comptées ? Que veut dire, pour un mathématicien, qu'un jeu est « difficile » ? Et que peut la théorie quand il ne reste que quelques points à se disputer ? Voici ce qui est démontré, ce qui reste ouvert, et ce que nous avons recalculé nous-mêmes.

Jouer au go Les règles du go

Trois états par point, mais pas toutes les combinaisons

Chaque intersection du goban est vide, noire ou blanche. Sur un plateau de n lignes, cela donne au plus 3 puissance n² dispositions. Mais beaucoup ne peuvent pas apparaître dans une partie : une chaîne de pierres sans aucune liberté aurait été capturée. On appelle donc position légale une disposition où chaque chaîne de pierres touche au moins une intersection vide. C'est la définition retenue par John Tromp et Gunnar Farnebäck dans leur article « Combinatorics of Go », et elle a un avantage : elle ne dépend pas des règles choisies (françaises, japonaises ou chinoises), qui diffèrent sur le décompte et le ko, pas sur la capture.

Sur les tout petits plateaux, on peut tout passer en revue. Notre script énumère les 81 dispositions du 2 × 2, les 19 683 du 3 × 3 et les 43 046 721 du 4 × 4, et garde celles où chaque chaîne a une liberté. Il retrouve exactement les valeurs publiées par Tromp et Farnebäck, et recensées dans l'encyclopédie en ligne des suites d'entiers (OEIS, suite A094777).

PlateauDispositions (3n²)Positions légalesPart légale
1 × 13133,3 %
2 × 2815770,4 %
3 × 319 68312 67564,4 %
4 × 443 046 72124 318 16556,5 %

Sur 1 × 1, une pierre seule n'a aucune liberté : seule la case vide est légale. Ensuite, la part légale baisse quand le plateau grandit, car plus il y a de pierres, plus une chaîne a de chances d'être enfermée quelque part. Mais l'énumération brute ne va pas loin : le 4 × 4 prend déjà une vingtaine de secondes à notre script, et le 5 × 5 compte plus de 800 milliards de dispositions.

Le compte exact du 19 × 19 : vingt-quatre ans de travail

L'histoire de ce calcul est racontée dans l'article de Tromp et Farnebäck. En septembre 1992, une discussion du forum rec.games.go pose la question du nombre de positions légales. Achim Flammenkamp publie le premier une estimation par simulation, en tirant des dispositions au hasard : environ 1,2 % de 3361, soit à peu près 2,089 × 10170. L'estimation était bonne : elle ne s'écarte que de 0,35 % de la valeur exacte, connue vingt-quatre ans plus tard.

Pour compter exactement, il faut une méthode plus fine que l'énumération : la programmation dynamique, qui balaie le goban point par point en ne retenant que l'état de la « frontière » entre la partie déjà traitée et le reste. L'idée est discutée en ligne dès 2000 ; en janvier 2005, Farnebäck publie le premier programme sans erreur, qui donne les comptes jusqu'au 10 × 10. Tromp obtient le 13 × 13 en juin 2005, puis, avec l'aide de Michal Koucký pour contourner les limites de mémoire, les plateaux suivants : le 17 × 17 en août 2006, après plus de 8 000 heures de processeur sur une grappe de calcul d'Amsterdam. Le 18 × 18 attend 2014 et les machines de l'Institute for Advanced Study de Princeton. Le 19 × 19 est annoncé en janvier 2016. Le voici, en entier :

208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935

C'est un nombre de 171 chiffres, environ 2,08 × 10170. Il ne représente que 1,196 % des 3361 dispositions possibles : sur un grand goban, presque toutes les dispositions prises au hasard contiennent au moins une chaîne sans liberté.

Les trois gobans du site, en chiffres

Les valeurs exactes publiées par Tromp et Farnebäck permettent de comparer les trois tailles qu'on joue ici. Notre script recalcule les puissances de 3 et les rapports à partir de ces valeurs.

GobanPointsDispositions (3n²)Positions légalesPart légale
9 × 9814,43 × 10381,04 × 1038 (39 chiffres)23,4 %
13 × 131694,30 × 10803,72 × 1079 (80 chiffres)8,7 %
19 × 193611,74 × 101722,08 × 10170 (171 chiffres)1,2 %

Plus que d'atomes dans l'univers ? Oui, avec des précautions

Le nombre d'atomes de l'univers observable n'est pas mesuré : il est estimé, à partir de la masse de matière ordinaire et en supposant, pour simplifier, que tout est de l'hydrogène. On lit couramment des valeurs entre 1078 et 1082, souvent arrondies à 1080. La comparaison a donc une marge d'incertitude de plusieurs ordres de grandeur, mais elle tient largement :

Une précaution encore : le nombre de positions ne dit pas à lui seul si un jeu est difficile. Les mathématiques ont d'autres mesures.

Les petits plateaux résolus, le grand non

« Résoudre » un jeu, c'est connaître le résultat d'une partie parfaite des deux côtés. Pour le go, cela n'a été fait que sur de très petits gobans. Dans sa thèse soutenue à Maastricht en 2005, Erik van der Werf décrit son programme Migos, qui résout tous les gobans carrés vides jusqu'au 5 × 5. Sur le 3 × 3, Noir joue au centre et gagne de 9 points, c'est-à-dire tout le plateau ; sur le 5 × 5, il joue aussi au centre et gagne de 25 points, encore tout le plateau. Ces scores s'entendent sans komi. Sur 19 × 19, personne ne connaît le résultat d'une partie parfaite, même depuis que les programmes dépassent les meilleurs joueurs, comme le raconte notre article sur le coup 37 d'AlphaGo.

Difficile au sens de l'informatique théorique

Pour classer la difficulté d'un jeu, les informaticiens étudient le go « généralisé » : un goban de n × n, avec n aussi grand qu'on veut, et une position donnée. La question est : le joueur qui a le trait peut-il forcer la victoire ? On regarde alors comment le temps ou la mémoire nécessaires grandissent avec n. Ces résultats portent sur des positions construites exprès, pas sur le goban vide de 19 × 19.

Ce détail de règle, presque invisible dans une partie ordinaire, change donc le classement mathématique du jeu. C'est un des points où les règles diffèrent, comme l'explique le guide règles françaises, japonaises et chinoises.

Berlekamp et Wolfe : la théorie du dernier point

À la fin d'une partie de go, le plateau se découpe souvent en petites zones séparées par des frontières solides : un passage à fermer ici, une frontière à pousser là. Chaque zone est un petit jeu, et la partie entière est leur somme. C'est exactement le cadre de la théorie des jeux combinatoires, développée notamment par Elwyn Berlekamp, John Conway et Richard Guy, qui sait donner une valeur à chaque petit jeu et additionner ces valeurs. Selon l'article de Wikipédia consacré à cette théorie, l'observation des fins de partie de go a d'ailleurs inspiré l'étude des jeux où les deux camps n'ont pas les mêmes coups.

En 1994, Berlekamp et David Wolfe publient Mathematical Go: Chilling Gets the Last Point. Leur outil central est le « chilling », le refroidissement : on fait comme si chaque coup coûtait un point à celui qui le joue. Les valeurs de go deviennent alors des objets bien connus de la théorie : des nombres, mais aussi des quantités plus petites que tout nombre positif, les « infinitésimaux », qui décident pourtant du dernier point. Le livre ne prétend pas analyser une partie entière, seulement ces fins de partie très tardives, où il permet de trouver l'ordre exact des coups.

Une anecdote revient dans les hommages rendus à Berlekamp, mort en 2019. Elle vient du mathématicien David Eisenbud, son collègue : Berlekamp aurait installé des positions de fin de partie qu'il avait choisies et battu un grand joueur japonais sept fois de suite. La nécrologie publiée par l'université de Berkeley précise qu'il a gagné en jouant aussi bien Noir que Blanc ; l'hommage d'Eisenbud pour l'institut de recherche mathématique MSRI parle de sept victoires consécutives. Aucun des deux textes ne nomme le joueur, et nous n'avons trouvé ni date ni relevé de ces parties : c'est un témoignage, pas un fait vérifiable dans le détail. Le livre lui-même contient une section intitulée « 9-dan stumping problem », littéralement un problème qui « colle » un 9e dan.

La théorie a aussi ses limites. En 2002, Wolfe a démontré que la fin de partie de go, au sens précis d'une somme de zones séparées par des pierres vivantes, est elle-même PSPACE-difficile : quand on multiplie et qu'on agrandit ces zones, même la fin de partie devient aussi dure qu'on veut.

Et sur ce site ?

Le go du site se joue sur les trois tailles du tableau ci-dessus : 9 × 9, 13 × 13 et 19 × 19, aux règles françaises, japonaises ou chinoises. Les règles japonaises n'y interdisent que le ko simple (un cycle sans fin rend la partie « sans résultat ») ; les règles françaises et chinoises appliquent un superko. Tu retrouves donc ici les deux traitements de la répétition que les théoriciens distinguent. Le classement contre l'ordinateur a un onglet par taille de goban, et le problème du jour propose chaque jour un problème de vie et de mort dans un coin. Pour l'histoire du plateau lui-même, lis du goban 17 × 17 au 19 × 19 ; pour commencer petit, le guide Ouvertures sur 9 × 9.

Ce qu'il faut retenir

Sources

À lire aussi

← Retour au blog Jouer au go
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →