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 graphene 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 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.”