La recherche arborescente Monte Carlo (MCTS) est un algorithme de recherche heuristique dans un arbre, utilisé dans les processus de décision, en particulier dans les logiciels jouant à des jeux de plateau. 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 de contrat, le go, le Scrabble et le Clobber, ainsi qu'à des jeux vidéo de stratégie au tour par tour et à des applications non ludiques.
L'algorithme fonctionne par des simulations répétées, également appelées déroulements, où le jeu est joué jusqu'au bout 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, rendant les meilleurs nœuds plus susceptibles d'être choisis lors des simulations futures. Cette approche diffère de la recherche minimax traditionnelle en évitant une fonction d'évaluation statique, s'appuyant plutôt sur des résultats simulés.
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 jeux, démontrant sa précision et son indépendance vis-à-vis du domaine dans le tic-tac-toe, l'Othello et les échecs. 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 algorithmes de recherche non informés. En 1992, B. Brügmann a utilisé pour la première fois 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 nom 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 au go 9×9 en 2008. Le programme Fuego a également commencé à battre de forts amateurs au go 9×9 à cette époque. En janvier 2012, le programme Zen a gagné 3:1 contre un joueur amateur 2 dan sur un plateau 19×19.
Google DeepMind a développé AlphaGo, qui est devenu en octobre 2015 le premier programme à battre un joueur professionnel humain de go sans handicap sur un plateau de taille complète. En mars 2016, AlphaGo a battu Lee Sedol 4:1, obtenant un niveau honorifique de 9 dan. AlphaGo a combiné la MCTS avec des réseaux neuronaux artificiels, une méthode d'apprentissage profond, pour l'évaluation de la politique et de la valeur, marquant une étape importante dans l'apprentissage automatique.
Principe de fonctionnement
La MCTS se concentre sur l'analyse des coups les plus prometteurs en développant l'arbre de recherche sur la base d'un échantillonnage aléatoire. Chaque cycle comprend quatre étapes :
- Sélection : En partant du nœud racine (état de jeu actuel), sélectionner successivement des nœuds enfants jusqu'à atteindre un nœud feuille. La sélection est biaisée pour favoriser les coups prometteurs, souvent en utilisant l'UCT.
- Expansion : Sauf si le nœud feuille termine le jeu, créer un ou plusieurs nœuds enfants représentant des coups légaux.
- Simulation : Effectuer un déroulement aléatoire à partir d'un nœud enfant choisi, en jouant jusqu'à ce que le jeu soit décidé.
- Rétropropagation : Mettre à jour les nœuds sur le chemin de l'enfant à la racine avec le résultat du déroulement, en incrémentant les compteurs de simulations et de victoires de manière appropriée.
Dans les jeux avec des matchs nuls, un match nul incrémente le numérateur de 0,5 et le dénominateur de 1 pour les deux joueurs. Cela garantit que les choix de chaque joueur s'étendent vers les coups qui maximisent leur propre valeur.
Algorithme UCT
L'algorithme UCT, introduit en 2006, applique les bornes de confiance supérieures à la recherche arborescente. Il équilibre l'exploration et l'exploitation en sélectionnant les nœuds enfants en fonction de leur récompense moyenne et d'un bonus pour les nœuds moins visités. Cela permet à l'arbre de recherche de s'étendre vers les coups les plus prometteurs tout en explorant encore les alternatives. L'UCT est devenu la norme pour les implémentations de MCTS, y compris dans MoGo et les programmes ultérieurs.
Applications
La MCTS a été utilisée dans des programmes pour des jeux de plateau comme Hex, Havannah, le jeu des Amazones et Arimaa, ainsi que des jeux vidéo en temps réel comme Ms. Pac-Man et Fable Legends. Elle gère également des jeux non déterministes comme le Skat, le poker, Magic: The Gathering et les Colons de Catane. Dans les jeux de stratégie au tour par tour, Total War: Rome II utilise la MCTS dans son IA de campagne de haut niveau. Au-delà des jeux, la MCTS a des applications dans les problèmes de planification et d'optimisation.
La combinaison de la MCTS avec des réseaux neuronaux, comme dans AlphaGo, s'est avérée particulièrement efficace. Cette approche hybride utilise des réseaux neuronaux pour guider la sélection et évaluer les positions, réduisant le besoin de simulations aléatoires étendues. Des programmes ultérieurs comme AlphaZero ont étendu cette approche aux échecs et au shogi, atteignant des performances surhumaines.