Mohammad Sina Kiarostami, Mohammadreza Daneshvaramoli, Saleh Khalaj Monfared, Aku Visuri, Helia Karisani, Simo Hosio, Hamed Khashehchi, Ehsan Futuhi, Dara Rahmati, and Saeid Gorgin. 2021. On Using Monte-Carlo Tree Search to Solve Puzzles. 2021 7th International Conference on Computer Technology Applications. Association for Computing Machinery, New York, NY, USA, 18–26. DOI:https://doi.org/10.1145/3477911.3477915
On using Monte-Carlo tree search to solve puzzles
|Author:||Kiarostami, Mohammad Sina1; Daneshvaramoli, Mohammadreza2; Monfared, Saleh Khalaj2;|
1Center for Ubiquitous Computing, Faculty of ITEE, University of Oulu, Oulu, Finland
2School of Computer Sciences, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
|Online Access:||PDF Full Text (PDF, 1.2 MB)|
|Persistent link:|| http://urn.fi/urn:nbn:fi-fe2022022520848
Association for Computing Machinery,
|Publish Date:|| 2022-02-25
Solving puzzles has become increasingly important in artificial intelligence research since the solutions could be directly applied to real-world or general problems such as pathfinding, path planning, and exploration problems. Selecting the best approach to solve puzzles has always been an essential issue. Monte-Carlo Tree Search (MCTS) has surged into popularity as a promising approach due to its low run-time and memory complexity. Thus, it is required to know how to employ this method to solve the puzzles.
In this work, we study the applicability of MCTS in solving puzzles or solving a puzzle with MCTS, not comparing many MCTS approaches. We propose a general classification of puzzles based on their features. This classification consists of four primary classes that provide a mathematical formula for each and their satisfactory criteria. This classification let us know how to utilize MCTS based on the puzzle’s features. We pass each puzzle to an MCTS algorithm as a series of satisfaction functions based on this mathematical formulation. The classification can perform general pathfinding or path-planning if the outlining problem is defined within the described mathematical constraints. MCTS progressively solves a puzzle until the functions are completely satisfied in our proposed classification. We examine different puzzles for each class using our proposed methodology. Furthermore, to evaluate the proposed method’s performance, each of these puzzles is compared with their available SAT solvers using the Z3 implementation and different variations of MCTS that are generally used.
|Pages:||18 - 26|
7th International Conference on Computer Technology Applications, ICCTA 2021
International Conference on Computer Technology Applications
|Type of Publication:||
A4 Article in conference proceedings
|Field of Science:||
113 Computer and information sciences
This research is connected to the GenZ strategic profiling project at the University of Oulu, supported by the Academy of Finland (project number 318930), and CRITICAL (Academy of Finland Strategic Research, 335729). Part of the work was also carried out with the support of Biocenter Oulu, spearhead project ICON.
|Academy of Finland Grant Number:||
318930 (Academy of Finland Funding decision)
335729 (Academy of Finland Funding decision)
© 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in 7th International Conference on Computer Technology Applications, https://doi.org/10.1145/3477911.3477915.