CNRS : Centre National de la Recherche Scientifique
Liens utiles CNRSLe CNRSAnnuairesMots-Clefs du CNRSAutres sites
Accueil Sciences et technologie de l'information et de l'ingénierie : Centre National de la reherche scientifiqueAccueil Sciences et technologie de l'information et de l'ingénierie : Centre National de la reherche scientifique
  Accueil >La recherche en ST2I> Faits marquants > Crazy Stone et le jeu de Go (médaillé d'or 2006)

Faits marquants

 

 

Crazy Stone et le jeu de Go (médaillé d'or 2006)

 

Depuis la victoire de Deep Blue contre Kasparov aux échecs, le nouveau défi pour l'intelligence artificielle est le jeu de go. Ce jeu d'origine chinoise, plusieurs fois millénaire, reste un domaine où l'intelligence humaine surpasse très largement les meilleurs algorithmes. Une communauté de chercheurs très active organise régulièrement des tournois entre programmes. Le programme développé au GRAPPA (LIFL/UMR 8022 CNRS/USTL), Crazy Stone, a remporté la médaille d'or des 11th Computer Olympiad, qui se tenaient en juin 2006 à Turin, devant dix autres concurrents venus du monde entier.

Jusqu'à présent, les techniques qui avaient été développées pour d'autres jeux, comme les échecs, n'ont pas permis de mettre au point un programme de go capable de rivaliser avec un joueur humain amateur, même peu expérimenté. Le jeu de go possède en effet des caractéristiques qui le rendent particulièrement difficile à aborder : le nombre de coups possibles est beaucoup plus grand qu'aux échecs (plus de 300 en début de partie), et il est souvent nécessaire d'anticiper un nombre de coups beaucoup plus élevé. Les méthodes qui explorent de manière exhaustive toutes les séquences possibles se heurtent rapidement à une très violente explosion combinatoire.

Pour tenter de surmonter cette explosion combinatoire, Crazy Stone utilise un algorithme qui n'est pas exhaustif, et qui prend ses décisions en se basant sur un échantillonage aléatoire des séquences possibles. Ce type de méthode, dit de Monte Carlo, avait été déjà proposé pour le jeu de go, mais n'avait pas réussi à produire de programmes très forts. En apportant des améliorations aux algorithmes, Crazy Stone a été le premier programme de go Monte Carlo à remporter des tournois importants.

Le succès de Crazy Stone a engendré un engouement important pour les techniques de Monte Carlo, et de gros progrès ont été réalisés depuis sa victoire à Turin. Malgré ces progrès spectaculaires, les meilleurs joueurs humains restent hors de portée des programmes actuels. Le jeu de go reste donc un problème ouvert très difficile, dont on peut espérer que l'étude nous apportera encore de nombreuses innovations dans le domaine des algorithmes de planification et de décision séquentielle.

 

Crazy Stone (noir) en action contre Aya (blanc): les couleurs vertes et bleues indiquent l'espérance de territoire estimée par le programme pour chaque joueur. Elle est calculée en faisant la moyenne de milliers de parties aléatoires.

 

Crazy Stone (noir) en action contre Aya (blanc): les couleurs vertes et bleues indiquent l'espérance de territoire estimée par le programme pour chaque joueur. Elle est calculée en faisant la moyenne de milliers de parties aléatoires.

 

Pour plus d'informations sur Crazy Stone :

http://remi.coulom.free.fr/CrazyStone/

 

Pour plus d’informations sur le jeu de go en général :

http://jeudego.org/

 

Contact

lgeib@lifl.fr

Accueil du Sitecontactimprimer Plan du sitecredits