Games, Computing, and the Mind: How Search Algorithms Reflect Game Playing

Games, Computing, and the Mind: How Search Algorithms Reflect Game Playing

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 turn 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 the latest research study, researchers 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 the desired objective. When playing a game, for example, an AI-based on 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 making 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 searches approach 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.