  Nowadays, the field of Artificial Intelligence in Computer Games (AI in
Games) is going to be more alluring since computer games challenge many aspects
of AI with a wide range of problems, particularly general problems. One of
these kinds of problems is Exploration, which states that an unknown
environment must be explored by one or several agents. In this work, we have
first introduced the Maze Dash puzzle as an exploration problem where the agent
must find a Hamiltonian Path visiting all the cells. Then, we have investigated
to find suitable methods by a focus on Monte-Carlo Tree Search (MCTS) and SAT
to solve this puzzle quickly and accurately. An optimization has been applied
to the proposed MCTS algorithm to obtain a promising result. Also, since the
prefabricated test cases of this puzzle are not large enough to assay the
proposed method, we have proposed and employed a technique to generate solvable
test cases to evaluate the approaches. Eventually, the MCTS-based method has
been assessed by the auto-generated test cases and compared with our
implemented SAT approach that is considered a good rival. 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
compared to SAT. However, for certain 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.
Consequently, we have found the bottleneck for the MCTS-based method in
significant test cases that could be improved in two real-world problems.
