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.
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).
| Plateau | Dispositions (3n²) | Positions légales | Part légale |
|---|---|---|---|
| 1 × 1 | 3 | 1 | 33,3 % |
| 2 × 2 | 81 | 57 | 70,4 % |
| 3 × 3 | 19 683 | 12 675 | 64,4 % |
| 4 × 4 | 43 046 721 | 24 318 165 | 56,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.
| Goban | Points | Dispositions (3n²) | Positions légales | Part légale |
|---|---|---|---|---|
| 9 × 9 | 81 | 4,43 × 1038 | 1,04 × 1038 (39 chiffres) | 23,4 % |
| 13 × 13 | 169 | 4,30 × 1080 | 3,72 × 1079 (80 chiffres) | 8,7 % |
| 19 × 19 | 361 | 1,74 × 10172 | 2,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 :
- le 19 × 19 compte environ 2 × 1090 fois plus de positions légales que 1080 ; aucune incertitude sur l'astronomie ne comble un tel écart ;
- le 13 × 13, avec 3,72 × 1079 positions, tombe déjà dans la fourchette des estimations : selon celle qu'on retient, il a plus ou moins de positions qu'il n'y a d'atomes ;
- le 9 × 9, avec 1038 positions environ, en est très loin.
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.
- 1980, David Lichtenstein et Michael Sipser montrent dans le Journal of the ACM que le go est PSPACE-difficile : il est au moins aussi dur que toute une famille de problèmes réputés hors de portée des méthodes rapides. Leur construction n'a pas besoin du ko.
- 1983, J. M. Robson montre que, si la seule répétition interdite est celle du ko simple, le go est EXPTIME-complet. Le temps nécessaire pour décider qui gagne croît alors, dans le pire des cas, de façon exponentielle avec la taille du goban, et c'est un résultat démontré, pas une conjecture. Le ko est ici essentiel : sans interdiction plus large, des cycles de captures peuvent faire durer une partie indéfiniment.
- Avec une règle de superko, qui interdit de reproduire une position déjà vue, la question est ouverte : on sait seulement que le go est PSPACE-difficile et qu'il se résout avec une mémoire exponentielle (classe EXPSPACE).
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
- Le nombre de positions légales du 19 × 19 s'écrit avec 171 chiffres, environ 2,08 × 10170 ; il a été calculé exactement par John Tromp et annoncé en janvier 2016. Seulement 1,2 % des dispositions de pierres sont légales.
- « Plus que d'atomes dans l'univers » est vrai de très loin pour le 19 × 19 ; le 13 × 13 tombe déjà dans la fourchette des estimations.
- Le go généralisé est PSPACE-difficile (1980), EXPTIME-complet avec le seul ko simple (1983) ; avec un superko, son classement reste une question ouverte.
- Les fins de partie très tardives se calculent avec la théorie des jeux combinatoires de Berlekamp et Wolfe, au point, selon un collègue de Berlekamp, de lui permettre de battre un grand joueur japonais sur des positions choisies.
Sources
- John Tromp et Gunnar Farnebäck, « Combinatorics of Go », version révisée du 31 janvier 2016 (historique des calculs, table des valeurs exactes) : tromp.github.io/go/gostate.pdf
- John Tromp, « Number of legal Go positions » (définition, valeurs, dates du calcul du 19 × 19) : tromp.github.io/go/legal.html
- OEIS, suite A094777, « Number of legal positions in Go played on an n X n grid » : oeis.org/A094777
- Wikipédia (anglais), « Observable universe », section sur le nombre d'atomes : en.wikipedia.org/wiki/Observable_universe
- Universe Today, « How Many Atoms Are There in the Universe? » (fourchette de 1078 à 1082) : universetoday.com
- Erik van der Werf, AI techniques for the game of Go, thèse, université de Maastricht, 2005, tableau 5.1 : maastrichtuniversity.nl
- David Lichtenstein et Michael Sipser, « GO Is Polynomial-Space Hard », Journal of the ACM, vol. 27, n° 2, 1980, p. 393-401 : doi.org/10.1145/322186.322201
- J. M. Robson, « The complexity of Go », Proceedings of the IFIP 9th World Computer Congress, 1983, p. 413-417 (cité par les deux sources suivantes)
- Erik Demaine et Robert Hearn, « Playing Games with Algorithms: Algorithmic Combinatorial Game Theory » (état des résultats sur le go, le ko et le superko) : arxiv.org/abs/cs/0106019
- Wikipédia (anglais), « Go and mathematics » et « Combinatorial game theory » : Go and mathematics, Combinatorial game theory
- Elwyn Berlekamp et David Wolfe, Mathematical Go: Chilling Gets the Last Point, A K Peters, 1994 ; présentation et table des matières : math.berkeley.edu, uni-bielefeld.de
- Robert Sanders, « Elwyn Berlekamp, game theorist and coding pioneer, dies at 78 », Berkeley News, 18 avril 2019 : news.berkeley.edu
- David Eisenbud, hommage à Elwyn Berlekamp, MSRI (SLMath) : slmath.org
- David Wolfe, « Go Endgames Are PSPACE-Hard », dans More Games of No Chance, MSRI Publications 42, 2002, p. 125-136 : library.slmath.org