Comment fonctionne la «recherche Monte-Carlo»?

16

J'ai entendu parler de ce concept dans un article Reddit sur Alpha Go. J'ai essayé de parcourir l'article et l'article, mais je ne pouvais pas vraiment comprendre l'algorithme.

Alors, quelqu'un peut-il donner une explication facile à comprendre comment fonctionne l'algorithme de recherche Monte-Carlo et comment est-il utilisé dans la création de robots d'intelligence artificielle?

Dawny33
la source
Une belle description de l'algorithme MCTS peut être trouvée à: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nbro

Réponses:

13

La méthode de Monte-Carlo est une approche où vous générez un grand nombre de valeurs aléatoires ou de simulations et formez une sorte de conclusions en fonction des modèles généraux, tels que les moyennes et les variances.

À titre d'exemple, vous pouvez l'utiliser pour les prévisions météorologiques . Il est assez difficile de prédire la météo à long terme, car il s'agit d'un système chaotique où de petits changements peuvent conduire à des résultats très différents. En utilisant les méthodes de Monte Carlo, vous pouvez exécuter un grand nombre de simulations, chacune avec des changements atmosphériques légèrement différents. Ensuite, vous pouvez analyser les résultats et par exemple calculer la probabilité de pluie un jour donné en fonction du nombre de simulations qui ont abouti à la pluie.

Quant à l'utilisation de Monte Carlo dans Alpha Go, ils semblent utiliser la soi-disant Monte Tree Tree Search . Dans cette approche, vous faites un arbre de mouvements possibles, quelques tours dans le futur, et essayez de trouver la meilleure séquence. Cependant, comme le nombre de coups possibles dans le jeu de go est très important, vous ne pourrez pas explorer très loin. Cela signifie que certains des mouvements qui semblent bons maintenant peuvent se révéler mauvais par la suite.

Ainsi, dans Monte Carlo Tree Search, vous choisissez une séquence prometteuse de mouvements et exécutez une ou plusieurs simulations de la façon dont le jeu pourrait se dérouler à partir de ce point. Ensuite, vous pouvez utiliser les résultats de cette simulation pour avoir une meilleure idée de la qualité réelle de cette séquence de mouvements spécifique et mettre à jour l'arborescence en conséquence. Répétez au besoin jusqu'à ce que vous trouviez un bon coup.

Si vous voulez plus d'informations ou regarder quelques illustrations, j'ai trouvé un article intéressant sur le sujet: C. Browne et al., A Survey of Monte Carlo Tree Search Methods ( référentiel ouvert / lien permanent (paywalled) )

Rôdeur désenchanté
la source
Donc, fondamentalement, ce que Monte-Carlo fait dans alphago est de créer des stratégies à long terme, en considérant différentes combinaisons de mouvements, plutôt que l'inverse (choisissez une stratégie puis les mouvements pour y parvenir)?
Diego Antonio Rosario Palomino
Il n'y a aucune mention de l'élément clé de l'approche Monte Carlo, qui est l'élément stochastique intégré dans la sélection des mouvements disponibles à étudier. Le compromis de l'exactitude pour obtenir un traitement plus léger n'a pas non plus été mentionné. Ce sont les deux aspects les plus importants et sont absents de la réponse. Au lieu de cela, «un grand nombre de valeurs aléatoires ou de simulations» a été mentionné, quand c'est un plus petit nombre de simulations à partir de facteurs pseudo-aléatoires (une recherche moins exhaustive) qui est caractéristique de la convergence de Monte Carlo.
FauChristian