En informatique, et plus précisément en intelligence artificielle, la recherche arborescente Monte Carlo ou Monte Carlo tree search (MCTS) est un algorithme de recherche heuristique utilisé dans le cadre de la prise de décision. Il est notamment employé dans les jeux. On peut citer son implémentation dans le jeu vidéo Total War: Rome II avec son mode campagne IA haut-niveau et les récents programmes informatiques de Go, suivis par les échecs et shogi, ainsi que les jeux vidéo en temps réel et les jeux à information incomplète tels que le poker.
L'algorithme MCTS est un algorithme qui explore l'arbre des possibles. La racine est la configuration initiale du jeu. Chaque nœud est une configuration et ses enfants sont les configurations suivantes. MCTS conserve en mémoire un arbre qui correspond aux nœuds déjà explorés de l'arbre des possibles. Une feuille de cet arbre (un nœud n'ayant pas d'enfants) est soit une configuration finale (i.e. on sait si un des joueurs a gagné, ou s'il y a match nul), soit un nœud dont aucun enfant n'a encore été exploré. Dans chaque nœud, on stocke deux nombres : le nombre de simulations gagnantes, et le nombre total de simulations. Chaque étape est composée de quatre phases.

La difficulté principale est dans la phase de sélection. Il faut sélectionner successivement les enfants jusqu'à atteindre une feuille. Pour cela, on maintient un compromis entre l'exploitation des choix qui ont l'air prometteurs et l'exploration des nœuds à partir desquels peu de simulations ont été réalisées. La première formule pour ce compromis entre exploitation et exploration, qui s'appelle UCT (Upper Confidence Bound 1 applied to Trees) était introduit par Levente Kocsis et Csaba Szepesvári. UCT est basée sur la formule UCB1 de Auer, Cesa-Bianchi et Fischer et l'algorithme AMS (Adaptive Multi-stage Sampling) a été appliqué à la décision multi-étage par Chang, Fu, Hu, et Marcus. Kocsis et Szepesvári recommandent de choisir le successeur i, en chaque nœud de l'arbre, pour lequel l'expression a la valeur maximale. Dans cette formule :
La première partie de la formule, correspond à l'exploitation ; la fraction est grande pour les successeurs qui ont eu beaucoup de succès jusque là. La seconde partie correspond à l'exploration ; elle est grande pour des successeurs qui n'ont été impliqués que dans peu de simulations.
Les implémentations plus modernes de MCTS sont basées sur une variante de UCT, cf. les travaux de Chang et al., (2005) à Operations Research (en).
L'un des avantage de la recherche arborescente de Monte-Carlo par rapport à l'algorithme minimax est qu'il n'est pas nécessaire de disposer d'une bonne heuristique pour la fonction d'évaluation, puisque les simulations vont jusqu'à la profondeur maximale de l'arbre ; c'est l'une des causes de son succès dans les logiciels de go.