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 →