University of Oulu

Mohammad Sina Kiarostami, Saleh Khalaj Monfared, Mohammadreza Daneshvaramoli, Negar Yousefian, Mahsa Massoud, Aku Visuri, Simo Hosio, Dara Rahmati, and Saeid Gorgin. 2021. Unlucky Explorer: A Complete non-Overlapping Map Exploration. In 2021 The 3rd World Symposium on Software Engineering (WSSE 2021). Association for Computing Machinery, New York, NY, USA, 150–154. DOI:https://doi.org/10.1145/3488838.3488864

Unlucky explorer : a complete non-overlapping map exploration

Saved in:
Author: Kiarostami, Mohammad Sina1; Monfared, Saleh Khalaj2; Daneshvaramoli, Mohammadreza2;
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
3Computer Science and Engineering Department, Shahid Beheshti University, Tehran, Iran
4Iranian Research Organization for Science and Technology (IROST), Tehran, Iran
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.6 MB)
Persistent link: http://urn.fi/urn:nbn:fi-fe2022030221479
Language: English
Published: Association for Computing Machinery, 2021
Publish Date: 2022-03-02
Description:

Abstract

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.

see all

ISBN: 978-1-4503-8409-4
Pages: 150 - 154
DOI: 10.1145/3488838.3488864
OADOI: https://oadoi.org/10.1145/3488838.3488864
Host publication: WSSE 2021: 2021 The 3rd World Symposium on Software Engineering. Xiamen, China. September 24 - 26, 2021
Conference: World Symposium on Software Engineering
Type of Publication: A4 Article in conference proceedings
Field of Science: 113 Computer and information sciences
Subjects:
SAT
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
335729
Detailed Information: 318930 (Academy of Finland Funding decision)
335729 (Academy of Finland Funding decision)
Copyright information: © 2021 Association for Computing Machinery. 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 2021 The 3rd World Symposium on Software Engineering (WSSE 2021), https://doi.org/10.1145/3488838.3488864.