April 19, 2022
Gaming the known and unknown via puzzle solving
For decades, efforts in game solving had been exclusively focused on 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, a question arose: How can an AI technique retain its performance for solving two-player games but instead be 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. 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 is known to be there, and even something that is hidden yet to be uncovered. Such a known case, for instance, would be the discovery of "wonder" material like graphene and its many potentials that are yet to be commercialized and widely used. Then again, what is the 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 this question in their latest study published in the Knowledge-Based Systems. The study focuses on two important contributions: (1) defining the solvability of a puzzle in a single-agent game context via the 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 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 a Minesweeper world, trying to guess our way forward while avoiding the "bomb" in our lives.
Many uncertainties exist in the fast-paced advancement of existing technology and the 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 national levels (i.e., policy and rule 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."