Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Recherche arborescente Monte-Carlo
Résumé
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.
Sélection. Depuis la racine, on sélectionne successivement 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 gauche (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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.