15
$\begingroup$

I have heard about this concept in a Reddit post about Alpha Go. I have tried to go through the paper and the article, but could not really make sense of the algorithm.

So, can someone give an easy-to-understand explanation of how the Monte-Carlo search algorithm work and how is it being used in building game-playing AI bots?

$\endgroup$
12
$\begingroup$

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances.

As an example, you could use it for weather forecasts. Predicting long-term weather is quite difficult, because it is a chaotic system where small changes can lead to very different results. Using Monte Carlo methods, you could run a large number of simulations, each with slightly different atmospheric changes. Then you can analyze the results and for example calculate the probability of rain on a given day based on how many simulations ended up with rain.

As for the use of Monte Carlo in Alpha Go, they seem to be using the so-called Monte Carlo Tree Search. In this approach, you make a tree of possible moves, a few turns into the future, and try to find the best sequence. However, since the number of possible moves in the game of go is very large, you won't be able to explore very far ahead. This means that some of the moves which look good now might turn out to be bad later.

So, in the Monte Carlo Tree Search, you pick a promising sequence of moves and run one or more simulations of how the game might proceed from that point. Then you can use the results of that simulation to get a better idea of how good that specific sequence of moves really is and you update the tree accordingly. Repeat as needed until you find a good move.

If you want more information or to look at some illustrations, I found an interesting paper on the topic: C. Browne et al., A Survey of Monte Carlo Tree Search Methods (open repository / permanent link (paywalled))

$\endgroup$
  • $\begingroup$ So basically what monte carlo does in alphago is to create long term strategies , by considering different move combinations , instead of the other way around ( pick an strategy and then the moves to achieve it ) ? $\endgroup$ – Diego Antonio Rosario Palomino Apr 24 '18 at 4:13
  • $\begingroup$ There's no mention of the key element of the Monte Carlo approach, which is the stochastic element integrated into the selection of available moves to investigate. Neither was the trade-off of exactness to achieve leaner processing mentioned. Those are the most important two aspects and are absent from the answer. Instead, "large number of random values or simulations," was mentioned, when it is a smaller number of simulations from pseudo-random factors (a less exhaustive search) that is characteristic of Monte Carlo convergence. $\endgroup$ – FauChristian Jul 11 '18 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.