Sage Journals: Discover world-class research

Abstract

Chinese chess is an artificial intelligence (AI) domain that merges ancient culture with emerging technology. This article explores key aspects of current Chinese chess technology, including move generation, evaluation functions, and search techniques in the search engine, as well as developments in the opening knowledge base and endgame databases. We also examine parallelization techniques, which are essential for improving computational efficiency and performance. Inspired by AlphaZero's achievements in reinforcement learning, this article also explores its key concepts and impact on AI techniques. It further highlights the field's development and the notable performance of computer Chinese chess in international competitions, particularly in human versus computer matches and global tournaments. The article concludes with a discussion of future trends in computer Chinese chess technology.

Keywords

computer Chinese chess artificial intelligence evaluation function opening knowledge base endgame database AlphaZero

Get full access to this article

View all access options for this article.

References

Acher

Esnault

(2016). Large-scale analysis of chess games with chess engines: A preliminary report. arXiv preprint arXiv:1607.04186.

Amdahl

G. M.

(1967). Validity of the single processor approach to achieving large scale computing capabilities. Spring Joint Computer Conference, 483–485. https://doi.org/10.1145/1465482.1465560

Beal

D. F.

(1990). A generalised quiescence search algorithm. Artificial Intelligence, 43(1), 85–98. ISSN 0004-3702. https://doi.org/10.1016/0004-3702(90)90072-8

Browne

C. B.

Powley

Whitehouse

Lucas

S. M.

Cowling

P. I.

Rohlfshagen

Tavener

Perez

Samothrakis

Colton

(2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43. https://doi.org/10.1109/TCIAIG.2012.2186810

Chen

Z.-X.

(1994). A study on Tyng-Jaur-Sha: Checkmate strategy for computer Chinese chess [M.Sc. thesis, Department of Electrical Engineering and Computer Engineering and Science, Yuan Ze University], Taiwan. [in Chinese].

Chen

B.-H.

(1996). Building an integrated environment for Chinese chess based on client/server architecture – The design and implementation of the client program [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

Chen

J.-C.

(2005). Design and implementation of knowledge-base system for computer Chinese chess [Ph.D. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

Chen

H.-H.

(2006). Machine learning of computer Chinese chess , [M.Sc. thesis, Department of Computer Science and Information Engineering, National Yunlin University of Science and Technology], Taiwan. [in Chinese].

Chen

B.-N.

Chen

J.-Y.

Chen

J.-C.

Hsu

T.-S.

Liu

P.-F

Hsu

S.-C

. (2009a). An intelligent tutoring system of Chinese chess. Next-Generation Applied Intelligence: 22nd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2009), 350–359. Springer Berlin Heidelberg.

10.

Chen

J.-C.

Chen

B.-N.

Hsu

T.-S.

(2009b). TMSK wins the Chinese chess tournament. ICGA Journal, 32(2), 102–104. https://doi.org/10.3233/ICG-2009-32211

11.

Chen

B.-N.

Liu

P.-F.

Hsu

S.-C.

Hsu

T.-S.

(2011). Knowledge abstraction in Chinese chess endgame databases. Computers and Games: 7th International Conference (CG 2010), 176–187. Springer Berlin Heidelberg.

12.

Chen

B.-N.

Liu

P.-F.

Hsu

S.-C.

Hsu

T.-S.

(2012). Aggregating consistent endgame knowledge in Chinese chess. Knowledge-Based Systems, 34, 34–42. https://doi.org/10.1016/j.knosys.2011.11.020

13.

Chen

J.-C.

Tseng

W.-J.

I.-C.

Wei

T.-H.

(2018). Comparison training for computer Chinese chess. IEEE Transactions on Games, 12(2), 169–176. https://doi.org/10.1109/TG.2019.2893430

14.

Chen

J.-C.

I.-C.

Tseng

W.-J.

Lin

B.-H.

Chang

C.-H.

(2015). Job-level alpha-beta search. IEEE Transactions on Computational Intelligence and AI in Games, 7(1), 28–38. https://doi.org/10.1109/TCIAIG.2014.2316314

15.

Cheng

M.-C.

(2006). The chess location evaluation tables of Chinese chess program [M.Sc. thesis, Department of Engineering Science, National Cheng Kung University], Taiwan. (in Chinese).

16.

Chess Nade. (2005). http://www.chessms.com/index.html

17.

Chess Programming Wiki. (2022). Chinese chess. https://www.chessprogramming.org/Chinese_Chess

18.

Chinese Chess Encyclopedia. (2004). https://www.xqbase.com/

19.

Chinese Chess Encyclopedia. (2006). Computer Xiangqi League. https://www.xqbase.com/league.htm

20.

Chinese Chess Learning Association. (2021). Rank and level directory. http://cceptw.com/s?p=cae&n=17. [in Chinese]

21.

Cyclone. (2006). http://www.ccyclone.com/

22.

ElephantBase. (2004). Encyclopedia of Chinese chess openings. https://www.xqbase.com/ecco/ecco_intro.htm

23.

ElephantBase. (2008). The 15th Chinese chess AI championship. https://www.xqbase.com/league/express.htm

24.

ElephantEye. (2008). https://github.com/xqbase/eleeye

25.

Fang

H.-R.

Hsu

T.-S.

Hsu

S.-C.

(2001). Construction of Chinese chess endgame databases by retrograde analysis. Computers and Games: Second International Conference (CG 2000), 96–114. Springer Berlin Heidelberg.

26.

Zhao

Jiang

(2019). Application of Q-learning and RBF network in Chinese chess game system. IOP Conference Series: Materials Science and Engineering, 677(2), Article ID 022101. https://doi.org/10.1088/1757-899X/677/2/022101 .

27.

Heinz

E. A.

(1998). Extended futility pruning. ICGA Journal, 21(2), 75–83. https://doi.org/10.3233/ICG-1998-21202

28.

Heinz

E. A.

(1999). Adaptive null-move pruning. ICGA Journal, 22(3), 123–132. https://doi.org/10.3233/ICG-1999-22302

29.

Heng

(2022). Tree search algorithms for Chinese chess. Highlights in Science, Engineering and Technology, 12, 13–24. https://doi.org/10.54097/hset.v12i.1358

30.

Hoki

Muramatsu

(2012). Efficiency of three forward-pruning techniques in shogi: Futility pruning, null-move pruning, and late move reduction (LMR). Entertainment Computing, 3(3), 51–57. https://doi.org/10.1016/j.entcom.2011.11.003

31.

Hsu

S.-C.

Huang

D.-H.

(1985). Design and implementation of a Chinese chess knowledge base. National Computer Symposium (NCS 1985), 505–509. [in Chinese].

32.

Huang

W.-C.

(2006). The design and implementation for the middle game of computer Chinese deep elephant [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University], Taiwan. [in Chinese].

33.

Hyatt

R. M.

Mann

(2002). A lockless transposition-table implementation for parallel search. ICGA Journal, 25(1), 36–39. https://doi.org/10.3233/ICG-2002-25104

34.

Kao

W.-L.

(2009). The automatically tuning system of evaluation function for computer Chinese chess [M.Sc. thesis, Department of Computer Science, National Chiao Tung University], Taiwan. (in Chinese).

35.

Kishimoto

Müller

(2004). A general solution to the graph history interaction problem. 19th National Conference on Artificial Intelligence (AAAI 2004), 644–649.

36.

Knuth

D. E.

Moore

R. W.

(1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326. https://doi.org/10.1016/0004-3702(75)90019-3

37.

Korf

R. E.

(1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97–109. https://doi.org/10.1016/0004-3702(85)90084-0

38.

Lee

T.-R.

(1996). Building an integrated environment for Chinese chess based on client/server architecture – The design and implementation of the server [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

39.

Huang

(2020). Research and implementation of Chinese chess game algorithm based on reinforcement learning. 5th International Conference on Control, Robotics and Cybernetics (CRC 2020), 81–86.

40.

Liao

J.-C.

(1982). An experiment on computer Chinese chess [M.Sc. thesis, Department of Computer Science, National Chiao Tung University], Taiwan. [in Chinese].

41.

Lincke

T. R.

(2001). Strategies for the automatic construction of opening books. Computers and Games: Second International Conference (CG 2000), 74–86. Springer Berlin Heidelberg.

42.

Liu

J.-H.

Lin

J.-S.

Hsu

S.-C.

(1995). A study of checkmate search strategies in computer Chinese chess. Journal of Computers, 7(3-4), 1–9. [in Chinese].

43.

Liu

M.-C.

(2013). The design and implementation of the Chinese chess program Shark [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University], Taiwan. [in Chinese].

44.

Manohararajah

(2001). Parallel alpha-beta search on shared memory multiprocessors [M.Sc. thesis, University of Toronto].

45.

Marsland

T. A.

Campbell

(1982). Parallel search of strongly ordered game trees. ACM Computing Surveys (CSUR), 14(4), 533–551. https://doi.org/10.1145/356893.356895

46.

Matsuzaki

(2018). Empirical analysis of PUCT algorithm with evaluation functions of different quality. 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI), 142–147.

47.

McIlroy-Young

Sen

Kleinberg

Anderson

(2020). Aligning superhuman AI with human behavior: Chess as a model system. 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1677–1687.

48.

Min

J. K.

(2018). Chess and coronary artery ischemia: Clinical implications of machine-learning applications. Circulation: Cardiovascular Imaging, 11(6), e007943. https://doi.org/10.1161/CIRCIMAGING.118.007943

49.

Nalimov

E. V.

Haworth

Heinz

E. A.

(2000). Space-efficient indexing of chess endgame tables. ICGA Journal, 23(3), 148–162. https://doi.org/10.3233/ICG-2000-23304

50.

Newborn

(2000). Deep Blue's contribution to AI. Annals of Mathematics and Artificial Intelligence, 28(1), 27–30. https://doi.org/10.1023/A:1018939819265

51.

NeymarL. (2019). ChineseChess-AlphaZero. GitHub. https://github.com/NeymarL/ChineseChess-AlphaZero

52.

Pham

N. H.

(2018). A completed implementation for Xiangqi rules. ICGA Journal, 40(3), 305–317. https://doi.org/10.3233/ICG-180054

53.

Pham

N. H.

(2024). Felicity Xiangqi (Chinese chess) endgame tablebase. GitHub. https://github.com/nguyenpham/FelicityEgtb

54.

Pikafish. (2024). https://github.com/official-pikafish/Pikafish

55.

Plaat

Schaeffer

Pijls

de Bruin

(1995). An algorithm faster than NegaScout and SSS* in practice. Computer Strategy Game Programming Workshop, 1–16.

56.

Reinefeld

(1983). An improvement to the scout tree search algorithm. ICCA Journal, 6(4), 4–14. https://doi.org/10.3233/ICG-1983-6402

57.

Scheiermann

Konen

(2022). AlphaZero-inspired game learning: Faster training by using MCTS only at test time. IEEE Transactions on Games, 15(4), 637–647. https://doi.org/10.1109/TG.2022.3206733

58.

Schrittwieser

Antonoglou

Hubert

Simonyan

Sifre

Schmitt

Guez

Lockhart

Hassabis

Graepel

Lillicrap

Silver

(2020). Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839), 604–609. https://doi.org/10.1038/s41586-020-03051-4

59.

Schut

Tomasev

McGrath

Hassabis

Paquet

Kim

(2023). Bridging the human-AI knowledge gap: Concept discovery and transfer in AlphaZero. arXiv preprint arXiv:2310.16410.

60.

Shah

N. R.

(2019). Health care in 2030: Will artificial intelligence replace physicians? Annals of Internal Medicine, 170(6), 407–408. https://doi.org/10.7326/M19-0344

61.

Shannon

C. E.

(1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275. https://doi.org/10.1080/14786445008521796

62.

Silver

Huang

Maddison

C. J.

Guez

Sifre

Van Den Driessche

Schrittwieser

Antonoglou

Panneershelvam

Lanctot

Dieleman

Grewe

Nham

Kalchbrenner

Sutskever

Lillicrap

Leach

Kavukcuoglu

Graepel

Hassabis

(2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587), 484–489. https://doi.org/10.1038/nature16961

63.

Silver

Schrittwieser

Simonyan

Antonoglou

Huang

Guez

Hubert

Baker

Lai

Bolton

Chen

Lillicrap

Hui

Sifre

Van Den Driessche

Graepel

Hassabis

(2017). Mastering the game of go without human knowledge. Nature, 550(7676), 354–359. https://doi.org/10.1038/nature24270

64.

Sinclair

(1998). Using example-based reasoning for selective move generation in two player adversarial games. Advances in Case-Based Reasoning: 4th European workshop (EWCBR-98), 126–135. Springer Berlin Heidelberg.

65.

Tao

Pan

(2020). Design and improvement of the pruning algorithm of the Chinese chess in the computer games. The Journal of Engineering, 2020(429), 426–428. https://doi.org/10.1049/joe.2019.1169

66.

Thompson

(1986). Retrograde analysis of certain endgames. ICCA Journal, 9(3), 131–139. https://doi.org/10.3233/ICG-1986-9302

67.

Tsai

H.-C.

(2005). The N-relaxed checking-win search problem in Chinese chess [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

68.

Tsao

K.-M.

(1988). Design and implementation of an intelligent Chinese chess program [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

69.

Tung

Y.-T.

(2003). Design and implement of Chinese chess program DAI [M.Sc. thesis, Department of Computer Science and Information Engineering, National Dong Hwa University], Taiwan. [in Chinese].

70.

(2002). English translation DRAFTS of Asian Rules. http://www.clubxiangqi.com/rules/

71.

K.-C.

(2005). Graph history interaction problem in computer Chinese chess [M.Sc. thesis, Department of Computer Science and Information Engineering, National Taiwan University], Taiwan. [in Chinese].

72.

P.-H.

Liu

P.-Y.

Hsu

T.-S.

(2006). An external-memory retrograde analysis algorithm. Computers and Games: 4th International Conference (CG 2004), 145–160. Springer Berlin Heidelberg.

73.

XQBase. (2004). https://github.com/xqbase

74.

XQWizard. (2010). https://www.xqbase.com/xqwizard/xqwizard.htm

75.

XQWLight. (2008). https://github.com/xqbase/xqwlight

76.

Ding

Zhang

Wang

Yang

(2022). A data-efficient method of deep reinforcement learning for Chinese chess. IEEE 22nd International Conference on Software Quality, Reliability, and Security Companion (QRS-C 2022), 1–8.

77.

Marsland

T. A.

(1992). Experiments in forward pruning with limited extensions. ICCA Journal, 15(2), 55–66. https://doi.org/10.3233/ICG-1992-15202

78.

Yen

S.-J.

Chen

J.-C.

Yang

T.-N.

Hsu

S.-C.

(2004). Computer Chinese chess. ICGA Journal, 27(1), 3–18. https://doi.org/10.3233/ICG-2004-27102

79.

Zhang

Y.-T.

(1981). Artificial intelligence in Chinese chess [M.Sc. thesis, Department of Electrical Engineering, National Taiwan University], Taiwan. [in Chinese].

80.

Zhang

(2023). Chinese Chess competition strategy analysis based on the zero-sum game. Theoretical and Natural Science, 12(1), 32–37. https://doi.org/10.54254/2753-8818/12/20230427

81.

Zhuang

Y.-T.

Chen

Pan

Y.-H.

(2017). Challenges and opportunities: From big data to knowledge in AI 2.0. Frontiers of Information Technology and Electronic Engineering, 18, 3–14. https://doi.org/10.1631/FITEE.1601883

82.

Zobrist

A. L.

(1970). A new hashing method with applications for game playing. Technical Report (88).

Computer Chinese Chess: Past,Present,and Future

Abstract

Keywords

Get full access to this article

References