Recherche arborescente Monte Carlo
Comment choisir un coup quand je ne sais pas dire à quoi ressemble une bonne position ?
Joue des milliers de parties aléatoires à partir de chaque coup possible et favorise ceux qui ont le plus gagné, en développant l’arbre là où les résultats semblent prometteurs.
La recherche Monte Carlo n’a pas besoin de fonction d’évaluation. Elle juge un coup par l’expérience : jouer la partie jusqu’au bout avec des coups aléatoires, de nombreuses fois, et compter les victoires.
Un échantillonnage purement aléatoire gaspille l’effort sur les mauvais coups, donc les essais sont guidés. Chaque tour descend un arbre qui grandit et, à chaque position, choisit le coup qui équilibre deux choses : un bon taux de victoire jusqu’ici (exploitation) et peu d’essais jusqu’ici (exploration). La règle usuelle est l’UCT : taux de victoire plus c fois la racine carrée de ln N sur n.
Comme elle n’a besoin que des règles, elle marche là où noter une position à la main est difficile. Comme elle échantillonne, elle est aléatoire, et sa force croît avec le nombre de parties qu’on lui accorde.
Chargement de la démo…
Puissance 4 avec Monte Carlo sélectionné. Faites varier le nombre de parties aléatoires par coup et voyez comment le jeu de l’IA change.
- 01Sélection : depuis la racine, descendre vers l’enfant de plus grande valeur UCT jusqu’à une position qui a encore des coups non essayés.
- 02Expansion : ajouter un nouvel enfant pour l’un de ces coups.
- 03Simulation : depuis la nouvelle position, jouer des coups aléatoires jusqu’à la fin de la partie.
- 04Rétropropagation : ajouter le résultat (victoire, nul ou défaite) à chaque position du chemin jusqu’à la racine.
- 05Répéter pour le nombre de parties accordé, puis jouer le coup de la racine le plus visité.
function mcts(root, iterations):
for i in 1..iterations:
node = root
while is_fully_expanded(node) and not game_over(node):
node = argmax over c in children(node) of
c.wins / c.visits + C * sqrt(ln(node.visits) / c.visits)
if not game_over(node): node = add_child(node, random untried move)
result = random_playout(node.position)
for n from node up to root:
n.visits += 1
n.wins += result_for(n)
return argmax over c in children(root) of c.visitsN est le nombre de parties aléatoires, que vous choisissez. La force monte lentement avec lui, et la recherche peut être arrêtée à tout moment avec une réponse utilisable.
- Aucune fonction d’évaluation à concevoir ni à régler.
- Peut être arrêtée à tout moment en renvoyant un coup.
- S’accommode des jeux à beaucoup de coups par tour.
- Les parties aléatoires peuvent rater une tactique qu’une recherche courte voit tout de suite.
- La réponse change d’une exécution à l’autre.
- Un bon coup demande beaucoup de parties, donc elle peut être plus lente qu’un alpha-bêta bien ordonné.
- 01OthelloL’un des cinq adversaires. Sans évaluation à régler, c’est un bon contrôle de celle faite à la main.
- 02Puissance 4Juge chaque colonne par la fréquence des parties aléatoires qui commencent par elle et finissent par une victoire.