Monte Carlo Tree Search (MCTS) is a heuristic search algorithm that can make game play decisions. It does this by attempting to determine the most promising move from those available. What’s interesting is that the algorithm just needs to know the game rules and winning conditions, it doesn’t need domain knowledge. Another advantage is that it can be interrupted or constrained by a time limit and will produce the most promising move found so far.
I built a Tic Tac Toe player a couple of years ago and while upgrading Unity recently I thought I’d try building it for the web so I built a WebGL version.
A short video showing an older version of the program:
The source code is up in GitHub at https://github.com/acharraggi/MCTS4. The game and MCTS code is in the scripts folder https://github.com/acharraggi/MCTS4/tree/master/Assets/scripts.
I was interesting in learning a bit about C# so that’s what this is written in. In addition to the MCTS code I also wrote some code to display the search tree after each move so one could look at it prior to the computer completing it’s move. Some domain code was added as the most promising move often ignored traps. For example a promising move might lead to a position where there were several downstream possible wins, but the opponent might have a direct winning move.
Click here to try it. Opens in a new window.
Be patient, there’s a 90MB download and then a rather long pause before game play starts. Starting player is randomly assigned after you click the Start button. If it’s your turn just click on the square you want to select. If it’s the computer’s turn the game pauses and display three buttons “More MCTS”, “Show Tree”, and “Accept:x” where x the number of a square. “More MCTS” runs another round of simulations which might change the answer, though I’ve tweaked things a bit so it’s probably not needed for such a simple game. “Show Tree” shows the current tree with nodes representing game state and the MCTS results so far. The “Accept:x” button completes the computer’s move and it becomes your turn. After there’s a win or draw you can play again, or close the browser window or go elsewhere to end the game.
I’d like to give this a try with a more interesting game like checkers, maybe some day.