Note: [1] I began working on Chinese-chess endgame databases by retrograde algorithms in mid 1996 under the direction of my master’s thesis advisor, Shun-Chin Hsu, in National Taiwan University. I noticed the problems caused by the special rules, particularly the rule of checking indefinitely. A couple of different approaches had been used without success. After graduation, I did not stop thinking about this problem while I fulfilled military service. One summer evening in 1998,1 was tackling this problem again in the office when everybody else went out for dinner. In a flash, I found the algorithm to compute the maximum move pattern of checking indefinitely, which was a prelude of all the algorithms and theories developed afterward. The weather in Taiwan is often cloudy, but when I walked out of my office on that evening, I saw a blood red sky as a prophecy for a big change in the weather.
Note: [2] Department of Computer Science, University of Maryland, A.V. Williams Building, College Park, Maryland 20742, USA. Email: hrfang@cs.umd.edu.
Abstract: Retrograde analysis is widely applied to construct databases of deterministic, finite, two-player zero-sum games with perfect information. However, its application to Chinese chess is limited because of the special rules about indefinite move sequences. Problems caused by the most influential rule, checking indefinitely3, were successfully solved in practical cases, with 50 selected endgame databases constructed in accord with this rule, where the 60-move rule was ignored. Other special rules were verified having much less impact on contaminating the databases via a rule-tolerant approach. For constructing complete endgame databases, we need rigorous algorithms. There are two rule sets in Chinese chess: the Asian rule set and the Chinese rule set. In this article, algorithms are successfully developed to build win-draw-loss endgame databases in accord with the Asian rule set.
DOI: 10.3233/ICG-2005-28204
Journal: ICGA Journal, vol. 28, no. 2, pp. 91-105, 2005
