Checkmate or should we say 'tsumi': The role of shogi in research on artificial intelligence and cognitive science

Developing powerful Shogi computer programs

The victory by the computer dubbed 'Deep Blue' over world chess champion Garry Kasparov in 1997 was a turning point for computer scientists in general, and artificial intelligence experts, in particular. Such computer programs for board games rely on powerful heuristic search methods--intelligent guessing based on experience--based on the development of so-called "heuristic evaluation functions".

"The victory of Deep Blue over a grand master was based on hand tuning of parameters in the computer programs," says Kunihito Hoki, an expert in artificial intelligence at UEC. "The goal of my research is to develop fully automated learning of heuristic evaluation functions for artificial intelligence. Recently, in collaboration with Tomoyuki Kaneko of the University of Tokyo, we developed a learning method that is capable of adjusting more than forty million parameters in the evaluation function." The learning method employed a well-modeled objective function and a numerical iterative method to control the heuristic search results by means of a large number of parameters.

In an innovative approach to demonstrate the power of their heuristic search method the researchers decided to implement the new method-- called Minimax Tree Optimization (MMTO)--in a program for playing shogi--a variant of chess also referred to as Japanese chess.

Notably, one of the unique features of shogi is that pieces captured by players can be reused as their own; a rule that makes the game 'divergent' and difficult to predict the outcome. Chess in contrast, 'converges' and the loss of a single piece can quickly lead to an end game. Thus, the quality of the evaluation functions is extremely important for producing powerful computer programs for shogi.

With this background, Hoiki and his colleague implemented their new method for a shogi program known as Bonanza and the power of the program was recognized by its first-place finish in the 2013 World Computer Shogi Championship. "We also have preliminary evidence of broader applications of our method to other two-player games such as chess," says Hoki.

Next move experiments: Cognitive science to analyze the human perspective of playing shogi

These questions are being addressed by Takeshi Ito, Chairman of the Cognitive Science and Entertainment Research Station at UEC, an experienced amateur player and advisor to the UEC Shogi Club, which is one of the top 8 university clubs in Japan.

"Shogi is one of the most popular board games in Japan with approximately 12 million playing the game," says Ito. "My experiments on 'next moves' are designed to analyze how players, ranging in ability from beginners to professionals, recognize phases and generate candidate moves."

Ito adds that the 'thought experiments' of shogi players consist of "verbal data from think-aloud protocols and eye-tracking data from an eye camera when solving next move problems".

Results from these experiments show that intermediate players think for longer periods of time (275s) than beginners and advances players (150s). Beginners take a long time (55s) to understand a position and focus on single moves that are possible from the current position. The time to understand a position becomes short with playing strength. Almost all professional players can understand a position within 3 seconds and find a proper candidate move immediately.

Intriguingly, professional players rely on past experience and moves are evaluated as having good or bad prospects without any look-ahead. Also, they recognize a position instantly and based on past experience and knowledge about the position.

"Professionals do not focus on all the piece positions but understand positions based on the flow of the game," says Ito. "My research compliments that of my colleague Kunihito Hoki. We are confident that our findings on shogi will contribute to the wider field of artificial intelligence and cognitive science."

References

1. Kunihito Hoki and Tomoyuki Kaneko, Large-Scale Optimization for Evaluation Functions with Minimax Search, Journal of Artificial Intelligence Research 49, 527­568, (2014).
2. Takeshi Ito, Takuya Obata, Takuya Sugiyama, Kunihito Hoki, Consultation Algorithm in Shogi-A Move Decision Based on the Positional Evaluation Value, Journal of Information Processing Society of Japan, 51, 2048-2054, (2010).
3. Takeshi Ito, Hitoshi Matsubara, and Reijer Grimbergen: Chunking in Shogi:New Findings, Advances in Computer Games, Lecture Notes in Computer Science 4250,pp.140-154 (2006).