WASEDA ONLINE

RSS

The Japan News by The Yomiuri Shimbun

Home > Opinion > Science

Opinion

Science

How to Think Ahead of the Next Move of “Akara” —the Challenges of Computer Shogi

Takenobu Takizawa
Professor, Faculty of Political Science and Economics, Waseda University

1. Akara 2010

On October 11, 2010, the computer shogi (Japanese chess) system Akara 2010 played a game against the then women's Osho champion Ichiyo Shimizu with no handicap and defeated her in 86 moves. Shimizu, who had defeated some male professional shogi players, was supposed to have almost the same level of ability as that of those who belong to the highest group of Shoreikai, a professional training institution. Therefore, it is likely that Akara 2010 exceeds their ability level. Actually, Kiyokazu Katsumata, a professional 6-dan (rank) player, certified by the Japan Shogi Association, the computer shogi program Gekisashi and a couple of runners-up at the 20th Computer Shogi World Championship, which was held in May 2010, are likely professional 4-dan players. The following is a summary of the mechanisms of computer shogi.

2. Programming of the Game

Figure 1

When deciding the next move in one game position, a shogi program thinks far ahead from that game position by following a "game tree," as shown in Fig. 1. When the average number of moves that can be made at each game position is b, and the average number of moves from one game position to the end of the game is p, the total number of moves that can be considered from one game position to the end of the game is b to the power of p. In a shogi game, b is a little more than 80 moves and p is a little more than 115 moves from the start of the game. The total number of moves that can be considered from the start of the game, which corresponds to the complexity of the game, is approximately 10 to the power of 220. This is the origin of the name of the program, as the Buddhist word Akara means 10 to the power of 224, which is close to 10 to the power of 220. Even today's fastest computers could not consider all of the possible moves from the start to the end of the game within one trillion (10 to the power of 12) years.

When deciding the next move in an actual game, the shogi program needs to quit thinking ahead at a certain point and approximate the result of the game (game position elements such as the advantage of the pieces captured and the defense of the king) that can be projected at that point.

3. Minimax principle and alpha-beta pruning

Figure 2

In Figure 1, ○ represents a game position where the player makes a move, and □ represents a game position where the opposing player makes a move. In this figure, there are three possible moves for each game position and the approximate outcome has been calculated at each of the game positions second moves forward (the third game position), under which the evaluation of this position is shown. The move at the second game position should be the most advantageous for the opposing player because it is the opposing player's turn to make a move. The move should make the subsequent game position the most advantageous for the opposing player (the least advantageous for the player), which is shown by bold lines from the second game positions to the third ones (including the move from the second game position b to game position f). Therefore, The position will be evaluated as somewhat superior (evaluation of f) if the player chooses b for her first move. The position will be evaluated as evenly matched if she chooses c, and as somewhat inferior if she chooses d. As a result, the player chooses b for the first move (the current game position). This decision rule, known as the "minimax principle," forms the basis of game programming. In Figure 1, nine game positions are approximated with evaluation functions.

Figure 3

In Figure 2, the game positions beyond game position b are evaluated first, which up to this point is the same as Figure 1, somewhat superior. If the evaluation of the game position i beyond the game position c (evenly matched) is gained, however, it eliminates the need to evaluate the game position j. If the game position j is evaluated as more advantageous for the player, rather than as evenly matched, the opposing player will not choose the move. If the game position j is evaluated as more advantageous for the opposing player, rather than as evenly matched, the game position will be evaluated as more advantageous for the opposing player. In any case, the player will not choose the move that leads to the game position c, which is the reason why it will not be necessary to evaluate the game position j. In other words, it is not necessary to evaluate other moves beyond the game position c if at least one move is found that is advantageous for the opposing player at game positions beyond the game position c. This decision rule is called "Beta cut-off." Similarly in the game position d, evaluation of the game position l is more advantageous for the opposing player than that of the game position b, and therefore other moves will be cut off (this is called Alpha cut-off, in which the player and the opposing player in Beta cut-off are reversed). This decision rule is called Alpha-Beta pruning. In Figure 2, seven game positions are approximated with evaluation functions. This means the same next move as in Figure 1 can be obtained through approximation with fewer evaluation functions than in Figure 1.

Figure 3 shows the ideal series of moves. In this case, the same next move as in Figure 1 and 2 can be obtained through approximation of five game positions with evaluation functions.

4. The History and the Future of Computer Shogi

In November 1974, the research group I belonged to became the first to embark on the development of computer shogi programs. I established the Group for Shogi Programs with Mr. Yoshiyuki Kotani of Tokyo University of Agriculture and Technology and others in 1986. The group changed its name to the Computer Shogi Association in 1987. The CSA started organizing the annual Computer-Shogi Championship in 1990. While the championship respects fairness above all, it imposes no restrictions on the specifications of the computers in order to pursue the best performance of the programs. In addition, we have encouraged those who developed programs that ranked high in the championship to present at conferences and write research papers about their algorithms and other research findings. I believe these efforts helped to advance computer shogi. A couple of particularly significant contributions are the release of the algorithm of the realization probability search, which was implemented in Gekisashi in 2005, and the release of the algorithm of the automatic learning of evaluation functions, which was implemented in Bonanza in 2006. Recently, the source codes of Bonanza and GPS shogi have been released, making it easier for newcomers to enter the computer shogi world. Table 1 shows the history of computer shogi, Table 2 shows a summary of the Computer Shogi World Championship, and Table 3 shows a summary of matches between computers and human players since 2007.

Table 1. The History of Computer Shogi
Year Event
1974 Development of computer shogi programs started
1984 A shogi program developed by the author played against the then elementary school meijin (champion) Yoshiyuki Kubota (currently a 6-dan professional player). The program was completely defeated and evaluated as 5-kyu (level).
1986 The Group for Shogi Programs was established.
1987 The Group for Shogi Programs changed its name to the Computer Shogi Association
Computer shogi software that runs on a personal computer was released.
1990 The 1st Computer Shogi Championship were held.
Around 1995 Computer programs that were ranked high at the Computer Shogi Championships reached the 1-dan level.
2005 The computer shogi program Gekisashi places in the top 16 of the national Amateur-Ryuo championship.
The computer shogi program TACOS played against 7-dan professional player Takanori Hashimoto with no handicap and put up a good fight.
The Japan Shogi Association prohibited professional shogi players from playing against computers in public.
2007 The computer shogi program Bonanza played against Ryuo Champion Akira Watanabe with no handicap and put up a good fight.
2008 Gekisashi and Tanase Shogi defeated the top amateur players each with short playing time.
Gekisashi defeated the top amateur player in a game with a one-hour playing time (and 1-minute byoyomi additional counting after the playing time).
2010 Computer programs that were ranked highly at the World Computer Shogi Championship reached the level of professional 4-dan player
The computer shogi system Akara 2010 defeated women's Osho Champion Ichiyo Shimizu in a game with a playing time of three hours (and 1-minute byoyomi additional counting after the playing time).
Table 2. World Computer Shogi Championships
Date No. of Days Winner 2nd 3rd No. of Participants Venue Tournament Style
1 1990.12 1 Eisei Meijin Kakinoki Morita 6(2) Shogi Kaikan Round robin
2 1991.12 1 Morita Kanazawa Eisei Meijin 9 Shogi Kaikan Round robin
3 1992.12 1 Kanazawa Kakinoki Morita 10 Shogi Kaikan 7-round tournament according to the Swiss tournament system
4 1993.12 1 Kanazawa Kakinoki Morita 14(1) Shogi Kaikan 7-round tournament according to the Swiss tournament system
5 1994.12 1 Kanazawa Morita YSS 22 Sheraton 7-round tournament according to the Swiss tournament system
6 1996.1 2 Kanazawa Kakinoki Morita 25(1) Sheraton 7-round tournament and final
7 1997.2 2 YSS Kanazawa Kakinoki 33(1) Sheraton 7-round tournament and final
8 1998.2 2 IS Kanazawa Shotest 35 Sheraton 2-class preliminary stages and final
9 1999.3 2 Kanazawa YSS Shotest 40 Sheraton 1st/2nd qualifying rounds and final
10 2000.3 3 IS YSS Kawabata 45 Sheraton 1st/2nd qualifying rounds and final
11 2001.3 3 IS Kanazawa KCC 55 Kazusa 1st/2nd qualifying rounds and final
12 2002.5 3 Gekisashi IS KCC 51(1) Kazusa 1st/2nd qualifying rounds and final
13 2003.5 3 IS YSS Gekisashi 45 Kazusa 1st/2nd qualifying rounds and final
14 2004.5 3 YSS Gekisashi IS 43 Kazusa 1st/2nd qualifying rounds and final
15 2005.5 3 Gekisashi KCC IS 39 Kazusa 1st/2nd qualifying rounds and final
16 2006.5 3 Bonanza YSS KCC 43(1) Kazusa 1st/2nd qualifying rounds and final
17 2007.5 3 YSS Tanase Gekisashi 40 Kazusa 1st/2nd qualifying rounds and final
18 2008.5 3 Gekisashi Tanase Bonanza 40(1) Kazusa 1st/2nd qualifying rounds and final
19 2009.5 3 GPS Otsuki Monju 42 Waseda University 1st/2nd qualifying rounds and final
20 2010.5 3 Gekisashi Shuso GPS 43(1) Univ. of Electro-Communications 1st/2nd qualifying rounds and final
21 2011.5 3         Waseda University 1st/2nd qualifying rounds and final

*The names were "Computer Shogi Championships" before the 11th Championship.
*Numbers of participants include the number of invited players, which are shown in ( ).
*Finals are all round robins, preliminaries are (modified) Swiss style
*From the 2nd through 5th, "Kanazawa" was called "Kiwame"
*Names of programs and venues are abbreviated
*Details for the 21st are to be confirmed

Table 3. Human vs. Computer Shogi matches since 2007 (partial)
Year Month Day Event Program Human Winner Handicap Time Byoyomi
2007 3 21 1st Daiwa Shoken cup Bonanza Ryuo Champion Akira Watanabe Ryuo Watanabe None 2h 60sec
5 5 17th World Computer Shogi Championship YSS Yukio Kato Kato None 15min 30sec
2008 5 5 18th World Computer Shogi Championship Gekisashi Toru Shimizugami Gekisashi None 15min 30sec
Tanase Yukio Kato Tanase None 15min 30sec
11 8 Game Programming Workshop 2008 Gekisashi Toru Shimizugami Gekisashi None 60min 60sec
Tanase Yukio Kato Kato None 60min 60sec
2009 3 10 71st IPSJ National Convention Gekisashi Satoshi Inaba Inaba None 60min 60sec
3 22 3rd UEC E&C Symposium Majorityvoting*1 Ikuma Tanizaki Tanizaki None 40min 60sec
11 7 UEC E&C "The Frontline of Computer Shogi" Monju with Bonanza Ikuma Tanizaki Tanizaki None 60min 30sec
GPS Shogi Satoshi Inaba GPS Shogi None 60min 30sec
2010 2 6 Osaka Univ. of Commerce"Brain Sports and Education" Gekisashi Noboru Kosaku Gekisashi None 20min None (kiremake)
10 11 IPSJ 50th Anniversary Event Akara 2010 Women's Osho Ichiyo Shimizu Akara None 3h 60sec

*1 Majority voting by Gekisashi, Bonanza, AI Shogi, Shin Todai Shogi

The 21st World Computer Shogi Championship is to be held at International Conference Hall, Waseda University in May 2011. It is expected that new algorithms will be created then. In addition, I personally look forward to seeing Akara challenge the top professional human players.

Takenobu Takizawa
Professor, Faculty of Political Science and Economics, Waseda University

Profile
Born in November 1951
March 1974: Graduated from the Department of Mathematics, School of Science and Engineering, Waseda University
March 1977: Completed the Master's Program in Mathematics, Graduate School of Science and Engineering, Waseda University
March 1980: Withdrew from the Doctoral Program in Mathematics, Graduate School of Science and Engineering, Waseda University after completing the course requirements.
April 1978: Assistant, Faculty of Engineering, Tamagawa University
April 1981: Full-Time Lecturer, Faculty of Engineering, Tamagawa University
April 1985: Full-Time Lecturer, School of Political Science and Economics, Waseda University
April 1987: Associate Professor, School of Political Science and Economics, Waseda University
April 1992: Professor, School of Political Science and Economics, Waseda University
April 2004-Present: Professor, Faculty of Political Science and Economics, Waseda University

Professor Takizawa's major publications (co-authored) include
Introduction to Fuzzy Theory and Its Application [Faji Riron -Kiso to Oyo-] (Kyoritsu Shuppan, August 2010), Elementary Calculus for Economics [Keizaikei no Tameno Bibun Sekibun] (Kyoritsu Shuppan, March 2007), Enjoy Statistics with Excel [Excel de Tanoshimu Tokei] (Kyoritsu Shuppan, February 2004).