I have heard about this concept in a Reddit post about AlphaGo. 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?
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))
