A generic implementation of a Nested Monte Carlo Search for single player games

A 15\times 15 initial SameGame board has an upper bound of 1.97\times 10^{182} reachable board positions.

Therefore it can be extremely difficult to solve, even for computers.

A very promising approach to solving complex problems such as SameGame is the Nested Monte Carlo Search (NMCS). It is a very simple variation from the family of Monte Carlo Search algorithms, especially suited for single player games.

In this post we will see a generic implementation of the NMCS in Java that can easily be adapted to different problem domains.

But before we come to that, let’s look at how the NMCS works.
Continue reading →