Chapitre 5
Recherche arborescente
Monte-Carlo
5.1 Introduction
Les méthodes de Monte-Carlo consistent à faire un grand nombre de parties aléatoires ou pseudo-aléatoires. Les résultats de ces parties sont ensuite utilisés pour choisir
le meilleur coup.
Les méthodes de Monte-Carlo ont récemment connu de nombreux développements
en programmation des jeux. Elles constituent la meilleure approche pour de nombreux
problèmes pour lesquels l'espace de recherche est grand et qui n'ont pas de fonction
d'évaluation naturelle et simple.
Le problème typique pour lequel les méthodes de Monte-Carlo sont adaptées est le
jeu de Go : l'espace de recherche est très grand et il n'existe pas de fonction d'évaluation
simple, si ce n'est la moyenne de parties aléatoires.
5.2 Le jeu de Go
"Le Go est un sale jeu aléatoire."
Maître Lim.
Le jeu de Go est un jeu chinois très ancien. Il est populaire en Corée, au Ja pon et en
Chine. Les générations successives de joueurs de Go ont accumulé une expérience énorme
du jeu tout au long de son histoire. Aujourd'hui on compte des dizaines de millions de