University of Oulu

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:

On using Monte-Carlo tree search to solve puzzles

Saved in:
Author: Kiarostami, Mohammad Sina1; Daneshvaramoli, Mohammadreza2; Monfared, Saleh Khalaj2;
Organizations: 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
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 1.2 MB)
Persistent link:
Language: English
Published: Association for Computing Machinery, 2021
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.

see all

ISBN: 978-1-4503-9052-1
Pages: 18 - 26
DOI: 10.1145/3477911.3477915
Host publication: 7th International Conference on Computer Technology Applications, ICCTA 2021
Conference: International Conference on Computer Technology Applications
Type of Publication: A4 Article in conference proceedings
Field of Science: 113 Computer and information sciences
Funding: 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
Detailed Information: 318930 (Academy of Finland Funding decision)
335729 (Academy of Finland Funding decision)
Copyright information: © 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,