92
Recherche arborescente Monte-Carlo
joueurs de Go en extrême orient, et des centaines de joueurs professionnels. Le jeu de
Go est un jeu à information parfaite et à somme nulle entre deux joueurs : Blanc et Noir.
Un damier de Go (Goban) est une grille 19xl9, qui est vide au début de la partie et que
les joueurs remplissent tour à tour en posant une pierre sur une intersection. Le nombre
moyen de coups possibles est de l 'ordre de 250, et les parties peuvent facilement durer
200 coups. D ' un point de vue programmation , les difficultés viennent à la fois du grand
nombre de coups possibles, qui rend une approche combinatoire par force brute de type
Alpha-Bêta inadaptée ; elles viennent aussi de la complexité de l'év aluation d' une position
et de la définition ambiguë de la fin de la partie (en utilisant des règles non ambiguës, les
parties dureraient plus de 350 coups). Les meilleurs joueurs de Go sont 9ème Dan et les
débutants sont 20ème kyu. Plus un joueur a un grade élevé en Dan plus il est fort, plus
un joueur à un petit nombre de kyus plus il est fort. Un joueur premier kyu qui progresse
devient premier Dan.
Un des nombreux intérêts de la programmation du jeu de Go d' un point de vue de
! ' Intelligence Artificielle [12] est qu'on peut très facilement comparer deux programmes
en les faisant jouer l ' un contre l ' autre. Et les programmeurs de Go ne s 'en privent pas. De
nombreux tournois de programmes sont régulièrement organisés.
Les méthodes de Monte-Carlo permettent d' écrire un programme de Go av ec très
peu de connaissances ; de plus l ' approche Monte-Carlo réagit bien à l ' augmentation de la
puissance de calcul, alors que les approches précédentes de la programmation du jeu de
Go utilisaient beaucoup de connaissances et ne réagissaient pas bien à l ' augmentation de
puissance de calcul.
Afin d' écrire un programme de Monte-Carlo Go on doit effectuer des parties aléatoires. La connaissance minimale à av oir pour jouer ces parties est de jouer des coups
légaux et ne pas se boucher les yeux. I! est tout à fait remarquable qu' un programme qui
dispose de si peu de connaissances du jeu soit capable de mieux jouer que des programmes
qui ont de grandes quantités de connaissances.
Exercice : É crire un classe Go qui permettent de jouer des parties aléatoires de Go.
5.3 Algorithme basique de Monte-Carlo
Maintenant qu'on dispose d' une classe permettant de jouer des parties aléatoires de
Go, il dev ient simple d'écrire un algorithme de Monte-Carlo basique. Cela consiste simplement à faire un certain nombre de parties aléatoires après chaque coup possible, à
mémoriser les résultats de ces parties et à faire une moyenne des résultats des parties pour
chaque coup possible. Le coup choisi est celui qui a la meilleur moyenne.
Exercice : É crire un algorithme de Monte-Carlo basique se reposant sur la classe Go.
Recherche arborescente Monte-Carlo
joueurs de Go en extrême orient, et des centaines de joueurs professionnels. Le jeu de
Go est un jeu à information parfaite et à somme nulle entre deux joueurs : Blanc et Noir.
Un damier de Go (Goban) est une grille 19xl9, qui est vide au début de la partie et que
les joueurs remplissent tour à tour en posant une pierre sur une intersection. Le nombre
moyen de coups possibles est de l 'ordre de 250, et les parties peuvent facilement durer
200 coups. D ' un point de vue programmation , les difficultés viennent à la fois du grand
nombre de coups possibles, qui rend une approche combinatoire par force brute de type
Alpha-Bêta inadaptée ; elles viennent aussi de la complexité de l'év aluation d' une position
et de la définition ambiguë de la fin de la partie (en utilisant des règles non ambiguës, les
parties dureraient plus de 350 coups). Les meilleurs joueurs de Go sont 9ème Dan et les
débutants sont 20ème kyu. Plus un joueur a un grade élevé en Dan plus il est fort, plus
un joueur à un petit nombre de kyus plus il est fort. Un joueur premier kyu qui progresse
devient premier Dan.
Un des nombreux intérêts de la programmation du jeu de Go d' un point de vue de
! ' Intelligence Artificielle [12] est qu'on peut très facilement comparer deux programmes
en les faisant jouer l ' un contre l ' autre. Et les programmeurs de Go ne s 'en privent pas. De
nombreux tournois de programmes sont régulièrement organisés.
Les méthodes de Monte-Carlo permettent d' écrire un programme de Go av ec très
peu de connaissances ; de plus l ' approche Monte-Carlo réagit bien à l ' augmentation de la
puissance de calcul, alors que les approches précédentes de la programmation du jeu de
Go utilisaient beaucoup de connaissances et ne réagissaient pas bien à l ' augmentation de
puissance de calcul.
Afin d' écrire un programme de Monte-Carlo Go on doit effectuer des parties aléatoires. La connaissance minimale à av oir pour jouer ces parties est de jouer des coups
légaux et ne pas se boucher les yeux. I! est tout à fait remarquable qu' un programme qui
dispose de si peu de connaissances du jeu soit capable de mieux jouer que des programmes
qui ont de grandes quantités de connaissances.
Exercice : É crire un classe Go qui permettent de jouer des parties aléatoires de Go.
5.3 Algorithme basique de Monte-Carlo
Maintenant qu'on dispose d' une classe permettant de jouer des parties aléatoires de
Go, il dev ient simple d'écrire un algorithme de Monte-Carlo basique. Cela consiste simplement à faire un certain nombre de parties aléatoires après chaque coup possible, à
mémoriser les résultats de ces parties et à faire une moyenne des résultats des parties pour
chaque coup possible. Le coup choisi est celui qui a la meilleur moyenne.
Exercice : É crire un algorithme de Monte-Carlo basique se reposant sur la classe Go.