5.4 UCB
93
5.4 UCB
"Lorsque vous avez trouvé un bon coup, cherchez-en un meilleur. "
Pedro Damiano.
Plutôt que de faire un nombre égal de simulations pour chaque coup possible, il est
plus judicieux d' utiliser les résultats des simulations précédentes pour savoir quels ont
été les meilleurs coups jusqu' ici de façon à les essayer plus que les coups qui semblent
mauvais. To utefois si on privilégie toujours le meilleur coup, on peut oublier des coups
pour lesquels les premières simulations se sont mal passées mais qui sont tout de même
bons et qui révélerait tout leur potentiel si on leur donnait plus de simulations. On est
fac e à un dilemme exploration/exploitation : on veut faire plus de simulations pour les
coups qui nous semble les meilleurs de façon à diminuer l' incertitude sur leur qualité, on
exploite donc les coups qui nous semblent les meilleurs, mais on veut aussi explorer ceux
qui nous semblent moins bons au cas où ils seraient en réalité meilleurs.
Un algorithme qui permet un bon équilibre entre exploration et exploitation est UCB
(Upper Confidence Bound). Il consiste à choisir le coup qui maximise la fonction µi +
C x Jlog(p)/Pi où µi est la moyenne des parties commençant par le coup Ci, p est le
nombre de parties jouées et Pi est le nombre de parties commençant par le coup Ci · C est
une constante qu' il faut régler pour l ' adapter au domaine auquel l ' algorithme est appliqué. Une constante élevée favorisera l ' exploration alors qu' une petit constante favorisera
l ' exploitation. Pour des résultats compris entre 0 et 1, choisir une constante de l ' ordre de
0.3 est un bon compromis dans de nombreux jeux.
Exercice : É crire un algorithme UCB pour jouer au Go.
5.5 UCT
On cherche maintenant à développer un arbre à partir de la position initiale, dont
chaque nouvelle feuille sera évaluée par une partie aléatoire. À chaque nouvelle partie
aléatoire, le programme commencera par descendre l ' arbre jusqu' à ce qu' il crée une nouvelle feuille. Une fois la partie aléatoire terminée, les valeurs moyennes de tous les noeuds
de l' arbre par lesquels la partie aléatoire est passée seront mises à jour avec le résultat de
la partie aléatoire.
Pour descendre l ' arbre on choisit à chaque niveau le coup à jouer avec la formule
UCB , c 'est pourquoi l ' algorithme s ' appelle UCT (UCB applied to Trees).
La figure 5.1 donne les quatre étapes de l ' algorithme UCT. La première étape consiste
à descendre l ' arbre en utilisant la politique UCB. La deuxième étape est d' aj outer une
nouvelle feuille en dessous du dernier noeud atteint par la descente de l ' arbre. La troisième
étape est de jouer une partie aléatoire à partir de la position atteinte à cette nouvelle feuille.
93
5.4 UCB
"Lorsque vous avez trouvé un bon coup, cherchez-en un meilleur. "
Pedro Damiano.
Plutôt que de faire un nombre égal de simulations pour chaque coup possible, il est
plus judicieux d' utiliser les résultats des simulations précédentes pour savoir quels ont
été les meilleurs coups jusqu' ici de façon à les essayer plus que les coups qui semblent
mauvais. To utefois si on privilégie toujours le meilleur coup, on peut oublier des coups
pour lesquels les premières simulations se sont mal passées mais qui sont tout de même
bons et qui révélerait tout leur potentiel si on leur donnait plus de simulations. On est
fac e à un dilemme exploration/exploitation : on veut faire plus de simulations pour les
coups qui nous semble les meilleurs de façon à diminuer l' incertitude sur leur qualité, on
exploite donc les coups qui nous semblent les meilleurs, mais on veut aussi explorer ceux
qui nous semblent moins bons au cas où ils seraient en réalité meilleurs.
Un algorithme qui permet un bon équilibre entre exploration et exploitation est UCB
(Upper Confidence Bound). Il consiste à choisir le coup qui maximise la fonction µi +
C x Jlog(p)/Pi où µi est la moyenne des parties commençant par le coup Ci, p est le
nombre de parties jouées et Pi est le nombre de parties commençant par le coup Ci · C est
une constante qu' il faut régler pour l ' adapter au domaine auquel l ' algorithme est appliqué. Une constante élevée favorisera l ' exploration alors qu' une petit constante favorisera
l ' exploitation. Pour des résultats compris entre 0 et 1, choisir une constante de l ' ordre de
0.3 est un bon compromis dans de nombreux jeux.
Exercice : É crire un algorithme UCB pour jouer au Go.
5.5 UCT
On cherche maintenant à développer un arbre à partir de la position initiale, dont
chaque nouvelle feuille sera évaluée par une partie aléatoire. À chaque nouvelle partie
aléatoire, le programme commencera par descendre l ' arbre jusqu' à ce qu' il crée une nouvelle feuille. Une fois la partie aléatoire terminée, les valeurs moyennes de tous les noeuds
de l' arbre par lesquels la partie aléatoire est passée seront mises à jour avec le résultat de
la partie aléatoire.
Pour descendre l ' arbre on choisit à chaque niveau le coup à jouer avec la formule
UCB , c 'est pourquoi l ' algorithme s ' appelle UCT (UCB applied to Trees).
La figure 5.1 donne les quatre étapes de l ' algorithme UCT. La première étape consiste
à descendre l ' arbre en utilisant la politique UCB. La deuxième étape est d' aj outer une
nouvelle feuille en dessous du dernier noeud atteint par la descente de l ' arbre. La troisième
étape est de jouer une partie aléatoire à partir de la position atteinte à cette nouvelle feuille.