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.
  • Bo-Nian Chen, Department of Computer Science and Information Engineering, National Taiwan University.
  • Kuang-che Wu, Department of Computer Science and Information Engineering, National Taiwan University.

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. 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.

• Bo-Nian Chen and Pangfeng Liu and Shun-Chin Hsu and Tsan-sheng Hsu, "Conflict Resolution of Chinese Chess Endgame Knowledge Base", Proc. 12th Advances in Computer Games Conference, (ACG), Springer-Verlag LNCS, 2009, to appear.
  • In tournaments between grandmasters, players utilize not perfect but useful endgame heuristic that are still beyond the reach of computers. Endgame heuristics are often incorperated as part of the evaluation func- tion used in Chinese chess programs. In our program, Contemplation, we have proposed an automatic strategy to construct a large set of endgame heuristics. In this paper, we propose a conflict resolution strategy to eliminate the conflicts among the constructed heuristic database, which is called endgame knowledge base. In our experiment, the correctness of the obtained constructed endgame knowledge base is high enough for practical usage.

• Bo-Nian Chen and Pangfeng Liu and Shun-Chin Hsu and Tsan-sheng Hsu, "Knowledge Inferencing on Chinese Chess Endgames," Proc. 6th International Conference on Computers and Games (CG), Springer-Verlag LNCS# 5131, pages 180--191, 2008.
  • Several Chinese chess programs exhibit grandmaster playing skills in the opening and middle games. However, in the endgame phase, the programs only apply ordina l search algorithms; hence, they usually cannot exchange pieces correctly. Some researchers use retrograde algorithms to solve endgames with a limited number of attack pieces, but this approach is often not practical in a real tournament. I n a grandmaster game, the players typically perform a sequence of material excha nges between the middle game and the endgame, so computer programs can be useful . However, there are about 185 million possible combinations of material in Chin ese chess, and many hard endgames are inconclusive even to human masters. To res olve this problem, we proposed a novel strategy that applies a knowledge inferen cing algorithm on a suffciently small database to determine whether endgames wit h a certain combination of material are advantageous to a player. Our experiment results show that performance of the algorithm is good and reliable for buildin g a large knowledge database of material combinations.

• Bo-Nian Chen and Pangfeng Liu and Shun-Chin Hsu and Tsan-sheng Hsu, "Abstracting Knowledge from Annotated Chinese-Chess game Records," Proc. 5th International Conference on Computers and Games (CG), Springer-Verlag LNCS# 4630, pages 100--111, 2006.
  • Expert knowledge is crucial to improving the strength of computer Chines e chess programs. Although a great deal of expert knowledge is available in text format that uses natural languages, manually transforming it into computer readable forms is time consuming and difficult. Written expert annotations of Chinese chess games follow certain styles. By analyzing and collecting commonly used phrases and patterns from experts' annotations, we introduce a novel pattern matching strategy that automatically abstracts knowledge from a large number of annotated game records. The results of experiments on the middle phase of games indicate that our strategy achieves a low error rate. We hope to utilize this approach to automatically collect Chinese chess knowledge that is currently in text format.

• Kuang-che Wu, Shun-Chin Hsu and Tsan-sheng Hsu, "The Graph History Interaction Problem in Chinese Chess," Proc. 11th Advances in Computer Games Conference, (ACG), Springer-Verlag LNCS# 4250, pages 165--179, 2005.
  • The importance of mastering Chinese chess rules to improve the skills of Computer Chinese chess players is recognized by experts. However, we are not aware of any published results of a good enough implementation of Chinese chess rules without severe performance degradation. This paper reports such an implementation. The Chinese chess rules used to decide the outcome of a game when it falls into loops are those proposed by the Asia Chinese Chess Association. Chinese chess rules for cyclic moves differ from Western chess rules in two regards. First the outcome of a cyclic game can either be win, lose, or draw. Second, depends on the plys made inside a loop, there are upto 16 types of rule violations for each player when a loop occurs. The same type of rule has to be violated three times in a row, namely in three consecutive loops, to lose the game. In other words, a player can violate different rules in three cycles to achieve a draw. In comparison, Western chess rules define a game always be a draw after three consecutive loops.

• 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# 3846, pages 145--160, 2004.
  • 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.