Pourquoi le jeu est-il si compliqué pour un robot?

Billet d'humeur journalistique :


"...résultats des courses, l'ordinateur a battu l'humain, un pilier de notre intelligence qui s'effrondre ...!!"

Info Huffington post
Pourquoi le jeu est-il si compliqué pour un robot?
Les jours à venir pourraient bien être à marquer d'une pierre blanche dans l'histoire de l'intelligence artificielle. Du 9 au 15 mars, AlphaGo, le programme développé par DeepMind, la société de Google spécialisée dans l'IA, va affronter le champion du monde de jeu de go.
Une victoire d'un ordinateur sur Lee Sedol serait un véritable coup de tonnerre, au moins aussi important que la défaite de Garry Kasparov contre Deep Blue, le superordinateur d'IBM en 1997. Le programme de Google a déjà réussi à s'imposer face au meilleur joueur européen en octobre, une première. Mais la différence de niveau est impressionnante. Seul un joueur occidental a réussi dans l'histoire à se hisser au niveau des meilleurs compétiteurs asiatiques de ce jeu d'origine chinoise.
Qu'est-ce qui rend le jeu de go si difficile pour le robot? Les règles, que Confucius mentionnait il y a 2500 ans, sont pourtant assez simples.
Un pion à la fois
Le plateau du jeu de go est composé de 19 lignes verticales et 19 horizontales. Au total, cela fait donc 361 intersections sur lesquels les deux joueurs doivent placer, chacun leur tour, un pion blanc ou noir. Ces pions sont tous les mêmes et ne peuvent pas être bougés une fois posés.
Ils peuvent par contre être capturés, pour ça, il faut enlever les "libertés" de ces pions, c'est à dire les encercler entièrement (les diagonales ne comptent pas). Dans l'exemple ci-dessous, les deux pions noirs sont encerclés, le joueur blanc les retire donc du jeu (et gagne des points).



Le but du jeu est de contrôler le plus de "territoires" possibles, soit des ensembles de pions ou d'intersections vides, mais ne pouvant pas être prises par l'adversaire. Car vous les encerclez. Placer un pion à l'intérieur équivaudrait à un suicide.
Quand il n'y a plus de places libres, le jeu s'arrête et on compte les points: les intersections vides à l'intérieur de ces territoires plus les pièces capturées.
Qu'est-ce qui rend le jeu de go si difficile à maîtriser pour un ordinateur? Malgré cette simplicité apparente, les positions possibles sont incroyablement vastes. Il y en a "1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000", selon Demis Hassabis, le fondateur de DeepMind, la startup rachetée par Google en 2014.
Cela représente un 1 avec 170 zéros derrière. A titre de comparaison, on estime que l'univers connu est composé de bien moins d'atomes (seulement "80 zéros" derrière le 1). Et les échecs? Ici, le nombre de positions possibles serait d'un 1 suivi de 47 zéros.
Un jeu trop "simple" pour un ordinateur
Avec un tel chiffre, impossible pour une intelligence artificielle d'arriver à calculer, pour chaque coup, toutes les possibilités. Surtout, il y a un deuxième problème: le jeu est très difficile à prédire. " Pour analyser une position il faut comprendre ce qui se passe sur le plateau et les interactions possibles entre les pièces", explique au HuffPost Tristan Cazenave, chercheur en intelligence artificielle appliquée au jeu à l'université Paris-Dauphine.
"Aux échecs, on étudie la valeur de chaque pièce, puis on évalue leurs positions, pour savoir si une pièce à beaucoup de liberté. Avec toutes ces informations, on peut estimer si un joueur est plutôt en avance ou en retard dans la partie", précise-t-il. C'est en analysant qui gagne dans la partie et les possibilités laissées par le jeu que les algorithmes arrivent à vaincre les humains.
Mais avec le jeu de go, il était quasiment impossible de définir ces deux inconnues. Jusqu'au programme mis en place par DeepMind. En utilisant des réseaux de neurones, les chercheurs ont montré au logiciel des milliers de matchs et des millions de combinaisons possible pour qu'il apprenne des plus grands joueurs mondiaux. AlphaGo a ensuite joué des milliers de parties contre lui-même pour progresser et découvrir de nouveaux coups.
Reste à voir si cette nouvelle méthode suffira à battre le plus grand joueur de go actuel. Si la majorité des experts estiment que le programme tel qu'il a été pensé en octobre dernier était quasi sûr de perdre contre Lee Sedol, reste à voir comment DeepMind aura amélioré son poulain en six mois.