Un
pro du go battu par un
algorithme : pourquoi ça change tout
Par Oscar Barda Game
designer. Publié initialement le 28/01/2016
Les
faits : DeepMind est un petit labo anglais d’intelligence
artificielle fondé en 2011, racheté par Google
en 2014,
qui l’arrose depuis de moyens impressionnants pour faire avancer ce
champ de
recherche.
Premier
coup d’éclat de DeepMind : une intelligence
artificielle capable de gagner
à tous les
jeux de la vieille console Atari un à un.
Cette
fois, DeepMind vient de battre Fan
Hui, le champion d’Europe de jeu de go, à l’aide de son
programme
AlphaGo – en octobre, ce que vient seulement de
révéler la
revue Nature.
Une
partie de go sur son plateau, le goban - Xchen27/Wikimedia
Commons/CC
Le
jeu de go est l’un des plus anciens jeux de plateau
stratégiques du monde dont nous connaissons encore les règles. Joué en
Chine
depuis 2 500 ans au moins, il est doté de règles simples dont
émerge
une très grande complexité.
Comme
d’autres jeux célèbres, il répond à l’adage (sinon le Graal)
des faiseurs de jeu : « Un instant pour l’apprendre, une vie
pour le
maîtriser. » La partie se déroule sur le goban (le
plateau de jeu quadrillé de 19x19 lignes) où les joueurs placent à
tour de
rôle des pierres blanches et noires pour capturer des territoires,
s’encercler
ou se capturer l’un l’autre.
Encore
extrêmement populaire en Chine, en Corée et au Japon, le go
joua même un rôle déterminant dans l’histoire de ce dernier pays à
travers une
partie célèbre racontée dans le roman « Le
Maître
ou le tournoi de go » de Yasunari Kawabata (Nobel
de
littérature 1968) où Kitani Minoru, jeune supporter de l’ouverture du
Japon
affronta en 1938 le Meijin (maître de go du Japon) Honinbo Shusai,
tenant
de la tradition, en une illustration grandiose des tensions politiques
d’avant-guerre.
La partie de go légendaire du Meijin contre Minoru - Gobooks.info
Ce
qu’il faut pour la suite retenir de
l’essence de ce jeu c’est que s’il possède une composante stratégique
analytique
comme les échecs, le déroulé d’une partie de go est beaucoup plus
fluide,
habile et agile que les froids calculs.
Au
go, il y a rarement une seule bonne réponse et les joueurs
expriment ainsi fortement leurs caractère en jouant. Il y a quelque
chose
d’étrangement humain dans cet enchaînement de pierres noires et
blanches ;
il faut réagir aux émotions, aux envies de l’adversaire, le faire
tomber dans
des pièges non pas parce qu’il ne les a pas vu venir, mais parce que
vous jouez
sur une faille de son comportement, de sa personnalité plutôt que de
son
raisonnement.
Pour
résumer, le go permet aux joueurs une grande créativité et
les erreurs et caractères des joueurs sont souvent des facteurs bien
plus
déterminants qu’aux échecs (il va de soi qu’aucun des deux jeux n’est
meilleur
que l’autre, ils sont juste différents mais nous y reviendrons !).
Voici
donc un premier point à comprendre sur le go : c’est un
jeu très humain.
Le
nombre de coups légitimes sur un plateau de go est de 10 puissance
170 c’est à dire 1 avec 170 zéros derrière.
Impossible
à se représenter ? On peut calculer par
approximation combien il y a d’atomes dans nos corps (environ 7x10 puissance
27). Puis combien d’atomes composent la terre en fonction de
sa
masse complète, puis faire de même pour les planètes avoisinantes puis
inclure
le soleil, puis les étoiles et les galaxies qui nous entourent dans le
vide
puis enfin faire une estimation du nombre d’atomes dans
l’univers… Au
total il y en aurait entre 10 puissance 78 et
10 puissance 82 dans
l’univers visible.
Il
y a donc plus de possibilités de parties de go que d’atomes
dans tout l’univers. Combien de fois plus ? Un milliard de
milliards de
milliards de milliards de milliards de milliards de milliards de
milliards de
milliards de fois plus.
Ça
fait beaucoup de parties de go possible (même si nos cerveaux
sont peu équipés pour comprendre l’ampleur de ces ordres de grandeur).
A titre
de comparaison, il y a aux échecs moins de 10 puissance 50 positions
légitimes
possibles.
Kasparov contre le programme X3D Fritz en 2003 - SMSI/Wikimedia Commons/CC
Par
ailleurs alors qu’aux échecs il y a en
moyenne environ 20 coups possibles à chaque tour, au go il y
environ 200.
Au tour suivant ? Encore 200. Et au tour d’après 200 et
autant au
tour d’après, etc.
Ce
que cela veut dire c’est que pour calculer tous les coups
possibles à partir d’une position, si aux échecs un ordinateur peut
facilement
voir 4 ou 5 coups en avance (20 x 20 x 20 x
20…), au
go cela devient très vite impossible.
Si
je vous donne des nombres un peu abstraits et très grands c’est
pour vous expliquer un deuxième concept : le go est quasi
incommensurable.
En
1996, l’ordinateur Deep Blue affronte aux échecs le champion du
monde Garry Kasparov en deux parties, une gagnée par la
machine et
une par l’humain. Puis en 1997 l’ordinateur Deeper Blue amélioré
revient
et gagne cette
fois-ci 3 parties sur 5 (les deux parties restantes étant
deux matchs
nuls). Mais quelle différence avec le jeu de go finalement ? C’est
la même
chose non ? Un ordinateur qui bat un humain à un jeu de stratégie…
Connaissez-vous
le morpion ou tic-tac-toe ? Mais si, la
grille de 3 x 3 cases dans laquelle un joueur joue les croix
et
l’autre les cercles ! Eh bien on peut à peu près tous, avec un peu
d’entraînement, résoudre le morpion.
Résoudre
un jeu c’est être au courant de toutes ses possibilités
et pouvoir à chaque instant choisir la meilleure chose à faire
mathématiquement
pour finir gagnant à tous les
coups. Car si le morpion a quelque chose comme
20 000 parties possibles, elles se ressemblent toutes :
la
partie se finit toujours en 9 coups et après le premier il n’y a
plus que
8 possibilités, puis 7, et l’on voit bien vite où l’adversaire
veut en
venir, permettant de prédire très facilement les coups à chaque instant
et de
l’empêcher d’aligner les trois symboles qui donnent la victoire.
Exemple
de
grille de morpion - Symode09/Wikimedia
Commons/domaine public
Dans
les années 70, le morpion est bien vite résolu par
les ordinateurs, c’est à dire qu’un ordinateur fera toujours victoire
ou match nul contre vous. Comment ? Par une
méthode qu’on
appelle le bruteforcing (la
force brute), c’est-à-dire en prévoyant tous les coups possibles à tous
les
instants et tous les coups possibles après ceux-là et en choisissant
parmi eux
la meilleur option pour aller vers la victoire.
A
mesure que la capacité de calcul des ordinateur augmentait, peu
à peu les jeux sont tombés sous les coups
toujours plus
rapides et puissants de l’informatique ces 30 dernières années (le
Puissance 4, Nim, Quarto, l’awalé)
jusqu’à ce qu’on arrive justement à Deep Blue en 1996 qui tente de
montrer
que l’informatique peut battre un joueur d’échecs…
Alors
comment est-ce que Deep Blue gagne un match contre
Kasparov ? Bon, c’est un peu plus compliqué que ce que je vais
dire là,
mais pour simplifier : Deep Blue apprend par cœur les parties que
Kasparov
a perdues et à chaque fois que Kasparov joue, Deep Blue essaie de jouer
au plus
près comme les joueurs humains qui ont battu Kasparov. Lorsque les
pièces
commencent à mourir, le nombre de possibilités diminue et au bout d’un
moment,
il devient plus facile à Deep Blue de faire du bruteforcing :
calculer toutes les possibilités
et gagner à partir de ça.
AlphaGo
n’a pas appris à battre Fan Hui meilleur joueur de go
européen, il a appris à jouer au go mieux que lui. AlphaGo ne bruteforce pas
le go, son but n’est pas de résoudre le go mais d’être le meilleur
joueur.
AlphaGo,
vidéo promotionnelle de
DeepMind
La
différence n’est
peut-être pas évidente de prime abord mais la nature de cette
différence écrira
l’avenir de l’humanité :
·
dans
un cas,
l’ordinateur est une calculette idiote mais très puissante qui essaie
tous les
coups possibles sans distinction,
·
dans
l’autre,
l’ordinateur s’approche de la façon dont les humains pensent.
Dans
le premier cas,
celui de Deep Blue, vous mettez un robot dans une pièce avec
10 portes
fermées et une ouverte et il s’envoie la tête la première dans toutes
les
portes jusqu’à trouver celle qui est ouverte. On pourra certes admirer
sa
persistance, sa puissance et sa résistance supérieures en tous points à
celles
d’un humain qui lui se serait fait mal, mais un vrai humain aurait
juste en
10 secondes passé la porte ouverte plutôt que de se cogner le
crâne aux
autres.
AlphaGo,
pour filer la
métaphore, regarde autour de lui, se cogne dans une porte fermée puis
décide de
passer la porte ouverte.
Exemple
de robot
« pas fut fut » comme dirait ma grand-mère
Eh
bien AlphaGo a passé la porte : il a
défait Fan Hui par 5 à 0. Et pas comme Deep Blue avec des égalités
et des
bugs… Non, AlphaGo, rencontrant le champion européen pour la
première
fois, l’a mis à terre et ce sans avoir appris comme l’avait fait Deep
Blue à se
battre exclusivement contre Fan Hui. Non, il a juste été meilleur au go.
Et
ça n’est pas simple comme prouesse d’ingénierie car cela fait
maintenant 50 ans que les informaticiens essaient d’abattre les
joueurs de
go. Mais jusqu’à présent, avec des méthodes classiques de résolution et
de
force brute, en raison de la complexité du go, les ordinateurs
n’avaient jamais
réussi à atteindre un niveau professionnel car encore aujourd’hui nous
n’avons
pas la capacité de calcul nécessaire pour bruteforcer le go.
Au
mieux les intelligences artificielles pouvaient-elles parfois
prendre une partie ou deux à des bons joueurs dans les années 90, puis
en
2013 quelques avancées ont été faites. Mais AlphaGo vient de
renverser la
table dans la course que se mènent tous les géants du Web à
l’intelligence
artificielle.
A
la manière du joueur
d’échecs de Stefan Zweig, le
programme est enfermé dans une geôle de processeurs informatiques
formant un
réseau de neurones artificiels [PDF]
–
inspiré de loin de nos structures cérébrales – et a analysé
30 millions de
coups d’humains professionnels, essayant de comprendre pour chacun la
logique
derrière le mouvement et lesquels ont mené à la victoire ou à la
défaite. Il
essaie ensuite de comprendre comment s’enchaînent ces mouvements entre
eux et quels
motifs se répètent et à nouveau cherche parmi ceux-là lesquels sont
gagnants
dans quelles conditions.
Enfin,
AlphaGo créé plusieurs versions de lui-même un peu
différentes et joue contre lui-même des millions de parties en essayant
de
respecter un équilibre de tactique (court terme) et de stratégie (long
terme).
Puis
comme nous l’avons dit, d’autres sociétés, les Facebook, les
Apple et compagnie s’essaient au go, on fait des petits tournois
amicaux entre
intelligences artificielles. AlphaGo en a remporté 499… sur 500.
En
mars de cette année, AlphaGo va aller en Corée se frotter en
5 matches à Lee
Sedol,
légende moderne du go, 9e dan (le plus haut rang) considéré comme l’un
des
meilleurs joueurs au monde.
Des
joueurs de
go du Xe siècle. Voilà ce qu’AlphaGo essaie de battre - Tableau
de Zhou Wenju/Wikimedia Commons
Pourquoi ?
Parce
quand moi je joue au go, je joue au même jeu que d’autres humains il y
a
2 500 ans. Alors qu’il est évident que notre vision de l’art,
des
tableaux, des sculptures a changé, l’assemblage de sentiments, de
hauts, de
bas, de victoires fracassantes et de défaites écrasantes qui
constituent le go
me connectent du bout des doigts à des siècles d’histoire. La façon
dont on
mange, dont on marche et dont on parle a changé, mais nous jouons
encore au go
comme il y a 1 000 ans.
D’une
certaine façon, le
go comme les échecs avant lui représente une victoire de la machine non
pas sur
l’intelligence, mais sur la culture humaine : les scientifiques
commencent
à montrer que la machine peut prendre part à nos jeux et à notre
Histoire et
abattant le go, symbole de raffinement chez la noblesse et
l’aristocratie de
certaines de nos cultures humaines, pinacle de la subtilité et de
l’intelligence tactique, AlphaGo battant Lee Sedol n’est pas du tout
une menace
pour nous humains mais bien un pied dans la porte dont nous ne nous
déferons
pas.
Peut-être
(sûrement)
seront-elles trop vite trop intelligentes pour nous, pas forcément
conscientes
d’elles-mêmes (pour peu qu’on comprenne un jour ce qu’est la
conscience) mais
trop forte à tout ce que nous faisons pour que nous les maîtrisions,
ces
intelligences artificielles…
Mais
pourquoi
sommes-nous allés sur la lune déjà ? Parce qu’on en était
incapable, parce
que c’était impossible et que des imbéciles voulaient accomplir
l’impossible.
C’est
la raison pour
laquelle l’IA se frotte au go mais dans quelques années elle écrira des
romans,
parlera naturellement, comprendra nos lois et sera peut être capable de
nous en
proposer des meilleures… Parce qu’aujourd’hui c’est impossible et que
des gens
ont décidé de rêver grand.
Et
si au-delà du tour de
force culturel, cette première victoire au go est aussi un exercice
pratique
pour la machine, tentant d’appliquer ses méthodes d’apprentissage à des
règles
codifiées, d’apprendre notre monde et de faire avancer les méthodes de
calcul
moderne, il n’en reste pas moins que ça n’est plus juste une grosse
calculette
qui va plus vite que nous, mais un pas marquant vers le début de la
révolution
des intelligences artificielles.
Dernière mise à jour 02/07/2023