Gaming the Known and Unknown via Puzzle Solving With an Artificial Intelligence Agent

Researchers design multiple strategies for an artificial intelligent (AI) agent to solve a stochastic puzzle like Minesweeper.

For decades, efforts in solving games had been exclusive to solving two-player games (i.e., board games like checkers, chess-like games, etc.), where the game outcome can be correctly and efficiently predicted by applying some artificial intelligence (AI) search technique and collecting a massive amount of gameplay statistics. However, such a method and technique cannot be applied directly to the puzzle-solving domain since puzzles are generally played alone (single-player) and have unique characteristics (such as stochastic or hidden information). So then, a question arose as to how the AI technique can retain its performance for solving two-player games but instead applied to a single-agent puzzle?

For years, puzzles and games had been regarded as interchangeable or one part of the other. In truth, this may not be the case all the time. Looking from a real-world perspective, ‘game’ is something we face every day; dealing with the unknown. For instance, the unknown of making the right decision (i.e., getting married) or the wrong one (i.e., quitting a job) or not making one at all (i.e., regrets on ‘what if’). Meanwhile, ‘puzzle’ is something that was known to be there, and even something is hidden yet to be uncovered. Such a known case, for instance, would be the discovery of ‘wonder’ material like and its many potentials that are yet to be commercialized and widely used. Then again, how and what border between ‘puzzle’ and ‘game’ in a puzzle-solving context?

At the Japan Advanced Institute of Science and Technology (JAIST), Japan, Professor Hiroyuki Iida, and colleagues attempted to answer these two questions in their latest study published in the journal Knowledge-based Systems. The research study focuses on two important contributions: (1) defining the solvability of a puzzle in a single-agent game context via Minesweeper testbed and (2) proposing a new artificial intelligence (AI) agent using the unified composition of four strategies called PAFG solver. Taking advantage of the known information and unknown information of the Minesweeper puzzle, the proposed solver had achieved better performance in solving the puzzle comparable to the state-of-the-art studies.

The figure depicts AI strategies that use knowledge-driven strategies to deal with unknown information while adopting data-driven strategies to use the known information of the Minesweeper puzzle. The resultant findings establish the boundary condition for solvability in a single-player stochastic puzzle which is canonical to broad real-world problems. Credit: Hiroyuki Iida from JAIST

The researchers adopted an AI agent composed of two knowledge-driven strategies and two data-driven strategies to best use the known and unknown information of the current decision to best estimate the subsequent decision to make. As a result, the boundary between the puzzle-solving and game-playing paradigm can be established for the single-agent stochastic puzzle like the Minesweeper.

Such a condition plays a particularly important role in real-world problems where the boundary between the known and unknown is usually blurred and very hard to identify. As Professor Iida remarks: “With the capability of AI agent to enhance puzzle solving performance, the boundary of solvability become apparent. Such a situation allowed the clear definition of ‘puzzle’ and ‘game’ conditions, typically found in many real-life situations, such as determining high-stake investment, assessing the risk level of an important decision, and so on.” In essence, we all live in our Minesweeper world, trying to guess our way forward while avoiding the ‘bomb’ in our life.

Many uncertainties existed with the face-paced advancement of existing technology and new paradigm of computing available (i.e., IoT, cloud-based services, edge computing, neuromorphic computing, etc.). This condition could be true for people (i.e., technological affordance), community (i.e., technology acceptance), society (i.e., culture and norm), and even at the national levels (i.e., policy and rules changes). “Every day human activity involves a lot of ‘game’ and ‘puzzle’ conditions. However, mapping the solvability paradigm at scale, boundary conditions between the known and the unknown can be established, minimizing the risk of the unknown and maximizing the benefit of the known,” explains Ms. Chang Liu, the lead author of the study. “Such a feat is achieved by culminating knowledge-driven techniques, AI technology, and measurable uncertainty (such as winning rate, success rate, progress rate, etc.) while still keeping the puzzle fun and challenging.”

Reference: “A solver of single-agent stochastic puzzle: A case study with Minesweeper” by Chang Liu, Shunqi Huang, Gao Naying, Mohd Nor Akmal Khalid and Hiroyuki Iida, 28 March 2022, Knowledge-Based Systems.
DOI: 10.1016/j.knosys.2022.108630

About Japan Advanced Institute of Science and Technology, Japan

Founded in 1990 in Ishikawa prefecture, the Japan Advanced Institute of Science and Technology (JAIST) was the first independent national graduate school in Japan. Now, after 30 years of steady progress, JAIST has become one of Japan’s top-ranking universities. JAIST counts with multiple satellite campuses and strives to foster capable leaders with a state-of-the-art education system where diversity is key; about 40% of its alumni are international students. The university has a unique style of graduate education based on a carefully designed coursework-oriented curriculum to ensure that its students have a solid foundation on which to carry out cutting-edge research. JAIST also works closely both with local and overseas communities by promoting industry–academia collaborative research.

About Ms. Chang Liu from Japan Advanced Institute of Science and Technology, Japan

Ms. Chang Liu is a doctoral student at the School of Advanced Science and Technology (JAIST), Nomi, Japan. Her research focuses on researching appeal information about the evolution of puzzle games based on the game mechanics and player’s experience, supervised by Professor Hiroyuki Iida in the Lab of Entertainment Technology. She is working on analyzing the significant factors in the evolution of ancient to modern puzzle games, and the information analysis during the process of solving puzzles and playing games, to finding a line between puzzles and games.

About Professor Hiroyuki Iida from Japan Advanced Institute of Science and Technology, Japan

Dr. Hiroyuki Iida received his Ph.D. in 1994 on Heuristic Theories on Game-Tree Search from the Tokyo University of Agriculture and Technology, Japan. Since 2005, he has been a Professor at JAIST, where he is also a Trustee and Vice President of Educational and Student Affairs. He is the head of the Iida laboratory and has published over 300 papers, presentations, and books. His research interests include artificial intelligence, game informatics, game theory, mathematical modeling, search algorithms, game-refinement theory, game tree search, and entertainment science.

Funding information

This study was funded by a grant from the Japan Society for the Promotion of Science in the framework of the Grant-in-Aid for Challenging Exploratory Research (Grant Number 19K22893).

See author's posts