Unlucky explorer : a complete non-overlapping map exploration

Abstract

<div lang="en" class="abs"><p class="abs_header">Abstract</p><p>In this work, we introduce the Maze Dash puzzle as an exploration problem where the agent must find a Hamiltonian Path visiting all the cells with a minimum number of turnings for most cases. We also discuss the real-world application of the problem, such as 8 ball billiards and Snooker games. We investigate different methods by a focus on Monte-Carlo Tree Search (MCTS) and SAT to get an overview of which class of solutions solves the puzzle quickly and accurately. Also, we perform optimization to the proposed MCTS algorithm to prune the tree search. Also, since the prefabricated test cases of this puzzle are not large enough to assay the proposed method, we employ a technique to generate solvable test cases to evaluate the approaches. Eventually, our comparison indicates that the MCTS-based approach is an up-and-coming method that could cope with the test cases with small and medium sizes with faster run-time than SAT. However, for specific discussed reasons, including the features of the problem, tree search organization, and also the approach of MCTS in the Simulation step, MCTS takes more time to execute in large size scenarios. Our results can be employed to choose a proper approach to create an AI to solve the Maze Dash, 8 ball billiards, and Snooker games.</p></div>