Abstract
Recently, a number of programs have been developed that successfully apply variable-depth search to find solutions for mating problems in Japanese chess, called tsume shogi. Publications on this research domain have been written mainly in Japanese. To present the findings of this research to a wider audience, we compare six different tsume programs. To find the solutions of difficult tsume-shogi problems with solution sequences longer than 20 plies, we will see that variable-depth search and hashing to deal with a combination of transposition, domination and simulation leads to strong tsume-shogi programs that outperform human experts, both in speed and in the number of problems for which the solution can be found. The best program has been able to solve Microcosmos, a tsume-shogi problem with a solution sequence of 1525 plies.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L.V. Allis. Searching for Solutions in Games and Artificial Intelligence PhD thesis, The Netherlands: University of Limburg, 1994. ISBN 90-9007488-0.
L.V. Allis, M. van der Meulen, and H.J. van den Herik. Proof-number search. Artificial Intelligence, 66:91–124, 1994.
T. Anantharaman, M.S. Campbell, and F. Hsu. Singular extensions: Adding selectivity to brute-force searching. Artificial Intelligence, 43:99–109, 1990.
A.D. de Groot. Thought and Choice in Chess. The Hague, The Netherlands: Mouton & Co, 1965.
M. Hirose, H. Matsubara, and T. Ito. The composition of tsume-shogi problems. In Advances in Computer Chess 8, pages 299–319, Maastricht, Holland, 1996. ISBN 9062162347.
K. Ito. Best-first search to solve tsume shogi problems. In H. Matsubara, editor, Computer Shogi Progress, pages 71–89. Tokyo: Kyoritsu Shuppan Co, 1996. ISBN 4-320-02799-X. (In Japanese).
K. Ito, Y. Kawano, and K. Noshita. On the algorithms for solving tsume-shogi with extremely long solution-steps. Journal of the Information Processing Society of Japan, 36(12):2793–2799, 1995. (In Japanese).
K. Ito, Y. Kawano, M. Seo, and K. Noshita. Tsume shogi. In H. Matsubara and I. Takeuchi, editors, BIT special issue: Game Programming, pages 130–138. Kyoritsu Shuppan Co., Tokyo, Japan, 1997. ISBN 00110-2-57035. (In Japanese).
K. Ito and K. Noshita. Two fast programs for solving tsume-shogi and their evaluation. Journal of the Information Processing Society of Japan, 35(8):1531–1539, 1994. (In Japanese).
T. Ito, Y. Kawano, M. Seo, and K. Noshita. Recent progress in solving tsume-shogi by computers. Journal of the Japanese Society of Artificial Intelligence, 10(6):853–859, 1995. (In Japanese).
Y. Kadowaki. Tsumuya-tsumazaruya, Shogi-Muso, Shogi-Zuko. Tokyo: Heibon-sha, 1975. ISBN 4-582-80282-0. (in Japanese).
Y. Kadowaki. Zoku-tsumuya-tsumazaruya. Tokyo: Heibon-sha, 1978. ISBN 4-582-80335-0. (in Japanese).
Y. Kawano. Using similar positions to search game trees. In R.J. Nowakowski, editor, Games of no chance (Combinatorial games at MSRI, Berkeley 1994), pages 193–202. Cambridge: University Press, 1996.
Y. Kawano. Personal communication, 1998.
R.E. Korf and D.M. Chickering. Best-first minimax search. Artificial Intelligence, 84:299–337, 1996.
Y. Kotani, T. Yoshikawa, Y. Kakinoki, and K. Morita. Computer Shogi. Tokyo: Saiensu-sha, 1990. (in Japanese.).
H. Matsubara. Shogi to computer (Shogi and computers). Kyoritsu Shuppan Co., Tokyo, Japan, 1994. ISBN 4-320-02681-0. (In Japanese).
H. Matsubara and K. Handa. Some properties of shogi as a game. Proceedings of Artificial Intelligence, 96(3):21–30, 1994. (In Japanese).
H. Matsubara, H. Iida, and R. Grimbergen. Natural developments in game research. ICCA Journal, 19(2):103–112, June 1996.
D.A. McAllester. Conspiracy numbers for min-max search. Artificial Intelligence, 35:287–310, 1988.
K. Morita. Personal communication, 1996.
Y. Nakayama, T. Akazawa, and K. Noshita. A parallel algorithm for solving hard tsume shogi problems. ICCA Journal, 19(2):94–99, June 1996.
N. Nilsson. Problem Solving Methods in Artificial Intelligence. New York: McGraw-Hill, 1971.
K. Noshita. How to make a quick and accurate tsume-shogi solver. Shingaku-Kenkyukai, COMP91, 56:29–37, 1991. (In Japanese).
K. Noshita. The tsume shogi solver T2. In H. Matsubara, editor, Computer Shogi Progress, pages 50–70. Tokyo: Kyoritsu Shuppan Co, 1996. ISBN 4-320-02799-X. (In Japanese).
K. Noshita. Personal communication, 1998.
J. Schaeffer. Conspiracy numbers. Artificial Intelligence, 43:67–84, 1990.
M. Seo. The C* algorithm for and/or tree search and its application to a tsume-shogi program. Master’s thesis, Faculty of Science, University of Tokyo, 1995.
M. Seo. A tsume shogi solver using conspiracy numbers. In H. Matsubara, editor, Computer Shogi Progress 2, pages 1–21. Tokyo: Kyoritsu Shuppan Co, 1998. ISBN 4-320-02799-X. (In Japanese).
G. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence, 12:179–196, 1979.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grimbergen, R. (1999). A Survey of Tsume-Shogi Programs Using Variable-Depth Search. In: van den Herik, H.J., Iida, H. (eds) Computers and Games. CG 1998. Lecture Notes in Computer Science, vol 1558. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48957-6_20
Download citation
DOI: https://doi.org/10.1007/3-540-48957-6_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65766-8
Online ISBN: 978-3-540-48957-3
eBook Packages: Springer Book Archive