Torigo — la révolution du jeu de Go

Notre prochain défi contre l’IA, et pour l’IA. L‘humain sera-t-il battu dans un jeu plus ouvert?

Maxime Goaziou
13 min readSep 30, 2020
2016 — Match du maître Lee Sedol contre AlphaGo

Quelques notes pour cet article.
IA signifie Intelligence Artificielle et le Goban est le nom du plateau au jeu de Go.
Nous aborderons globalement le jeu de Go et les méthodes de l’IA qui ont été utilisées pour fabriquer AlphaGo ainsi qu’AlphaGo Zero qui bat désormais AlphaGo (voir “Mastering the game of Go without human knowledge”). Sans précisions, AlphaGo signifiera AlphaGo comme AlphaGo Zero pour faciliter la lecture.
Enfin, je ne suis pas un expert en IA ni en science de la donnée, donc n’hésitez pas à commenter après lecture du présent article 🙂

Introduction

L’Intelligence Artificielle a fait grand bruit ces dernières années et ce n’est pas prêt de s’arrêter au vu son utilisation grandissante dans la société. Les vidéos de robots qui performent des saltos, les séries dystopiques comme « Black Mirror » ou encore les articles expliquant que nos emplois se font remplacer vitesse grand V par des machines sont là pour nous véhiculer tantôt de la peur tantôt de la béatitude devant nos progrès technologiques.

En 2016, c’est Lee Sedol 9ème Dan au Go, une légende vivante avec ses 18 titres internationaux, qui a été battu par AlphaGo, l’intelligence artificielle de Go acquise par Google (la société Deepmind).

Environnant les 10⁶⁰⁰ parties sensées possibles, le jeu de Go est tellement profond et intuitif qu’il semblait impossible de construire un jour une machine capable de battre les humains. A titre de comparaison il y aurait 10⁸⁰ atomes dans l’univers et 10¹²⁰ parties sensées possibles aux Echecs. (Voir nombre de Shannon)

Cette défaite de Lee Sedol m’a marqué en tant que joueur et en tant qu’humain, car ce jeu si profond faisait partie des derniers à tenir la dragée haute à la machine. Le sentiment que le jeu soit « résolu » a rajouté à ma frustration et m’a rangé derrière une forme de fatalisme ambiant contre les machines qui nous dominerait à tous les jeux. Pourtant, en tant qu’informaticien et passionné de sciences, j’ai été également ébahi de voir les avancées au sein de l’informatique. Il faut quand même le rappeler et se rassurer, ce sont bien des humains et non des robots qui construisent les mécanismes subtils de l’Intelligence Artificielle.

2016 — Sophia, un robot humanoïde disant qu’elle veut détruire l’humanité

La puissance croissante de l’IA et son utilisation généralisée apporte des questions nouvelles quant à la distinction de l’humain face à la machine dans de nombreux domaines où il est affronté. Ainsi même de sa place dans la société. En matière logique, en quoi sommes-nous différent de l’IA et sur quels paramètres pourrions-nous jouer pour retrouver notre ascendant sur elle ? Il est question d’étudier les limites de l’intelligence de l’homme comme celles de la machine.

Les prouesses de l’Humain aux jeux de stratégie sont-elles l’intuition et l’imagination quand celles de la machine sont la capacité de mémoire et la puissance de calcul ?

I ) Calcul versus intuition

Comment réduire l’efficacité de calculs prédictifs dans le jeu ?
Comment favoriser l’intuition et l’imagination dans le Go ?

« L’imagination est plus importante que la connaissance. » Einstein

Avant d’aller plus loin, voici quelques points à connaître sur le jeu:

Au jeu de Go, les bords et les coins regorgent de séquences de jeu (Noir — Blanc) réputées les meilleures, dites « Josekis ». Après des millénaires de jeu, des variations de coups sur les bords ont été retenues comme stratégiquement meilleures que d’autres. On appelle en fait les coups proches des côtés « orientés territoire », c’est-à-dire gagner des points rapidement avec une lecture de jeu plus simple. Les coups approchant du centre du plateau sont eux appelés « orientés influence » car il s’agit de coups plus intuitifs, voire de paris à plus long-terme. Les Josekis sont des chemins qui proposent des issues positives dans l’équilibre entre le gain de territoire et l’influence sur l’avenir de la partie.

Les ouvertures de jeu sont des Josekis particuliers vers les coins et les bords, ils sont aussi appelés Fusekis. En théorie, il permettent de maximiser la probabilité de victoire dès le début de la partie.

Regardons maintenant la mécanique de l’IA:

Pour AlphaGo, l’apprentissage par renforcement semble être un atout principal pour apprendre le jeu. Comme nous l’avons vu, l’IA ne peut pas calculer toutes les parties possibles. Ses méthodes sont utilisées ingénieusement pour lui éviter au maximum de calculer des coups absurdes. Il cherche à être pondéré par les coups obtenant le plus de récompenses pour obtenir la victoire. En jouant contre lui-même, les séquences avec le plus de récompenses à la fin des coups calculées sont retenues et il s’améliore en explorant de nouvelles séquences à partir de meilleurs coups probables à la racine.

Les coups de capture semblent être les meilleurs candidats aux récompenses rapides, bien avant que le plateau soit rempli. L’on capture plus facilement contre un bord. De plus des récompenses peuvent être obtenues plus rapidement en entourant des territoires à partir des coins que nul part ailleurs. Au cours du temps, on dirait que la machine se sent attirée quelque part comme la gravité nous attire au sol, là où il y a le plus de récompenses: vers les coins et les bords du goban !
Progressivement, les graines (pierres), s’écartent du sol (les bords, et fleurissent en générant des fusekis (les ouvertures de jeu) ? Le robot apprend et se tient debout.

Image 1: 1–1 point, un pierre sur le coin en 1, pierre ayant le moins de libertés dès le départ. Image 2: un Joseki connus sur le coin. Source: AlphaGo Zero dans “Mastering the game of Go without human knowledge”

Ces images d’AlphaGo montrent son processus d’apprentissage: l’IA apprend d’abord à ne pas jouer de coups mauvais sur les coins où la pierre est le plus en danger car avec le moins de liberté du plateau, pendant que son opposant (lui-même) obtient des récompenses en apprenant à la capturer (coup 1 image 1). Plus tard (image 2), on peut voir que l’IA apprend de bonnes séquences sur les coins puis qu’elle tempère finalement leur utilisation pour en préférer d’autres encore meilleures.

« Les coins sont d’or, les bords sont d’argent, le centre est la jungle. » Proverbe de Go

Avant d’atteindre un état déterministe de la partie, les coups sont prédits à partir des probabilités de calculs obtenues par des séquences de coups finies qui donnent les meilleures récompenses pour gagner. Les séquences déterministes avec le moins de profondeur se trouvent sur les bords, c’est pourquoi on trouve parmi les premières séquences apprises les Josekis. Les bords permettent d’éclairer des séquences déterministes alors que le centre reste un terrain obscure et indéterminable.

AlphaGo contre Lee Sedol —Une ouverture de jeu très classique

Il est remarquable de constater que les grands maîtres ainsi qu’AlphaGo, jouent, pour leur très grande majorité, leurs premiers coups de parties sur les points étoilés du goban, ou ‘hoshis’, aux 4 coins (points noirs sur l’image).

Ces endroits stratégiques, ou heuristiques, sont des traditions de jeu qui perdurent et qui, paradoxalement, ferment le jeu aux coups de connaisseurs au moment où il est le plus ouvert en amont de toutes les séquences possibles: au début tout le goban est libre pour jouer !

Et si ces traditions nous empêchaient de découvrir d’autres styles de jeu ? Comment la machine pourrait-elle réduire la largeur du jeu à calculer, qui lui permet de sélectionner des meilleurs coups en temps fini, si elle n’a plus bord sur lequel s’atteler ni milieu pour se repérer ?

Si les Josekis sont bien un avantage pour l’humain comme pour l’IA, ils semblent lui laisser encore plus de marge en trouvant des séquences encore plus efficaces. Mais alors, comment pourrions-nous retirer les Josekis ? Une réponse radicale mais finalement assez sérieuse m’est apparue : retirons les coins et les bords du plateau !

II ) Un plateau sans bords

A quoi peut donc ressembler un plateau sans bords ?

“Il n’y a pas de limite.. C’est infini” ?

Et bien oui … et non. Ici cela dépend peut-être de la façon dont vous imaginer la forme de l’univers 🙂. Mais si nous voulons faire une partie avec une durée convenable pour notre dégustation de thé, considérons que le quadrillage officiel au Go de 19x19 lignes et colonnes doive être respecté. Ainsi, comment supprimer les bords et conserver un quadrillage fini ?

Rejoignons alors les bords du plateau de Go !
Qu’obtient-t-on ?

“Une Sphère” ?

Pourquoi pas ! Mais nous ne devons pas oublier que le plateau du jeu est un quadrillage en tout point, sinon les règles du jeu seraient caduques !

Pour vérifier si la Sphère respecte la condition d’un quadrillage en tout point, dessinons un quadrillage dessus :

Sphère

Sur cette image qui ressemble à une jolie planète, le quadrillage semble fonctionner..

Sauf aux 2 pôles ! En effet ce n’est plus un quadrillage à ces 2 endroits, mais une multitude de lignes qui se rejoignent au même point : soit la formation de triangles et non de carrés pour notre quadrillage voulu en tout point.

La Sphère n’est donc pas valide en nombre d’intersections.

Mais alors, n’existe-t-il pas de forme pour que les bords se rejoignent et jouer au Go ?

Persévérons en tentant autre chose avec notre plateau de jeu initial. Si nous tordons le goban au milieu (à ne pas faire à la maison !), pour faire se fusionner deux bords opposés, qu’obtient-on ?

Nous avons maintenant un solide de révolution : le Cylindre !

Certes, maintenant notre quadrillage est bien valable avec deux bords en moins, mais il en reste encore deux..

Et si nous réitérions l’expérience en fusionnant cette fois-ci les deux bords restant, les deux cercles du Cylindre obtenu ?

BinGo ! Nous avons désormais une nouvelle révolution : le Tore !

Tore, forme où le quadrillage est respecté en tout point: un quadrillage circulaire.

Ca y est une forme existe pour jouer au jeu de Go sans bords et elle est en 3 dimensions. Mais il faut l’avouer, ce n’est pas encore très pratique.

III ) Une plate-forme pas si plate

Avec cette envie de sortir de la résignation collective face aux machines et pour découvrir le jeu de Go d’une vision nouvelle, j’ai donc conçu une plate-forme pour jouer au jeu de Go sans coins ni bords :

Le « Torigo » ! ➡ https://torigo.io

Vous l’aurez peut-être remarqué, c’est la concaténation de :

  • « Tore » , la forme où le quadrillage circulaire est possible (le donut des Maths)
  • et de « igo » qui est l’appellation du Go au Japon.

Comme évoqué précédemment, il n’est à priori pas aisé de jouer sur un donut. Il serait préférable de visualiser l’intégralité du plateau et du stade de la partie sans devoir tourner un objet.
Voici donc les astuces que j’ai trouvées pour rendre le Torigo jouable simplement :

De la même manière qu’au Go classique sur un plateau en 2 dimensions, l’affichage du plateau est entier mais il y a maintenant le prolongement des lignes en pointillés sur les extrémités. De plus, si une pierre est jouée sur une extrémité, elle apparaîtra en transparence à l’extrémité opposée pour visionner sa présence: on comprend que ce serait l’autre bout du donut dans le monde réel.

Cependant, puisqu’il n’y a plus de coins ni de côtés, il n’y a plus de centre non plus ! Alors il est possible de changer son propre référentiel dans le jeu. Pour faciliter le déplacement, on peut soit cliquer sur les flèches pas à pas, soit cliquer et se déplacer dans le plateau comme on tire une mappemonde virtuelle.

Images 1 et 2 : même partie 9x9 avec un référentiel différent. Pointillés et pierres en “miroir” aux extrémités. Image 3 : capture de Blanc.

Lors des parties il est amusant de savoir que tu peux regarder le jeu sous un autre angle que son adversaire.

Images 1 et 2 : Fin d’une même partie d’un plateau 13x13 sur torigo.io, vue d’un référentiel différent.

IV ) Les implications sur le jeu

Pour les nouveaux joueurs, puisque ce jeu n’a pas encore le poids de l’histoire sur les stratégies, cela peut être un avantage pour comprendre le jeu de Torigo et développer de pures stratégies. J’ai pu remarquer qu’il était aussi simple d’apprendre le Torigo que le Go. Bien que profond, ce jeu est très simple avec ses 2–3 règles. En supprimant les bords, on enlève en fait presque une règle.

Si tu es intéressé par apprendre le Go, aussi appelé le jeu où on entoure, n’hésite pas à jouer dans ce mini-jeu simplifié: le Capture Go où le but est de capturer 5 pierres le premier. A essayer avec ou sans bords contre ce petit robot: Capture Bot 🤖

Pour les joueurs expérimentés de Go, cette variante peut être complémentaire avec le Go classique et même rebattre les cartes avec vos adversaires ! On peut aussi se demander si toutes les règles et principes sont bien conservés. Comme vu précédemment, le fait que le quadrillage soit respecté en tout point permet de conserver l’intégralité des règles.

Une question que l’on peut se demander est: est-ce que le shisho est conservé ?

Le « Shichō », ou escalier, est une séquence de jeu où un joueur a enfermé les pierres de son adversaire de manière à ce que s’il essaie de s’échapper, il se fera prendre avec certitude ses pierres une fois arrivées jusqu’au bord du plateau. La séquence fonctionne-t-elle au Torigo ? Rencontrons nous sur ce nouveau goban pour le découvrir 🙂.

Pour l’intelligence artificielle:

Vis à vis d’AlphaGo, nous ne pouvons nier que construire des territoires efficacement vers le centre faisait aussi partie de son ingéniosité. Cependant, l’IA pourra-t-elle réduire la largeur du jeu dès le début du jeu pour trouver des séquences déterministes qui lui permettent de s’améliorer et de dépasser notre intuition avant la fin de la partie ? Cela ne sera pas facile et l’Abre de Recherche amélioré qui est impliqué (sans déploiements de Monte Carlo dans AlphaGo Zero) ne sera peut-être pas si efficace avec un tel goban: l’issue parait incertaine puisque très indéterminée.
N’oublions pas que nous ajoutons en fait une dimension et passons à un goban 3D.

La machine sera-t-elle désorientée sans référentiel et sa gravitation déterministe pondéré vers les bors ? Le robot pourra-t-il se lever sans sol sur lequel s’appuyer ? Encore plus de possibilités de liaisons entre les groupes de pierres sur l’ensemble du nouveau goban circulaire semblent émerger: donc encore plus de parties sensées possibles !

“I, Robot” movie

Par exemple, il parait insensé sur un Goban classique de jouer ses premières pierres sur les bords car elles seraient vite en danger et ne formeraient pas de territoires (3 libertés sur les bords, 2 sur les coins). Sur le torigoban toutes les pierres ont 4 libertés dès le départ, toutes les probabilités de victoire des coups possibles sont équitablement réparties au début du jeu: la toute position de la première pierre n’aura d’ailleurs aucune conséquence sur le déroulement de la partie.

Une dernière chose que j’aimerai évoquer sur l’apprendtissage d’AlphaGo Zero. Les auteurs disens que l’IA a découvert la séquence du Shisho étonnamment bien plus tard que d’autres grands principes du jeu. Je dois avouer que cela ne m’a pas tellement étonné puisque la profondeur de cette séquence peut être aussi longue que la plus grande diagonale du goban. Au jeu de Torigo, le Shisho serait peut-être un des premiers principes que l’IA aurait à apprendre, et devinez quoi, les diagonales des Shishos sur le torigoban sont en moyenne toujours plus grandes..!

De l’article “Mastering the game of Go without human knowledge” sur AlphaGo Zero

Quoiqu’il en soit, il sera nécessaire que les joueurs de Go “mettent de côté” les stratégies classiques en entrant dans cette nouvelle dimension. Le jeu de Go a des millénaires et il reste toujours autant magique. Mais sur le Torigo, de nombreuses choses sont à comprendre et il reste quasiment tout à faire !

Le jeu de Go m’a permis de voir et d’approfondir des concepts tout en m’amusant et même de faire parfois des parallèles avec la philosophie.

Je pense que jouer sur un plateau sans bords apporte encore quelque chose : devoir nous appuyer sur nos propres pierres plutôt que sur des limites visibles connues, de recentrer nos intuitions dans ce super jeu de stratégie.

Conclusion

Les principaux objectifs de cette réflexion et de l’implémentation du Torigo sont de :

  • Challenger les chercheurs en IA et les joueurs humains à se confronter dans cette nouvelle dimension ;
  • Permettre à de nouveaux joueurs de découvrir le Go dans une version originale sans ouvertures de jeu !

➜ Cela va-t-il rebattre les cartes entre les joueurs ?
➜ AlphaGo et le maître Lee Sedol s’affronteront-ils de nouveau ?
➜ Serait-ce le nouveau jeu de stratégie où l’humain bat encore la machine ? Pour l’instant, il l’est 😜

N’hésites pas à partager tes réflexions dans les commentaires ou de me contacter directement. Je sera ravi de pouvoir en discuter, et qui sait, de voir la première IA jouer au Torigo !

L’aventure commence ! Here we Go again?
https://torigo.io

🇬🇧 Partager l’article à des anglophones : the Go game revolution.
Partie rapide contre un robot: Capture Bot 🤖

Merci à mes proches et à ma famille, pour leurs soutiens, leurs discussions et “prises au jeu”. Des débats persistent mais nous auront des réponses tôt ou tard. Je ne serai pas arrivé jusque là sans leur regard critique et leur bienveillance.

Soutenir le projet : Patreon
Contact : vick@torigo.io

--

--

Maxime Goaziou
Maxime Goaziou

Written by Maxime Goaziou

Software engineer and Go player — Creator of Torigo.io the open game of Go with no edges, unbeaten by AI

Responses (2)