Saturday, May 25, 2013

Monte Carlo Tree Seach

Recently I have made great progress on my AI project, so today I will attempt to wake this sleepy blog from hibernation.

While I had heard about the success of Monte Carlo Tree Search applied to Go and other games a few years ago, it was only about a month ago that I became aware that in its basic form the algorithm is domain independent. It is therefore very suitable for my goal of making general game playing AI that doesn't need to be taught the rules of the games played.

For the necessary background knowledge and a great introduction to the algorithm and its variations, "A Survey of Monte Carlo Tree Search Methods" is a great resource. This paper also includes pseudo-code for the basic algorithm.

In essence, MCTS plays thousands of games to completion taking random moves to get there. The resulting win, loss or draw of each game then informs the algorithm which parts of the search tree to explore further. This combination of random moves and statistical analysis makes the algorithm applicable to a large range of domains and also means it scales well to harder problems - the more CPU time you give it, the better the result will be.



Because the algorithm plays the games to completion, it only needs to be informed about which moves are valid for each turn and whether the game resulted in a win, loss or draw at the end. No other domain-specific knowledge is required.

Is this the end of my genetic programming approach? Quite the opposite, I will be exploring combining the two approaches in the near future.

To try out MCTS, I implemented the basic algorithm and applied it to Tic Tac Toe. After a couple of hours of coding I was ready to play against it...and...it plays extremely well! If the agent starts, it appears impossible to win against it. It sets up clever double win strategies so the best a human opponent can hope for is a draw. I was very impressed!

It is time to move on to the slightly more complex game of Connect 4...

No comments:

Post a Comment