Il aura fallu environ 20 ans de plus qu’aux échecs pour qu’un ordinateur arrive à vaincre le meilleur des joueurs de go. Si ce jeu millénaire a pu résister aussi longtemps, c’est qu’il est nécessairement « complexe » … non ?

Répondre à cette question nécessite de définir ce que l’on entend par « complexe » et c’est précisément l’objet de ce deuxième billet de regard sur le match AlphaGo – Fan Hui.

Alors, le go, un jeu complexe ?

Des règles simples, mais difficiles à formaliser

La première « complexité » à laquelle on peut penser est celle d’apprendre à jouer, ce à quoi on répondra aisément que sur ce plan le go est très simple : il suffit de quelques explications pour pouvoir commencer à jouer et ce n’est pas Dédé qui me contredira.

En comparaison, les échecs et ses cousins (shogi, xiang qi) nécessitent de savoir distinguer les pièces et de connaître leur mouvement avant de pouvoir disputer la moindre partie. Le go demande seulement d’avoir compris comment poser une pierre sur le plateau (goban) et comment se passe une capture.

« Alors que les règles Baroques des échecs n’ont pu être inventées que par les humains, les règles du Go sont si élégantes, organiques et si rigoureusement logiques que si une vie intelligente existe quelque part dans l’univers, elle doit très certainement jouer au Go » (Edward Lasker)

Pour autant, si le go est vraiment un jeu d’enfant, l’auteur de cet article pouvant en témoigner pour avoir initié des élèves en classe de maternelle, la question de la formalisation des règles a longtemps été un problème ouvert. Comme toujours, le diable se cache dans les détails …

Il existe essentiellement deux grandes familles de règles au jeu de go : celles qui dérivent des règles chinoises où l’on compte le nombre de pierres présentes en fin de partie et celles dérivant de la règle japonaise où ce sont les intersections libres qui donnent les points (la règle française étant inspirée du meilleur des deux).

A l’exception de quelques cas particuliers, ces règles déterminent généralement le même vainqueur et leurs différences n’ont souvent aucune conséquence pratique et sont d’ailleurs ignorées de la plupart des joueurs. Cependant, si vous voulez écrire un logiciel jouant au go, ces différences (et leur bestiaire de cas particuliers) seront à prendre en compte.

Complexité combinatoire

Une autre définition de la complexité est celle qui se rapporte au nombre de coups possibles : si aux échecs il n’est déjà pas possible de calculer toutes les positions pour trouver les bons coups, ce n’est certainement au go que cela sera le cas ! Il y a en effet plus de positions possibles au jeu de go qu’il n’y a de particules élémentaires estimées dans l’univers visible !

Pour être plus précis, il y aurait entre 10⁴⁰ et 10⁵⁰ positions possibles aux échecs, ce qui est moins que le nombre de particules (10⁸⁰). Quand au nombre de parties, il est estimé au nombre de Shannon (10¹²⁰), ce qui dépasse tout de même le gogol (10¹⁰⁰ ).

Sachant qu’il y a très exactement 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 (~10¹⁷⁰) positions possibles au jeu de go, si l’on en croit les calculs de John Tromp, il y aurait donc 10⁵⁰ fois plus de positions au jeu de go qu’il n’y a de parties possibles aux échecs !

Cependant, si ces nombres sont astronomiques, la science informatique regorge de problèmes d’une « complexité » similaire. Vous en trouverez de nombreux exemples dans les cours de Gérard Berry … que l’on remercie au passage pour avoir fait entrer le go à l’Académie des Sciences 🙂

Des positions difficiles à évaluer …

Si le go est un problème de taille, où il faut couper les branches de l’arbre, c’est également sa nature qui pose problème. En effet, on ne dispose pas de fonction d’évaluation.

Un exemple de fonction d’évaluation est, pour rester dans la comparaison avec les échecs, de donner des valeurs aux pièces et de compter les points pour déterminer qui est en avance. Ce type de fonction, au jeu de go, nous n’en avons pas … par contre ce qui est « simple » c’est de savoir qui a gagné à la fin : il suffit de compter les points !

Billet et vidéo de Science Étonnante (David Louapre)

En effet, s’il est simple pour un joueur de voir qui a gagné, pour peu que l’on sache reconnaître les pierres reliées, celles qui sont capturées ou celles qui ne le sont pas ; il est loin d’être évident de faire voir quoi que ce soit à un programme …

C’est tout l’objet du prochain billet 🙂