La recherche arborescente Monte Carlo (MCTS) est un algorithme de recherche heuristique dans un arbre, utilisé pour les processus de décision, en particulier dans les logiciels qui jouent à des jeux de société. Elle résout l'arbre de jeu en se concentrant sur les coups les plus prometteurs, en développant l'arbre de recherche sur la base d'un échantillonnage aléatoire de l'espace de recherche. La MCTS a été combinée avec des réseaux neuronaux en 2016 et a depuis été appliquée à des jeux comme les échecs, le shogi, les dames, le backgammon, le bridge contrat, le go, le Scrabble et le Clobber, ainsi qu'à des jeux vidéo de stratégie au tour par tour et à d'autres domaines.
L'algorithme fonctionne par des simulations répétées, ou roll-outs, où les parties sont simulées jusqu'à leur terme avec des coups aléatoires. Les résultats de ces simulations sont utilisés pour pondérer les nœuds de l'arbre de jeu, guidant les sélections futures vers des coups plus prometteurs. Chaque cycle de MCTS comprend quatre étapes : la sélection, l'expansion, la simulation et la rétropropagation.
Historique
La méthode de Monte Carlo, qui utilise un échantillonnage aléatoire pour des problèmes déterministes, remonte aux années 1940. En 1987, Bruce Abramson a combiné la recherche minimax avec un modèle de résultat attendu basé sur des simulations aléatoires de parties, démontrant son efficacité sur le tic-tac-toe et d'autres jeux. En 1989, W. Ertel, J. Schumann et C. Suttner ont appliqué des méthodes similaires à la démonstration automatique de théorèmes, améliorant les temps de recherche. En 1992, B. Brügmann a utilisé cette approche dans un programme jouant au go. En 2002, Chang et al. ont proposé l'échantillonnage adaptatif multi-étapes (AMS), qui a introduit l'exploration et l'exploitation basées sur l'UCB dans les arbres de Monte Carlo, posant les bases de l'UCT.
En 2006, Rémi Coulom a inventé le terme de recherche arborescente Monte Carlo, tandis que L. Kocsis et Cs. Szepesvári ont développé l'algorithme UCT (Upper Confidence bounds applied to Trees). S. Gelly et al. ont implémenté l'UCT dans le programme MoGo, qui a atteint le niveau dan en go 9x9 d'ici 2008. En 2012, le programme Zen a remporté un match contre un joueur amateur 2 dan sur un plateau 19x19. AlphaGo de Google DeepMind, utilisant la MCTS avec des réseaux neuronaux, est devenu le premier programme à battre un joueur professionnel humain de go en 2015 et a vaincu Lee Sedol en 2016.
Principe de fonctionnement
L'accent de la MCTS est mis sur l'analyse des coups les plus prometteurs en développant l'arbre de recherche sur la base d'un échantillonnage aléatoire. Chaque simulation joue une partie jusqu'à son terme, et les résultats pondèrent les nœuds afin que les meilleurs coups soient choisis plus fréquemment. La recherche de jeu Monte Carlo pure de base applique des simulations égales à chaque coup légal et sélectionne le coup avec le plus de victoires.
Chaque cycle de MCTS comprend quatre étapes :
- Sélection : En partant de la racine, sélectionner des nœuds enfants successifs jusqu'à atteindre un nœud feuille.
- Expansion : Créer un ou plusieurs nœuds enfants à partir de la feuille, sauf si la partie est décidée.
- Simulation : Effectuer une simulation aléatoire complète à partir du nouveau nœud.
- Rétropropagation : Mettre à jour les statistiques des nœuds le long du chemin du nouveau nœud à la racine.
Algorithme UCT
L'algorithme UCT équilibre l'exploration et l'exploitation en utilisant la formule de la borne de confiance supérieure. Il sélectionne les nœuds enfants en fonction de leur taux de victoire moyen et d'un bonus pour les nœuds moins visités, permettant à l'arbre de s'étendre vers des coups prometteurs tout en explorant des alternatives. Cette approche est centrale pour l'efficacité de la MCTS.
Applications
La MCTS a été utilisée dans des programmes pour des jeux de société comme Hex, Havannah, le jeu des Amazones et Arimaa, ainsi que pour des jeux vidéo en temps réel comme Ms. Pac-Man et Fable Legends. Elle s'applique également à des jeux non déterministes comme le skat, le poker, Magic: The Gathering et les Colons de Catane. Au-delà des jeux, la MCTS a été explorée dans des problèmes de planification et d'optimisation.
Importance
La combinaison de la MCTS avec des réseaux neuronaux profonds, comme dans AlphaGo, a marqué une étape importante dans l'intelligence artificielle et le apprentissage automatique. Elle a démontré comment la recherche heuristique peut être intégrée à des méthodes de apprentissage profond pour atteindre des performances surhumaines dans des domaines complexes, influençant les recherches ultérieures dans le IA générative et d'autres domaines.