Nested Monte-Carlo Search

Tristan CazenaveIJCAI 2009 · OpenReview

Abstract

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16×16 Sudoku.

Introduction

In many complex problems—from logistics to board games—the number of possible states is so astronomical that exhaustive search is impossible. Usually, we rely on "heuristics" (rules of thumb) to guide the search toward promising areas. But what happens when we don't have a good heuristic?

Standard Monte-Carlo methods use random "playouts" (playing a game to the end with random moves) to estimate the value of a position. While useful, pure randomness often fails to find deep, high-scoring paths in complex puzzles. Nested Monte-Carlo Search (NMCS) tackles the challenge of guiding a search toward better states using only these random playouts as a foundation.

The NMCS Algorithm

The core innovation is Nested Monte-Carlo Search (NMCS). It works through recursive levels of "intelligence":

  • Level 0: A purely random playout from the current position to the end.
  • Level $n$: To decide the next move, the algorithm tries every possible move available. For each move, it runs a Level $n-1$ search. It then chooses the move that yielded the highest score at the lower level.
  • Memorization: Because the searches are randomized, a Level 2 search might accidentally find a worse result than a previous Level 1 search. To prevent this "regression," the algorithm always remembers the best sequence of moves found so far and follows it if the new randomized searches fail to improve upon it.

This nesting allows the algorithm to optimize moves at every stage of the game, not just near the starting position.

Key Insights: Bootstrapping and Memory

Even without a heuristic, the nesting effect creates a "gradient" of quality. A Level 1 search is significantly smarter than Level 0, and Level 2 is smarter still. This is clearly visible in the score distributions for different levels when memorization is employed.

Score distributions for levels 0 to 3 with memorization. Higher levels show a clear shift towards higher scores.

Randomness is a double-edged sword. Without memorizing the "best sequence," higher-level searches can actually perform worse than lower-level ones because they might "miss" a lucky high-scoring path found previously. Memorization ensures that increasing the search level always leads to better mean scores. This effect ensures that the probability distributions for higher levels are clearly separated and shifted toward higher scores.

Experimental Results

The algorithm was evaluated on three distinct, difficult problems:

  1. Morpion Solitaire (Disjoint version): NMCS found a new world record of 80 moves for the disjoint version. For context, the best human score at the time was 68.
  2. SameGame: A Level 3 NMCS achieved a total score of 77,934, outperforming the previous state-of-the-art algorithm, SP-MCTS, which scored 73,998.
  3. 16x16 Sudoku: On difficult 16x16 grids, NMCS (Level 1) solved problems in 1.34 seconds on average. Traditional "Forward Checking" was unable to solve 21% of the problems even after 20,000 seconds per problem.
Mean scores over time for different nesting levels. Higher levels maintain a performance advantage as search time increases.

Conclusion

The primary limitation of NMCS is computational cost, as each level of nesting increases time complexity exponentially. However, the paper demonstrates that NMCS is a powerful "anytime" algorithm. As shown in the performance scaling over time, it can be stopped at any point to provide the best result found so far, making it a robust choice for problems where heuristics are unavailable or unreliable.

Summary updated

Abstract

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16×16 Sudoku.
BibTeX
@inproceedings{cazenave2009nested,
  author = {Tristan Cazenave},
  title = {{Nested Monte-Carlo Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=HkbYf7f_WH},
}
Figure