Nested Monte-Carlo Search with simulation reduction

作者：Akiyama Haruhiko^*; Komiya Kanako; Kotani Yoshiyuki

来源：Knowledge-Based Systems, 2012, 34: 12-20.

DOI：10.1016/j.knosys.2011.11.015

• Nested Monte-Carlo Search
• All-Moves-As-First (AMAF)
• Single-player games
• Morpion Solitaire
• Random simulation

The execution time of Nested Monte-Carlo Search for Morpion Solitaire, a single-player game, increases exponentially with the level of the nested search. We investigated the use of two methods for reducing the execution time in order to enable a deeper nested search: simply reducing the number of lower level searches by a constant rate and using All-Moves-As-First heuristic to the reduction in the number of lower level searches. Testing showed the latter is more effective. Using it, we achieved a new world record of 146 moves for a computer search for the touching version of Morpion Solitaire.

• 出版日期2012-10