Après 2500 ans, l’énigme du jeu de go est enfin résolue

Le jeu de go est un jeu très ancien originaire de Chine. Il fait intervenir deux joueurs qui, chacun leur tour, placent des pierres noires et blanches sur un plateau afin d'étendre leur « territoire » au maximum. Les plus anciennes références au jeu de go datent du 5e siècle avant JC ; en bref, des chinois jouaient sur les rives du Yangzi Jiang bien avant que le Parthénon n'étende son ombre sur la ville d'Athènes. À la fois simple et complexe, le jeu de go est connu pour sa grande richesse combinatoire ; certains joueurs n'hésitent pas à dire que le plateau de jeu standard (19x19) offre un nombre de combinaisons infini. Pourtant, comme l'informaticien John Tromp l'a révélé la semaine dernière, cette proposition n'est pas vraie. Il y a juste beaucoup, beaucoup de combinaisons possibles.

Plus précisément, il y aurait 20 816 819 938 197 998 469 947 863 334 486 277 028 652 245 388 453 054 842 563 945 682 092 741 961 273 8015 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 façons d'utiliser le plateau de 361 points avec les pierres blanches et noires. Difficile de trouver ça avec un crayon et un bout de papier. Comme un utilisateur de Reddit l'a fait remarquer, c'est plus que le nombre total d'atomes observables dans l'univers.

Tromp a commencé ses calculs en mars 2015, avec l'aide du personnel et des serveurs informatiques de l'Institut d'études avancées en sciences naturelles, du Centre pour la recherche sur les communications (dépendant de l'Institut d'analyses pour la Défense) à Princeton, New Jersey, avec en sus un coup de main du Helion Cloud de Hewlett-Packard.

« Le logiciel a été développé en 2005 ; depuis nous aurions pu faire les calculs, mais nous n'avions pas le hardware nécessaire, » explique Tromp. « En 2007, Michal Koucký et moi avons calculé le nombre de combinaisons possibles pour un plateau de 17x17, et cela a suffi à mettre à plat les calculateurs du Centre de Mathématiques et d'Informatique allemand où je travaillais. »

Vous voulez vérifier son travail ? Pas de problème. Tromp a mis son logiciel à disposition sur github, mais pour le faire tourner il faudra « un serveur de 15TB d'espace disque fast scratch, un processeur de 8 à 16 cœurs, et 192BG de RAM. »

Pendant des années, les limites du matériel à disposition l'ont empêché de résoudre le mystère de la combinatoire du jeu de go de 19x19 lignes. La question le tourmentait depuis 1992, quand il a appris à y jouer pour la première fois. On pourrait croire qu'il n'y a pas un saut important entre un jeu de 17x17 et un jeu de 19x19 ; pourtant, Tromp précise qu'à chaque agrandissement ( une ligne verticale et une ligne horizontale supplémentaires) de la taille du plateau, il faut multiplier par cinq la RAM, le temps de calcul et l'espace disque requis.

Pendant des années, Tromp a tenté de convaincre des dizaines d'entreprises, mécènes, et institutions de financer l'achat du matériel nécessaire pour réaliser son rêve, sans succès. Même Amazon et Google ont refusé de faire un geste. Enfin, en 2014, un astronome hollandais de Princeton lui a fait une proposition. Tromp et ses collègues avaient déjà acquis un peu de notoriété grâce à leur succès avec le plateau de 18x18. Il n'y avait plus qu'à faire l'effort final.

Maintenant qu'il a résolu un mystère resté en sommeil pendant 2500 ans, quelle est la prochaine étape ? Tromp confie qu'il a l'intention de travailler sur sa preuve de travail « Cuckoo Cycle » et de résoudre des problèmes applicables au célèbre jeu Puissance 4. Il veut également appliquer sa méthode au jeu d'échecs. « Pour les échecs, les problèmes de combinatoire sont très différents. Nous ne pourrons jamais obtenir un nombre de combinaisons exact » explique-t-il. « Nous ne pouvons même pas, à l'heure actuelle, donner un ordre de grandeur. J'aimerais au moins, à terme, donner un encadrement du type : 'le nombre est entre 10^44 et 10^45'. »

Mais cela ne résout pas la question que tout le monde se pose : Pourquoi diable s'est-il engagé là-dedans ?

« Avoir la possibilité de déterminer la complexité d'un jeu et ne pas le faire, cela me rend dingue. Ça m'empêche de dormir », confie Tromp. « Comme le grand mathématicien Hilbert l'a dit : Nous devons savoir, nous saurons ! »