A new Morpion Solitaire record via Monte-Carlo search

• [August 2011]: A new record for the standard (5T) Morpion Solitaire game, with 178 lines:

  

  This was obtained using an enhanced variation of the NRPA algorithm described in the IJCAI paper linked below.

• [May 2011]: A paper is available describing the new Nested Rollout Policy Adaptation (NRPA) algorithm used to obtain the new Morpion Solitaire records:
  • Rosin, C.D. (2011). Nested Rollout Policy Adaptation for Monte Carlo Tree Search. Proceedings of IJCAI 2011.
  The paper includes a new record for the standard (5T) Morpion Solitaire game, with 177 lines:

  

• [August 2010]: In the single-player game Morpion Solitaire, the player must select a legal move to add one line to a grid each turn. The goal is to add as many lines as possible before running out of legal moves. For the standard version of the game, a record solution of 170 lines was done by hand by Charles-Henri Bruneau and published in 1976, and this record still stood as of February 2010. Despite some recent progress using Monte Carlo search techniques, the best publicized computer search-based solution as of February 2010 had only 149 lines. See the morpionsolitaire.com Records page for details. It seems surprising that humans would still dominate Morpion Solitaire, since it is a problem domain with a simple complete description and it seems amenable to computer search.

  I am using Morpion Solitaire as one benchmark problem in the development of new Monte Carlo search techniques. These techniques have now yielded a new record solution for the standard (5T) Morpion Solitaire game, with 172 lines:

  

  In addition, these same techniques have also yielded a new record for the disjoint (5D) variant of Morpion Solitaire. For this variant, the previous record of 80 lines was found by Monte Carlo search (T. Cazenave, "Nested Monte-Carlo Search." IJCAI 2009). The new record has 82 lines:

  

  The new techniques used to set these new records are based on a combination of nested search (somewhat like: T. Cazenave, "Nested Monte-Carlo Search." IJCAI 2009) and machine learning of Monte Carlo playout policies (learning-based playout policies have also been used in the game of Go: D. Silver & G. Tesauro, "Monte-Carlo Simulation Balancing." ICML 2009).