96
Recherche arborescente Monte-Carlo
partie aléatoire contient le coup, à n ' importe quel moment de la partie. Cette heuristique
s ' appelle AMAF (Ail Moves As First).
L' algorithme RAVE (Rapid Action Value Estimation) [36) combine la valeur AMAF
d' un coup avec la moyenne des parties commençant par ce coup en utilisant un paramètre
/3 qui décroît progressivement de 1 à O. Ceci permet de commencer par évaluer un coup
avec la valeur AMAF lorsqu' il y a peu de parties aléatoires. En effet la valeur AMAF
donne de meilleures estimations que la moyenne lorsque le nombre de parties aléatoires
est petit. En revanche, lorsque le nombre de simulations augmente, la moyenne donne
alors une meilleur estimation. On passe donc progressivement de la valeur AMAF à la
moyenne lorsque le nombre de parties aléatoires augmente. L' intérêt d'un coup est donc
estimé avec la formule suivante :
/3 X AM AF + (LO - /3) X µi
/3 est calculé à partir de s le nombre de parties aléatoires du coup, de sa le nombre de
fois que le coup a été pris en compte par l' heuristique AMAF, et d' une constante C1. La
formule pour /3 est :
/3 _
sa
- sa+s+C1 xsaxs
RAVE utilise cette formule à la place de la formule UCB pour choisir le coup à explorer lors de la descente de l ' arbre au début de chaque simulation.
5.8 Développements
La recherche arborescente Monte-Carlo connaît de très nombreux développements.
Au Go, la formule RAVE a encore été améliorée en initialisation des feuilles avec quelques
parties gagnées pour les coups jugés prometteurs. On introduit un troisième terme en plus
de RAVE avec un coefficient 'Y qui diminue très vite avec le nombre de simulations.
Une voie très prometteuse est d' introduire des biais dans les partie aléatoires. Plutôt
que d' utiliser des parties complètement aléatoires, il est meilleur de jouer les coups avec
des urgences différentes qui dépendent de la configuration locale au coup [44) .
Les techniques de Monte-Carlo ont aussi été appliquées avec succès à d' autres jeux.
Par exemple au Hex, elles donnent de très bons résultats, l 'heuristique RAVE donne des
résultats encore meilleurs qu' au Go car tous les coups commutent au Hex ce qui n 'est pas
le cas du Go.
La recherche arborescente Monte-Carlo peut être appliquée à des jeux pour lesquels
on dispose d' une bonne fonction d'évaluation. Le principe est de jouer un petit nombre
Recherche arborescente Monte-Carlo
partie aléatoire contient le coup, à n ' importe quel moment de la partie. Cette heuristique
s ' appelle AMAF (Ail Moves As First).
L' algorithme RAVE (Rapid Action Value Estimation) [36) combine la valeur AMAF
d' un coup avec la moyenne des parties commençant par ce coup en utilisant un paramètre
/3 qui décroît progressivement de 1 à O. Ceci permet de commencer par évaluer un coup
avec la valeur AMAF lorsqu' il y a peu de parties aléatoires. En effet la valeur AMAF
donne de meilleures estimations que la moyenne lorsque le nombre de parties aléatoires
est petit. En revanche, lorsque le nombre de simulations augmente, la moyenne donne
alors une meilleur estimation. On passe donc progressivement de la valeur AMAF à la
moyenne lorsque le nombre de parties aléatoires augmente. L' intérêt d'un coup est donc
estimé avec la formule suivante :
/3 X AM AF + (LO - /3) X µi
/3 est calculé à partir de s le nombre de parties aléatoires du coup, de sa le nombre de
fois que le coup a été pris en compte par l' heuristique AMAF, et d' une constante C1. La
formule pour /3 est :
/3 _
sa
- sa+s+C1 xsaxs
RAVE utilise cette formule à la place de la formule UCB pour choisir le coup à explorer lors de la descente de l ' arbre au début de chaque simulation.
5.8 Développements
La recherche arborescente Monte-Carlo connaît de très nombreux développements.
Au Go, la formule RAVE a encore été améliorée en initialisation des feuilles avec quelques
parties gagnées pour les coups jugés prometteurs. On introduit un troisième terme en plus
de RAVE avec un coefficient 'Y qui diminue très vite avec le nombre de simulations.
Une voie très prometteuse est d' introduire des biais dans les partie aléatoires. Plutôt
que d' utiliser des parties complètement aléatoires, il est meilleur de jouer les coups avec
des urgences différentes qui dépendent de la configuration locale au coup [44) .
Les techniques de Monte-Carlo ont aussi été appliquées avec succès à d' autres jeux.
Par exemple au Hex, elles donnent de très bons résultats, l 'heuristique RAVE donne des
résultats encore meilleurs qu' au Go car tous les coups commutent au Hex ce qui n 'est pas
le cas du Go.
La recherche arborescente Monte-Carlo peut être appliquée à des jeux pour lesquels
on dispose d' une bonne fonction d'évaluation. Le principe est de jouer un petit nombre