Computer Chinese Chess

• IIS members:
  • Tsan-sheng Hsu, IIS, Academia Sinica.
• Outside members:
  • Shun-chin Hsu, Department of Information Management, Chang Jung University, Tainan, Taiwan.
  • Ping-Yi Liu, Department of Computer Sciences, University of Texas at Austin, USA.
  • Hsu-cheng Tsai, Department of Computer Science and Information Engineering, National Taiwan University.
  • Kuang-che Wu, Department of Computer Science and Information Engineering, National Taiwan University.
  • Ping-hsun Wu, Department of CS, UC Santa Barbara, USA.

We conduct researches in these areas of Computer Chinese chess:

1. Computer detection and verification of Chinese chess special rules. Chinese chess uses sophisticated tie-breaking rules to decide the outcome of a game when it falls into repeated patterns. Western chess has no such rules. These rules are complex and often illustrated with examples. We hope to use graph theory, logic and algorithm techniques to describe and implement these special rules efficiently.

2. Memory-efficient generation of Chinese chess endgame databases. Retrograde analysis is well-known and has been successfully used in the design of Western chess endgame databases. Endgame databases can be treated as a directed graph with nodes representing possible board configurations and edges representing the moves. To solve an endgame, we need to traversal each edge and node of the graph according to an order set by the rules of the game.

   Several previous retrograde analysis algorithms are not memory efficient. To build larger endgame databases, we need to devise new algorithms that are either external-memory based or using new techniques.

   Another research issue in endgame database is to do data mining and high-level knowledge abstraction.

3. Computer programs to play Chinese chess. We hope to explore special searching algorithms and heuristics in designing computer programs that can play master-level Chinese chess. There are lots of studies in Western chess that can be used in out programs. However, there are several problems that are unique in Chinese chess that we have to face. Some of such examples are the usage of the pieces Cannon, the fact that the King is confined in the palace, and the usage of special tie-breaking rules. In the programs, we hope to integrate our results in special rules and endgame databases into our programs. The ultimate goal is not to beat human world champion, but to assist human in mastering the game of Chinese chess.

• Ping-hsun Wu, Ping-Yi Liu and Tsan-sheng Hsu, "An External-Memory Retrograde Analysis Algorithm", Proc. 4th International Conference on Computers and Games (CG), Springer-Verlag LNCS, 2004, to appear.
  • This paper gives a new sequential retrograde analysis algorithm for the construction of large endgame databases that are too large to be loaded entirely into the physical memory. The algorithm makes use of disk I/O patterns and saves disk I/O time. We construct a set of Chinese chess endgame databases with one side having attacking pieces using our algorithm. The performance result shows our algorithm works well even when the number of positions in the constructed endgame is larger than the number of bits in the main memory of our computer. We build the 12-men database KCPGGMMKGGMM, the largest reported in Chinese chess, which has 8,785,969,200 positions after removing symmetrical positions on a 2.2GHz P4 machine with 1 GB main memory. This process takes 79 hours. We have also found positions with the largest DTM and DTC values currently reported in the 11-men database KCPGGMKGGMM whose values are 116 and 96, respectively.

• Tsan-sheng Hsu and Ping-Yi Liu, "Verification of Endgame Databases," International Computer Game Association (ICGA) Journal, volume 25, number 3, pages 132--144, 2002.
  • This paper studies the verification of endgame databases using algorithms with limited memory space. To verify a constructed endgame database, the value of each position is checked for consistency against the values of the successor positions. Hence a trivial implementation of this algorithm needs to randomly access database content. A graph-theoretical technique called vertex-partitioning is proposed to divide an endgame database into several partitions. The positions in a partition have the good property that their successor positions are all in a relatively small proportion of these partitions. Hence only a small portion of the database needs to be loaded into the main memory at one time while verifying all positions in a partition. We show performance results in verifying Chinese chess endgame databases using this method. Our technique is a generalization of the previous approaches used in saving memory during the constructing of endgame databases. This technique can be used in other similar games, such as Western chess. The technique can also be used to save the amount of memory used in the initialization phase of retrograde analysis for constructing endgame databases.

Created by Tsan-sheng Hsu, April 18, 2001.