11.3 Le problème du choix du coup à gauche
Algorithm 11 Recherche Monte-Carlo imbriquée
nested (position, ordre)
meilleur playout +--- {
}
while not partie terminée do
if ordre = 1 then
move +--- argmaxm (playout Uoue (position, m)))
el se
move +--- argmaxm (nested Uoue (position, m), ordre -1) )
end if
if score du playout apres le coup move > score du meilleur playout then
meilleur playout +--- playout apres le coup move
end if
position +--- joue (position, coup du meilleur playout)
end while
return score (position)
L'espace de recherche du problème à profondeur 3 est donné dans la figure 11.2.
189
Exercice: Quelle est la probabilité d'un playout de trouver la solution d'un problème
de profondeur n? Quelle est cette probabilité pour une recherche de niveau un ? Quelle
est la complexité d'une recherche de niveau un ?
11.3.2 Le nombre de coups à gauche
3
2 2
1 2
1 1
0
FIGURE 11. 3 - Le score est le nombre de coups à gauche
Un problème qui a une répartition plus proche des problèmes rééls est le problème du
nombre de coups à gauche. Le score d'une feuille est le nombre de coups à gauche joués
pour atteindre cette feuille. La figure 11. 3 donne un problème de profondeur trois.
Exercice: Quelle est la probabilité d'un playout de trouver la solution d'un problème
de profondeur n ? Quelle est cette probabilité pour une recherche de niveau l ?