Nested Monte Carlo Tree Search as Applied to Samurai Sudoku

<p>As Sudoku has come into prominence as a favorite logic puzzle, mathematicians and computer scientists alike have analyzed the game for interesting properties. The large search space presents a challenge for both generating and solving Sudoku puzzles without relying on techniques that simply permute a valid puzzle. These permutations result in puzzles that are essentially the same since they follow the same solution path. Many Sudoku generating or solving programs rely on brute-force methods to avoid this pitfall, but this is inefficient since there is no heuristic to navigate the huge search space. A nested Monte Carlo tree search has some basis in brute-force methods, but guides the search in order to achieve better results by using random games within nested search stages. In this paper, we show that when the nested Monte Carlo search algorithm is implemented for solving Samurai Sudoku, a version of Sudoku in which a standard Sudoku puzzle is placed with four other standard Sudoku puzzles overlapping on each of the corners, it performs better than a completely random brute-force algorithm. Additionally, an improvement to the nested Monte Carlo search is made by implementing a heuristic that is used at each level of search. </p>

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2016

Author dc:creator

• Finley, Laura

Contributors dc:contributor

• Chris Tweddle, Ph.D.
• Jing Zhang, Ph.D.
• Dianna Galante, Ph.D.

• Sudoku
• Samurai Sudoku
• Monte Carlo search
• rollouts
• solver
• tree search
• Mathematics

Repository record dc:identifier

https://opus.govst.edu/theses/72

OAI identifier oai:identifier

oai:opus.govst.edu:theses-1074