Jeu de go : pourquoi ses règles simples résistent au calcul

Intervenant 10:00

Il y a plus de parties possibles sur ce simple plateau de bois, de 19 lignes sur 19, qu'il n'y a de particules élémentaires dans tout l'univers observable.

Intervenant 20:10

Oui, c'est un truc de fou quand on y pense.

Intervenant 10:13

Bonjour à toutes et à tous et bienvenue dans le podcast du magazine Tangente. Aujourd'hui, notre exploration approfondie nous plonge dans un sujet qui a vraiment de quoi fasciner quiconque écoute.

Intervenant 20:24

Tout à fait. Que l'on soit un stratège du dimanche ou un passionné de sciences dures,

Intervenant 10:28

Exactement. L'objectif, c'est de comprendre comment un jeu, qui était considéré dans la Chine antique comme l'un des quatre aboutissements d'une société cultivée, au même titre que la musique, la peinture et la calligraphie, dissimule en fait un puissant fond de mathématiques pure.

Intervenant 20:44

C'est carrément ça.

Intervenant 10:45

Bref, l'émission du jour est consacrée au jeu de go. Et sous son esthétique hyper épurée, ses mécanismes défient complètement l'entendement, qu'il soit humain ou informatique d'ailleurs.

Intervenant 20:58

Le contraste entre la surface et la profondeur est saisissant. En gros, le cadre matériel, c'est juste un goban, donc un plateau quadrillé par 19 lignes horizontales et verticales.

Intervenant 11:08

Ce qui fait 361 intersections, c'est bien ça ?

Intervenant 21:12

Exactement. Et les règles s'expliquent en 30 secondes. On pose tour à tour des pierres noires et blanches sur ces intersections. Et le but, ce n'est pas de détruire l'adversaire de façon binaire, mais de conquérir le plus grand territoire.

Intervenant 11:24

Ouais, en encerclant les espaces vides et parfois les pierres ennemies pour les capturer quoi.

Intervenant 21:29

Voilà. Il n'y a pas de déplacement complexe comme la marche du cavalier aux échecs par exemple.

Intervenant 11:33

C'est statique en fait.

Intervenant 21:34

Totalement. Mais cette simplicité absolue engendre une complexité combinatoire, topologique et algorithmique qui a tenu en échec les mathématiciens pendant des siècles.

Intervenant 11:45

Bon, décortiquons un peu tout ça. Pour vraiment comprendre cette complexité, il faut d'abord regarder le plateau vide et se demander mathématiquement jusqu'où ça peut aller.

Intervenant 21:54

C'est la bonne question à se poser.

Intervenant 11:56

Combien de configurations peuvent exister sur ce petit carré de bois ?

Intervenant 22:00

Pour donner un point de repère à notre audience, prenons un jeu super simple, genre le morpion.

Intervenant 12:04

Ouais, la petite grille de 3 par 3.

Intervenant 22:06

C'est ça. Le morpion, la partie s'achève au bout de neuf coups maximum. Les mathématiciens ont calculé qu'il y a 5 478 parties possibles, si on compte les symétries et tout.

Intervenant 12:17

Donc, un arbre des possibles qu'on peut littéralement dessiner sur un bout de papier, quoi.

Intervenant 22:21

Exact. C'est un système fini, trivial. Mais si on transpose ça au go, c'est l'effondrement du calcul classique.

Intervenant 12:29

Ah

Intervenant 22:30

ouais. Bah oui. Avec 361 intersections, on pourrait se dire, un peu naïvement, qu'une partie s'arrête au bout de 361 coups. Bah

Intervenant 12:38

oui, une fois le plateau rempli, c'est fini.

Intervenant 22:41

Sauf que non. Il y a la règle de capture qui vient complètement pulvériser cette limite.

Intervenant 12:45

Ah, attends, parce que la capture libère les intersections ?

Intervenant 22:49

Exactement !

Intervenant 12:50

En retirant des pierres prisonnières du plateau, on crée des espaces vierges qui rouvrent des nouvelles voies. Ça allonge la partie bien au-delà de la taille de la grille, en fait.

Intervenant 22:59

C'est le cœur du problème. Le nombre de parties devient tellement vaste qu'on ne peut pas les compter séquentiellement. Du coup, l'approche mathématique, c'est de réduire la dimension temporelle pour regarder la dimension spatiale. Action à trois états possibles, en fait. Elle est soit vide, soit noire, soit blanche.

Intervenant 13:14

Ouais, c'est exclusif.

Intervenant 23:16

Voilà. L'algèbre de base nous donne donc une borne supérieure de 3 à la puissance du nombre total d'intersections. Donc pour un goban, c'est 3 à la puissance 361.

Intervenant 13:26

Ce qui nous donne ce nombre vertigineux dont on parlait en intro, on est autour de 10 puissance 172 configurations.

Intervenant 23:32

Ce qui est gigantesque.