Recherche arborescente Monte-Carlo

La recherche arborescente Monte-Carlo, abrégée MCTS, ne tente pas d'examiner toutes les variantes à la même profondeur. Elle développe progressivement un arbre et utilise les résultats accumulés pour choisir où consacrer la prochaine portion de calcul. Un coup très visité n'est pas automatiquement bon, mais son estimation repose généralement sur davantage de recherche.

Un cycle de MCTS

1. Sélection: partir de la position initiale et suivre les branches existantes en équilibrant les coups qui semblent déjà forts avec ceux qui restent incertains.
2. Expansion: ajouter une position ou un coup que l'arbre n'a pas encore développé.
3. Évaluation: estimer le résultat depuis la nouvelle position. Les méthodes classiques peuvent achever des parties simulées, tandis que les systèmes modernes peuvent employer un réseau neuronal, modèle entraîné à reconnaître des motifs, pour l'évaluer.
4. Rétropropagation: ramener le résultat le long du chemin parcouru et mettre à jour le nombre de visites ainsi que les estimations.

La répétition de ce cycle équilibre exploitation et exploration. L'exploitation consiste à consacrer davantage d'effort aux zones où les indications sont déjà favorables. L'exploration consiste à tester des alternatives incertaines afin de ne pas rejeter trop tôt une surprise. La règle exacte qui les équilibre dépend de l'implémentation.

Contrairement à minimax, MCTS décide généralement dans quelle mesure explorer une branche à partir des informations recueillies pendant la recherche, plutôt qu'en fonction d'une profondeur uniforme seulement. Dans certains programmes d'échecs fondés sur des réseaux neuronaux, un réseau fournit une politique, qui suggère les coups probables, et une valeur, qui estime le résultat. Cette valeur joue un rôle apparenté à celui d'une fonction d'évaluation, même si le processus de recherche global est différent.