Figure 1
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
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
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.
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.
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).
============
Copyright Notice
============
All of the articles, images, photographs and other content displayed above are owned by Waseda University. Permission to reproduce any content is subject to the following Terms of Use.
Terms of Use
- Content may not be used in a manner that may harm the honor or reputation of Waseda University.
- When reproducing any content, you must request permission by notifying the Office of Information and Public Relations of Waseda University through e-mail ([email protected]) and indicate the title of the media and intended date of reproduction. Unauthorized reproduction is strictly prohibited.
- Please cite clearly the source of content at the end of each article using the following format (Source: Research SEA yyyy/mm/dd).
- Content may not be altered or modified in any way. Manipulation of photographs is strictly forbidden. Use of quotations as protected under copyright law is limited to summarization or quotation of the main point.
- Use of content is protected under the copyright law. Any claims or disputes, privacy issues, or other matters related to copyrighted content not owned or controlled by Waseda University becomes the sole responsibility of the user.
Figure 2
Figure 3
