Recherche arborescente Monte-Carlo MCTS
Algorithme de recherche qui construit un arbre de jeu à coups de simulations aléatoires et concentre son temps là où le gain semble le meilleur.
Quatre étapes répétées : choisir un chemin dans l'arbre, développer un nouveau nœud, jouer la partie au hasard jusqu'à la fin, puis remonter le résultat vers le haut. La sélection est généralement pilotée par UCB1, qui équilibre l'exploration de coups inconnus et l'approfondissement des coups prometteurs.
Elle ne nécessite aucune fonction d'évaluation écrite à la main, ce qui a été déterminant pour le go, où personne ne savait en écrire une bonne. AlphaGo a combiné MCTS et réseaux de neurones pour piloter à la fois la sélection et l'évaluation.