Recherche arborescente Monte-Carlo

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 pour prendre certaines prises 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[1] et les récents programmes informatiques de Go[2], suivis par les échecs et shogi[3], ainsi que les jeux vidéos en temps réel et les jeux à information incomplète tels que le poker[4].

Principe[modifier | modifier le code]

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 noeuds déjà explorés de l'arbre des possibles. Une feuille de cet arbre est soit une configuration finale (i.e. on sait si un des joueurs a gagné, ou s'il y a match nul), soit une configuration à partir de laquelle aucune simulation n'a encore été lancée. Dans chaque nœud, on stocke deux nombres : le nombre de simulations gagnantes dans une partie qui contient n, et le nombre de simulations totales. Chaque étape est composée de quatre phases[5].

  • Sélection. Depuis la racine, on sélectionne succcessivement des enfants jusqu'à atteindre une feuille. Dans cette phase, le choix des enfants est guidé par un compromis entre exploitation (aller vers un enfant qui a été prouvé comme prometteur) et exploration (aller visiter un autre enfant, qui a l'air moins prometteur mais qui pourrait l'être davantage). Dans l'exemple donné dans la figure, on choisit la feuille de droite (de profondeur 3).
  • Expansion: si cette feuille n'est pas finale, créer un enfant (ou plusieurs) en utilisant les règles du jeu et choisir l'un des enfants. Sur l'exemple, on ajoute cet enfant, marqué 0/0.
  • Simulation: simuler une exécution d'une partie au hasard depuis cet enfant, jusqu'à atteindre une configuration finale.
  • Backpropagation: utiliser le résultat de la partie au hasard et mettre à jour les informations sur la branche de la racine à cet enfant. Sur l'exemple, la partie était perdante. On incrémente donc uniquement le nombre de simulations totales sur la branche : 12/21 devient 12/22, 7/10 devient 7/11, 5/6 devient 5/7, 3/3 devient 3/4 et 0/0 devient 0/1. Si la partie avait été gagnante, on aura eu :12/21 devient 13/22, 7/10 devient 8/11, 5/6 devient 6/7, 3/3 devient 4/4 et 0/0 devient 1/1.
Étapes d'un MCTS.

Exploitation et exploration[modifier | modifier le code]

La difficulté principale est dans la phase de sélection. Il faut choisir un enfant et maintenir un compromis entre l'exploitation des choix qui ont l'air prometteurs et l'exploration des noeuds desquelles 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[6]. UCT est basé sur la formule UCB1 de Auer, Cesa-Bianchi et Fischer[7] et l'algorithme AMS (Adaptive Multi-stage Sampling) a été appliqué à la décision multi-étage par Chang, Fu, Hu, et Marcus[8]. Kocsis et Szepesvári recommande de choisir le successeur i, en chaque nœud de l'arbre, pour lequel l'expression a la valeur maximale. Dans cette formule :

  • w est le nombre de parties gagnés marqué dans le successeur i
  • n est le nombre de fois que le successeur i a été visité
  • N est le nombre de fois que le nœud, père de i, a été visité
  • c est le paramètre d'exploration — en théorie égal à , en pratique, choisi expérimentalement.

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 sucesseurs 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.[8],[9] (2005) à Operations Research.

Comparaison avec d'autres approches[modifier | modifier le code]

Références[modifier | modifier le code]

  1. « Monte-Carlo Tree Search in TOTAL WAR: ROME II’s Campaign AI », sur AI Game Dev (consulté le 25 février 2017)
  2. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel et Demis Hassabis, « Mastering the game of Go with deep neural networks and tree search », Nature, vol. 529, no 7587,‎ , p. 484–489 (ISSN 0028-0836, PMID 26819042, DOI 10.1038/nature16961, Bibcode 2016Natur.529..484S, lire en ligne)Accès payant
  3. (en) Auteur inconnu « Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm », {{{year}}}.
  4. Jonathan Rubin et Ian Watson, « Computer poker: A review », Artificial Intelligence, vol. 175, nos 5–6,‎ , p. 958–987 (DOI 10.1016/j.artint.2010.12.005, lire en ligne)
  5. G.M.J.B. Chaslot, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik et B. Bouzy, « Progressive Strategies for Monte-Carlo Tree Search », New Mathematics and Natural Computation, vol. 4, no 3,‎ , p. 343–359 (DOI 10.1142/s1793005708001094, lire en ligne)
  6. Levente Kocsis et Csaba Szepesvári (2006). « Bandit based Monte-Carlo Planning » Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18–22, 2006, Proceedings 4212: 282–293 p., Springer (DOI:10.1007/11871842_29). 
  7. Peter Auer, Nicolò Cesa-Bianchi et Paul Fischer, « Finite-time Analysis of the Multiarmed Bandit Problem », Machine Learning, vol. 47,‎ , p. 235–256 (DOI 10.1023/a:1013689704352, lire en ligne)

    Le modèle {{dead link}} doit être remplacé par {{lien brisé}} selon la syntaxe suivante :
    {{ lien brisé | url = http://example.com | titre = Un exemple }} (syntaxe de base)
    Le paramètre url est obligatoire, titre facultatif.
    Le modèle {{lien brisé}} est compatible avec {{lien web}} : il suffit de remplacer l’un par l’autre.

  8. a et b Hyeong Soo Chang, Michael C. Fu, Jiaqiao Hu et Steven I. Marcus, « An Adaptive Sampling Algorithm for Solving Markov Decision Processes », Operations Research, vol. 53,‎ , p. 126–139 (DOI 10.1287/opre.1040.0145, lire en ligne)
  9. Hyeong Soo Chang, Michael Fu, Jiaqiao Hu et Steven I. Marcus, « Google DeepMind's Alphago: O.R.'s unheralded role in the path-breaking achievement », INFORMS, vol. 45, no 5,‎ , p. 24–29 (lire en ligne)

Bibliographie[modifier | modifier le code]

  • Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton, « A Survey of Monte Carlo Tree Search Methods », IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no 1,‎ (lire en ligne)

Lien externe[modifier | modifier le code]