Games, computing, and the mind: How search algorithms reflect game playing

Scientists explore the links between game-solving search tree algorithms and the subjective experience of playing various turn-based games

JAPAN ADVANCED INSTITUTE OF SCIENCE AND TECHNOLOGY

Research News

 

IMAGE: ILLUSTRATION OF PPN AND CNS AS SEARCH INDICATORS, APPLIED TO SEVERAL TWO-PERSON AND SINGLE-PLAYER GAMES. THESE INDICATORS CAN BRIDGE SEARCH ALGORITHMS AND ENTERTAINMENT VIA THE ANALOGY OF 'MOTION IN MIND'... view more 

CREDIT: HIROYUKI IIDA FROM JAIST.

Iahikawa, Japan - Humans benefit from playing games more than some might realize. Games can be a relaxed approach to learning or honing our problem-solving skills while relieving stress. However, game playing generally carries a considerable amount of decision-making, involving mathematical and statistical considerations that we make to decide on what we think is the best move. Thus, games showcase many of the impressive faculties and inner workings of the human brain, which in turns makes them a great testbed and playground for research on artificial intelligence (AI).

One aspect common to many games is decision making based on uncertain information about current and potential future game states. Experienced players can 'look ahead' from the current state of a game and analyze what could happen several turns or moves down the line, allowing them to strategize accordingly. Most notably, this mental process is akin to what some search algorithms are designed to do--not just for game solving, but also in general computing tasks across various areas of application. But how do we establish a formal connection between these fields?

At the Japan Advanced Institute of Science and Technology (JAIST), Professor Hiroyuki Iida's research group is developing new theories to analyze and ultimately understand the many facets of games and game playing, both from purely objective and psychological points of view. In their latest study published in IEEE Access Prof. Iida, alongside first author of the paper Anggina Primanita and Mohd Nor Akmal Khalid, also from JAIST, attempted to bridge computing notions with the experience of game playing. To do this, they proposed two indicators to be used in search tree algorithms--the probability-based proof number (PPN) and the single conspiracy number (SCN)--and applied them to various turn-based games.

These search indicators are values that search tree algorithms calculate to 'assess' their progress towards a desired objective. When playing a game, for example, an AI based on a search algorithm would use search indicators to analyze potential future states while looking mainly for plays that somehow maximize the chances of winning. Ultimately, search indicators and algorithms should be crafted carefully to minimize computing resources used; not every possible play has to be considered in detail, but only those that are likely to win.

The researchers applied these two indicators in search tree frameworks in the context of different games, including Chess, Chinese Chess, Connect 4, Othello, and 2048. The results revealed interesting information on what each indicator brings to the table. "The PPN-based search provided a means for determining the quality of information available in the game and seemed to operate in a similar fashion to human intuition. Contrarily, the SCN-based search provided a platform to understand the player's experience and how they manage risks when taking decisions," explains Prof. Iida.

Additionally, the SCN-based search approach was linked with another theoretical framework developed at Iida's lab: the concept of motion in mind. This approach analyzes various objective and subjective aspects of the game-playing experience in a mathematical fashion by drawing analogies with motion-related concepts from physics, such as those in classical mechanics. By comparing the SCN with these analogies of motion in games, the researchers found that the underlying computations are directly related to the oscillations (from losing to winning positions) that happen in both single-player and two-player competitive games.

Both search approaches analyzed in this study have applications in and outside the realm of games. For example, PPN can be used to save valuable resources and time during intensive computing tasks, such as optimization problems, planning, scheduling, and simulations. Meanwhile, the SCN is useful in contexts where high-stakes decisions must be made or when long-term planning is necessary, as it allows for optimizing values and minimizing risks. "Both PPN and SCN can be crucial components for research in the field of artificial intelligence, including evolutionary computations and high-performance computing," remarks Prof. Iida, "Moreover, they both provide stepping stones for measuring entertainment from an information science point of view."

Further multidisciplinary studies shall help us find more links between entertainment, information science, and the human mind. Hopefully, in the long run, we will be able to tailor games from a more subjective and even purpose-driven perspective, maximizing our enjoyment while being useful in many other ways.

###

Reference

Title of original paper: "Computing Games: Bridging The Gap Between Search and Entertainment"

Journal: IEEE Access

DOI: 10.1109/ACCESS.2021.3079356

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 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 Trustee and Vice President of Educational and Student Affairs. He is the head of the Iida laboratory and has published over 300 hundred papers, presentations, and books. His current 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).