Note: [1] This article is an improved revision of a paper presented at the CG’02 conference with title “Indefinite Sequence of Moves in Chinese Chess Endgames”. In this co-authored paper, Haw-ren Fang independently designed the algorithms, developed the theorems and lemmas, programmed, and wrote the paper. Tsan-sheng Hsu provided partial financial support and gave a couple of comments. Shun-Chin Hsu shared his experience of Chinese-chess programming.
Note: [2] Department of Computer Science, University of Maryland, A.V. Williams Building, College Park, Maryland 20742, USA. Email: hrfang@cs.umd.edu.
Note: [3] Institute of Information Science, Academia Sinica, No 128, Section 2, Academia Road, Nankang, Taipei 115, Taiwan. Email: tshsu@iis.sinica.edu.tw.
Note: [4] Department of Information Management, Chang Jung University, No 396, Changjung Road. Section 1, Kwayjen, Tainan, Taiwan. Email: schsu@mail.cju.edu.tw.
Abstract: Retrograde analysis has been widely used to solve many problems. In Western chess, it has been successfully applied to construct 6-piece endgame databases (Thompson, 1996). The classical algorithm first determines all terminal positions, e.g., checkmate or stalemate in Western chess, and then iteratively propagates the values back to their predecessors until no propagation is possible. In the final phase the remaining unknown positions are then declared draws. However, in Chinese chess, there are special rules other than checkmate and stalemate to end a game. In real games, some positions are adjudicated as wins or losses because of these special rules, but in the final phase of a typical retrograde-analysis algorithm the positions are mistakenly marked as draws. The most influential special rule is checking indefinitely. In this article, we thoroughly investigate and abstract this special rule. Finally, we give a practical solution to construct endgame databases that adequately deal with the special rule.
DOI: 10.3233/ICG-2004-27103
Journal: ICGA Journal, vol. 27, no. 1, pp. 19-37, 2004
