Monte Carlo Tree Search

The UCB is a good algorithmn, until you realise that it can only see 1 move into the future. A strong player for any project has the ability to stratagise, by predicting into the future. Monte Carlo Tree Search takes this UCB algorithm and gives it the ability to see into the future, creating a stronger AI opponent at the cost of compute.

How it works

Monte Carlo tree search, as it’s name suggests, builds a tree of future states to calculate which state is the best. The algorithm works in 4 steps - Selection, Expansion, Simulation and Backpropogation

Selection

At the start of the search, the parent node looks to its children node, which consist of the legal connect 4 moves, e.g 7 children for each column you can place a piece in. If each child has already been simulated at least once, the child with the highest UCB score is chosen and the process repeats until you reach a node where not all future moves have been simulated.

Expansion

Once you reach a new unexplored node, you fist expand the node, creating children for each of the possible states the next move can take.

Simulation

Once you have reached a node where all the children aren’t explored, one of these children are chosen, and a random rollout takes place, similiarly to the UCB algorithm

Backpropogation

After simulation, the results of the simulation (win or loss or draw) go back up the tree, updating each parent node with the updated win score.

Decision making

After enough simulations, the child of the original state with the highest run count is chosen - as this is deemed to be the most promising node by the algorithm

Implementation

Implementing this algorithm from scartch was harder than expected, but also fun! The only problem was that for higher simulation counts, such as 1,000 or 10,000, it takes a good few seconds for the algorithm to make a decision. I also somehow broke my original connect 4 code when trying to implement this program. I ran 100 simulations of MCTS vs UCB, both with 1000 simulations each, and MCTS only won 20 more games than ucb. I moved MCTS simulation count to 10000 and it won most of the games played.