×

Computer shogi. (English) Zbl 0982.68121

Summary: This paper describes the current state of the art in computer shogi. Shogi (Japanese chess) promises to be a good vehicle for future research into game-playing programs that are based on tree-searching paradigms. This paper shows where chess and shogi are similar, and details the important areas that make shogi programming of particular interest. A crucial difference is the game-tree complexity, which is significantly higher in shogi than in chess. Three important differences are the “drop” rule, the diverging character of the game, and the slow build-up of forces. They make it difficult to have effective opening and endgame procedures. After a short summary of the rules of shogi and an outline of the main areas of current work in computer shogi, we provide an overview of the history of computer shogi, in which computer-shogi activities both in human tournaments and in exhibition events are given. We conjecture that by the year 2010 a computer will be comparable in strength to the best human players. The most important techniques used in computer shogi are described. We focus on issues such as opening play, selective search, quiescence search, solving tactical exchanges without tree searching, position evaluation and endgame play. At the end the key challenges in computer shogi are enumerated, and finally, concluding remarks are given.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68P10 Searching and sorting
91A05 2-person games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akl, S. G.; Newborn, M. M., The principal continuation and the killer heuristic, (Proceedings, ACM ’77 National Conference (1977), ACM Press: ACM Press New York), 446-473
[2] Allis, L. V.; van der Meulen, M.; van den Herik, H. J., Proof-number search, Artificial Intelligence, 66, 91-124 (1994) · Zbl 0801.90145
[3] Arioka, M., Brinkmate search in KFEnd, http://plaza9.mbn.or.jp/ kfend/inside_kfend/hissi.html (2000), (in Japanese)
[4] Beal, D. F., A generalised quiescence search algorithm, Artificial Intelligence, 43, 1, 85-98 (1990)
[5] Beal, D. F.; Smith, M. C., First results from using temporal difference learning in shogi, (van den Herik, H. J.; Iida, H., Proceedings of First International Conference on Computers and Games, CG’98. Proceedings of First International Conference on Computers and Games, CG’98, Lecture Notes in Computer Science, 1558 (1999), Springer: Springer Heidelberg), 113-125
[6] Bernstein, A.; Roberts, M.de V., Computer vs chess-player, Scientific American, 198, 96-105 (1958)
[7] Search algorithm for shogi program Gekisashi on the Internet Web page http://www.logos.t.u-tokyo.ac.jp/ gekisashi/ (2001), (in Japanese)
[8] Computer Shogi Association, http://www.computer-shogi.org/; Computer Shogi Association, http://www.computer-shogi.org/ · Zbl 1032.91520
[9] Fairbairn, J., Shogi for Beginners (1984), Shogi Association Ltd.: Shogi Association Ltd. London
[10] Greenblatt, R.; Eastlake, D.; Crocker, S., The Greenblatt chess program, (Proceedings of the Fall Joint Computer Conference (1967)), 801-810
[11] Grimbergen, R., An evaluation function for shogi, (Matsubara, H., Proceedings of Game Programming Workshop in Japan ’97, Hakone, Japan (1997)), 159-168
[12] Grimbergen, R., A survey of Tsume-Shogi programs using variable-depth search, (van den Herik, H. J.; Iida, H., Proceedings of First International Conference on Computers and Games, CG’98. Proceedings of First International Conference on Computers and Games, CG’98, Lecture Notes in Computer Science, 1558 (1999), Springer: Springer Heidelberg), 300-317
[13] Grimbergen, R., Plausible move generation using move merit analysis with cut-off thresholds in Shogi, (Frank, I.; Marsland, T. A., Proceedings of Second International Conference on Computers and Games, CG2000. Proceedings of Second International Conference on Computers and Games, CG2000, Lecture Notes in Computer Science, 2063 (2001), Springer: Springer Heidelberg), 331-349 · Zbl 0989.91521
[14] Grimbergen, R.; Iida, H., Report on the 8th CSA world Computer-Shogi Championship, ICCA J., 21, 2, 135-138 (1998)
[15] R. Hare, Shogi—Japanese chess, http://www.edinburgh.ac.uk/ rjhare/shogi/intro.html; R. Hare, Shogi—Japanese chess, http://www.edinburgh.ac.uk/ rjhare/shogi/intro.html
[16] Hashimoto, T., On-going work on brinkmate solver, J. Computer Shogi Assoc., 13, 44 (2000), (in Japanese)
[17] Hirose, M.; Matsubara, H.; Itoh, T., The composition of Tsume-Shogi problems, (van den Herik, H. J.; Uiterwijk, J. W.H. M., Advances in Computer Chess, 8 (1997), Universiteit Maastricht: Universiteit Maastricht The Netherlands), 299-318
[18] Hori, Y.; Seki, M.; Grimbergen, R.; Maruyama, T.; Hoshino, T., A Shogi processor with a field programmable gate array, (Frank, I.; Marsland, T. A., Proceedings of Second International Conference on Computers and Games CG2000. Proceedings of Second International Conference on Computers and Games CG2000, Lecture Notes in Computer Science, 2063 (2001), Springer: Springer Heidelberg), 311-330 · Zbl 0989.68537
[19] Hosking, L. V., The Art of Shogi (1997), The Shogi Foundation: The Shogi Foundation England
[20] Iida, H.; Uiterwijk, J. W.H. M.; van den Herik, H. J.; Herschberg, I. S., Potential applications of opponent-model search, Part 1. The domain of applicability, ICCA J., 16, 4, 201-208 (1993)
[21] Iida, H.; Abe, F., Brinkmate search, (Proceedings of Game Programming Workshop in Japan ’96, Hakone, Japan (1996)), 160-169
[22] Iida, H., Grandmaster’s exhibition handicap games with shogi programs at GPW’96, J. Computer Shogi Assoc., 10, 8-9 (1997), (in Japanese)
[23] Iida, H., Computer shogi will come of age: Toward challenging human supremacy in shogi, IPSJ Magazine, 39, 9, 872-876 (1998), (in Japanese)
[24] Iida, H., Computer vs grandmaster, J. Computer Shogi Assoc., 11, 6-9 (1998), (in Japanese)
[25] H. Iida (Ed.), J. Computer Shogi Assoc. 11 (1998); H. Iida (Ed.), J. Computer Shogi Assoc. 11 (1998)
[26] H. Iida (Ed.), J. Computer Shogi Assoc. 12 (1999); H. Iida (Ed.), J. Computer Shogi Assoc. 12 (1999)
[27] Iida, H.; Yoshimura, J.; Morita, K.; Uiterwijk, J. W.H. M., Retrograde analysis of the KGK endgame in shogi: Its implications for ancient Heian shogi, (van den Herik, H. J.; Iida, H., Proceedings of First International Conference on Computers and Games, CG’98. Proceedings of First International Conference on Computers and Games, CG’98, Lecture Notes in Computer Science, 1558 (1999), Springer: Springer Heidelberg), 318-340
[28] Iida, H.; Sasaki, N.; Hashimoto, T.; Uiterwijk, J. W.H. M.; van den Herik, H. J., Towards a classification of games using computer analyses, (Neuwahl, N., Proceedings of the International Colloquium “Board Games in Academia III”, Florence (1999)), 139-152
[29] Iida, H., YSS wins shogi tournament, ICCA J., 23, 3, 184-185 (2000)
[30] Jansen, P. J., Problematic positions and speculative play, (Marsland, T. A.; Schaeffer, J., Computers, Chess, and Cognition (1990), Springer: Springer New York), 169-182
[31] Jansen, P. J., KQKR: Speculatively thwarting a human opponent, ICCA J., 16, 1, 3-17 (1993)
[32] Kakinoki, Y., The search algorithms in the Shogi program K3.0, (Matsubara, H., Advances in Computer Shogi (1996), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), Chapter 1, pp. 1-23 (in Japanese)
[33] Kakinoki, Y., Kakinoki won the Sapporo Meijin (B-class) title, J. Computer Shogi Assoc., 13, 22-27 (2000), (in Japanese)
[34] Kanazawa, S., The algorithms in Kanazawa Shogi, (Matsubara, H., Advances in Computer Shogi, 3 (2000), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), Chapter 2, pp. 15-26 (in Japanese)
[35] Kawano, Y., Using similar positions to search game trees, (Nowakowski, R. J., Games of No Chance. Games of No Chance, MSRI Publications, 29 (1996), Cambridge University Press: Cambridge University Press Cambridge), 193-202 · Zbl 0872.90140
[36] Kotani, Y., Which computer shogi is strong?, (Matsubara, H., Advances in Computer Shogi, 3 (2000), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), 111-120, (in Japanese)
[37] Leggett, T., Shogi: Japan’s Game of Strategy (1966), Charles E. Tuttle Company: Charles E. Tuttle Company England
[38] Levy, D. N.; Broughton, D., The SEX algorithm in computer chess, ICCA J., 12, 1, 10-21 (1989)
[39] Levy, D. N.; Newborn, M., How Computers Play Chess (1991), Computer Science Press: Computer Science Press England
[40] Matsubara, H.; Iida, H.; Grimbergen, R., Natural Developments in game research, ICCA J., 19, 2, 103-112 (1996)
[41] (Matsubara, H., Advances in Computer Shogi, Vols. 1-3 (1996, 1998, 2000), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), (in Japanese)
[42] D.A. McAllester, D. Yuret, Alpha-beta-conspiracy search, http://www.research.att.com/ dmac/; D.A. McAllester, D. Yuret, Alpha-beta-conspiracy search, http://www.research.att.com/ dmac/
[43] Michie, D., Game playing and game learning automata, (Fox, L., Advances in Programming and Non-Numerical Computation (1966), Pergamon: Pergamon Oxford), 183-200 · Zbl 0265.68042
[44] Nagai, A., A new AND/OR tree search algorithm using proof number and disproof number, (Proceedings of Complex Games Lab Workshop (1998), ETL, Tsukuba: ETL, Tsukuba Japan), 40-45
[45] Nagai, A., A new depth-first-search algorithm for AND/OR trees, M.Sc. Thesis (1999), Department of Information Science, University of Tokyo: Department of Information Science, University of Tokyo Japan
[46] Nagai, A.; Imai, H., Application of df-pn+ to Othello endgames, (Proceedings of Game Programming Workshop in Japan ’99, Hakone, Japan (1999)), 16-23
[47] Nagai, A., The recent achievements of computer Tsume-Shogi: Challenges in solving problems with extremely long steps, J. Computer Shogi Assoc., 13, 34-42 (2000), (in Japanese)
[48] Nakaie, H.; Kotani, Y.; Iida, H., A method of applying opening book data to non-recorded positions, (Proceedings of Game Programming Workshop in Japan ’96, Hakone, Japan (1996)), 218-227, (in Japanese)
[49] Nakaie, H.; Kotani, Y., A method of applying opening book data by partial matching, (Proceedings of Game Programming Workshop in Japan ’97, Hakone, Japan (1997)), 106-113, (in Japanese)
[50] Newell, A.; Shaw, C.; Simon, H. A., Chess playing programs and the problem of complexity, IBM J. Res. Develop., 2, 320-335 (1958)
[51] Newell, A.; Simon, H. A., Human Problem Solving (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[52] Noshita, K., A note on algorithmic generation of tsume-shogi problems, (Matsubara, H., Proceedings of Game Programming Workshop in Japan ’99, Hakone, Japan (1996)), 27-33
[53] Rollason, J., SUPER-SOMA—Solving tactical exchanges in Shogi without tree searching, (Frank, I.; Marsland, T. A., Proceedings of Second International Conference on Computers and Games, CG2000. Proceedings of Second International Conference on Computers and Games, CG2000, Lecture Notes in Computer Science, 2063 (2001), Springer: Springer Heidelberg), 291-310 · Zbl 0996.91504
[54] Sakuta, M.; Iida, H., Report on the 9th CSA World Computer-Shogi Championship, ICCA J., 22, 3, 180-182 (1999)
[55] Samuel, A., Some studies in machine learning using the game of checkers, IBM J. Res. Develop., 3, 210-229 (1959)
[56] Seo, M.; Iida, H.; Uiterwijk, J. W.H. M., The \(PN^∗\)-search algorithm: Application to Tsume-Shogi, Artificial Intelligence, 129, 1-2, 253-277 (2001) · Zbl 0971.68039
[57] Shannon, C. E., Programming a computer for playing chess, Philos. Magazine, 41, 256-275 (1950) · Zbl 0041.44605
[58] Slate, D. J.; Atkin, L. R., Chess 4.5—The Northwestern University chess program, (Frey, P. W., Chess Skill in Man and Machine (1977), Springer: Springer Berlin), 82-118
[59] Takizawa, T., Report on Computer-Shogi Grand Prix in 1999, J. Computer Shogi Assoc., 12, 39-41 (1999), (in Japanese)
[60] Takizawa, T.; Grimbergen, R., Review: Computer Shogi through 2000, (Frank, I.; Marsland, T. A., Proceedings of Second International Conference on Computers and Games, CG2000. Proceedings of Second International Conference on Computers and Games, CG2000, Lecture Notes in Computer Science, 2063 (2001), Springer: Springer Heidelberg), 456-466
[61] Tanase, Y., The algorithms in IS Shogi, (Matsubara, H., Advances in Computer Shogi, 3 (2000), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), Chapter 1, pp. 1-14 (in Japanese)
[62] Uiterwijk, J. W.H. M.; van den Herik, H. J., Speculative play in computer chess, (van den Herik, H. J.; Herschberg, I. S.; Uiterwijk, J. W.H. M., Advances in Computer Chess, 7 (1994), University of Limburg: University of Limburg Maastricht), 79-90
[63] Watanabe, H.; Iida, H.; Uiterwijk, J. W.H. M., Automatic composition of Shogi mating problems, (van den Herik, H. J.; Iida, H., Games in AI Research (2000), Van Spijk: Van Spijk Venlo, Netherlands), 109-123
[64] Xinbo, G.; Iida, H.; Uiterwijk, J. W.H. M.; van den Herik, H. J., Strategies anticipating a difference in search depth using opponent-model search, Theoret. Comput. Sci., 252, 1-2, 83-104 (2001) · Zbl 0954.68059
[65] Yamashita, H., A report on two shogi programs participating in an open rating competition, J. Computer Shogi Assoc., 10, 3-7 (1997), (in Japanese)
[66] Yamashita, H., Half-extension algorithm, (Matsubara, H., Proceedings of Game Programming Workshop in Japan ’97, Hakone, Japan (1997)), 46-54
[67] Yamashita, H., YSS—About the data structures and the algorithms, (Matsubara, H., Advances in Computer Shogi, 2 (1998), Kyoritsu Shuppan: Kyoritsu Shuppan Tokyo), Chapter 6, pp. 112-142 (in Japanese)
[68] H. Yamashita, YSS 7.0—About the data structures and the algorithm, http://plaza15.mbn.or.jp/ yss/book_e.html; H. Yamashita, YSS 7.0—About the data structures and the algorithm, http://plaza15.mbn.or.jp/ yss/book_e.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.