A Survey of Tsume Shogi Programs Using Variable Depth Search
Grimbergen, R. (1999)
In H.J.van den Herik, H.Iida (eds.), Computers and Games, First International Conference, CG'98, Tsukuba, Japan, November 1998. LNCS 1558, pp. 300--317
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 have been 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.