188
Méthodes de Monte-Carlo pour le s jeux à un joueur
FIGURE 11.1 - A chaque étape d'une recherche de niveau n, on fait une recherche de
niveau n - 1 (lignes ondulées) pour chaque coup possible, puis on choisit le meilleur.
Algorithm 10 Jouer une partie aléatoire
playout (position)
while not partie terminée do
position +--- joue (position, coup aléatoire)
end while
return score (position)
l pour un arbre de hauteur h et d'arité a.
11.3 Le problème du choix du coup à gauche
Pour comprendre le fonctionnement de la recherche Monte-Carlo imbriquée, nous
allons l'analyser sur deux problèmes très simples. L'espace de recherche de ces deux
problèmes peut être représenté comme un arbre binaire. A chaque étape il y a deux coups
possibles : aller à gauche ou aller à droite.
11.3.1 Le nombre de coups sur le chemin le plus à gauche
3
2 1
1 0
0 0
0
FIGURE 11.2- Le score d'une partie est le nombre de coups sur le chemin le plus à gauche