For years, attempts in solving games have been limited to two-player games (i.e., board games such as checkers, chess-like games), where the game result can be efficiently and precisely predicted using artificial intelligence (AI) search techniques and a large number of gameplay statistics.
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. Image Credit: Hiroyuki Iida from Japan Advanced Institute of Science and Technology.
However, as puzzles are often played alone (single-player) and have unique features, such a strategy and method cannot be easily extended to the puzzle-solving area (such as stochastic or hidden information). The challenge then emerged as to how the AI technique could preserve its performance when applied to a single-agent puzzle while also addressing two-player games.
For decades, puzzles and games were thought to be convertible or parts of the same thing. In reality, this may not always be the case. From a practical standpoint, we deal with “games” on a daily basis: dealing with the unfamiliar.
For example, the uncertainty of making the correct (i.e., marrying) or wrong (i.e., quitting a job) decision, or not making one at all (i.e., regrets about “what if”). Meanwhile, the term “puzzle” refers to something that has been known to exist and even something that has yet to be discovered.
A well-known example would be the discovery of a “wonder” material like graphene and its numerous applications that have yet to be marketed. However, in a problem-solving setting, where and how do one draw the line between “puzzle” and “game”?
Professor Hiroyuki Iida and colleagues from the Japan Advanced Institute of Science and Technology (JAIST) tried to answer these two concerns in their recent work published in Knowledge-based Systems.
The paper focuses on two key contributions: (1) characterizing the solvability of a puzzle in a single-agent game situation using the Minesweeper testbed, and (2) suggesting a new artificial intelligence (AI) agent termed PAFG solver that employs a holistic composition of four approaches.
Using both known and unknown data from the Minesweeper puzzle, the suggested solution outperformed state-of-the-art research in solving the puzzle.
To best leverage the known and unknown knowledge regarding the current choice to accurately estimate the upcoming decision, the researchers used an AI agent made of two knowledge-driven strategies and two data-driven approaches. As a result, for a single-agent stochastic problem like Minesweeper, a border between the puzzle-solving and game-playing paradigm can be created.
In real-world challenges, where the line between known and unknown is frequently hazy and difficult to discern, such a circumstance is very significant.
With the capability of AI agents to enhance puzzle solving performance, the boundary of solvability becomes 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.
Hiroyuki Iida, Professor, Japan Advanced Institute of Science and Technology
In fact, humans all live in a minesweeper world, attempting to figure out how to go forward while avoiding the dreaded “bomb”.
With the rapid growth of current technology and the availability of a new computing framework, many questions emerged (i.e., IoT, cloud-based services, edge computing, neuromorphic computing, etc.). This criterion could apply to individuals (i.e., technological affordance), communities (i.e., technology acceptance), societies (i.e., culture and norm) and perhaps even 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.
Ms. Chang Liu, Study Lead Author, Japan Advanced Institute of Science and Technology
“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,” Ms. Liu added.
Journal Reference:
Liu, C., et al. (2022) A solver of single-agent stochastic puzzle: A case study with Minesweeper. Knowledge-based Systems. doi.org/10.1016/j.knosys.2022.108630.