[1]WEI Yinfu,LI Zhoujun.A method for calculating the total number of states of Chinese chess on the basis of dynamic programming[J].CAAI Transactions on Intelligent Systems,2019,14(1):108-114.[doi:10.11992/tis.201803008]
Copy

A method for calculating the total number of states of Chinese chess on the basis of dynamic programming

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 14 Number of periods: 2019 1 Page number: 108-114 Column: 学术论文—自然语言处理与理解 Public date: 2019-01-05
Title:
A method for calculating the total number of states of Chinese chess on the basis of dynamic programming
Author(s):
WEI Yinfu;  LI Zhoujun
The Institute of Intelligent Information Processing, School of Computer Science and Engineering, Beihang University, Beijing 100191, China
Keywords:
computer games; Chinese chess; combinatorial counting; space complexity; dynamic programming; counting method; problem solving; state space
CLC:
TP301.6
DOI:
10.11992/tis.201803008
Abstract:
The space complexity of Chinese chess is a primary index for analyzing the complexity of Chinese chess, which is a counting problem of calculating the number of states of Chinese chess. Given the features of Chinese chess, this problem can be divided into several subproblems that can be solved by dynamic programming to obtain a precise solution of the total number of states of Chinese chess. Our results show that the total number of states of Chinese chess mentioned in previous papers is inaccurate and much higher than the actual number of states (1039.88). Finally, the main idea of the counting method was summarized based on dynamic programming, and illustrations for some uses of the method were provided.
References:
[1] 王晓鹏, 王骄, 徐心和, 等. 中国象棋与国际象棋比较分析[J]. 重庆工学院学报, 2007, 21(1):71-76 WANG Xiaopeng, WANG Jiao, XU Xinhe, et al. A comparative analysis between chess and Chinese chess[J]. Journal of Chongqing institute of technology, 2007, 21(1):71-76
[2] 徐心和, 郑新颖. 棋牌游戏与事件对策[J]. 控制与决策, 2007, 22(7):787-790 XU Xinhe, ZHENG Xinying. Card and board games and event game theory[J]. Control and decision, 2007, 22(7):787-790
[3] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587):484-489.
[4] SILVER D, SCHRITTWIESER J, SIMONYAN K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676):354-359.
[5] SILVER D, HUBERT T, SCHRITTWIESER J, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm[J]. arXiv:1712.01815, 2017.
[6] 高强, 郭琛. 哈希技术在中国象棋机器博弈系统中的应用研究[J]. 科学技术与工程, 2008, 8(17):4869-4872 GAO Qiang, GUO Chen. Technology of hashing and its application research in hybrid game tree search engine of Chinese chess[J]. Science technology and engineering, 2008, 8(17):4869-4872
[7] 王骄, 徐长明, 徐心和. 中国象棋计算机博弈残局处理系统[C]//2006中国机器博弈学术研讨会. 北京, 中国, 2006. WANG Jiao, XU Changming, XU Xinhe. Endgame system in computer Chinese chess[C]//2006 Chinese Computer Games Seminar. Beijing, China, 2006.
[8] 吴丽贤, 和力. 一种中国象棋残局棋谱自动生成算法[J]. 云南民族大学学报(自然科学版), 2010, 19(6):435-438 WU Lixian, HE Li. An automatic generation algorithm for the manual of Chinese chess endgames[J]. Journal of Yunnan university of nationalities (natural sciences edition), 2010, 19(6):435-438
[9] 马麟. 关于中国象棋的发展论述[J]. 求知导刊, 2016(2):31 MA Lin. The develop of Chinese chess[J]. Journal of seeking knowledge guide, 2016(2):31
[10] 黄晨. 棋类游戏中的先行权[J]. 智能系统学报, 2007, 2(3):91-94 HUANG Chen. The first-move advantage in board games[J]. CAAI transactions on intelligent systems, 2007, 2(3):91-94
[11] 王玉霞. 组合计数中的映射原理及应用[J]. 喀什师范学院学报, 2005, 26(3):31-32 WANG Yuxia. Mapping principle of combinational counting[J]. Journal of Kashgar teachers college, 2005, 26(3):31-32
[12] 胡冠章. 组合计数的群论与计算机方法[J]. 数学进展, 1997, 26(1):1-12 HU Guanzhang. Group theory and computer methods for combinatorial enumerations[J]. Advances in mathematics, 1997, 26(1):1-12
[13] 曹博瑞, 刘铁. 映射法研究组合计数问题[J]. 文理导航, 2017(11):4 CAO Borui, LIU Tie. Solve combinational counting problem by mapping[J]. Guiding on art and science, 2017(11):4
[14] 王跃进. 映射观点下一些组合问题及其计数公式[J]. 上海中学数学, 2007(11):40-41 WANG Yuejin. Several combinational counting problem based on mapping[J]. Middle school math of Shanghai, 2007(11):40-41
[15] 高见元. 动态规划算法的运用方法探讨[J]. 软件导刊, 2007(10):136-138 GAO Jianyuan. Research on dynamic programming algorithm[J]. Software guide, 2007(10):136-138
[16] 宛楠, 张义. 动态规划算法分析[J]. 长江大学学报(自然科学版), 2013, 10(7):34-36 WAN Nan, ZHANG Yi. The analysis of dynamic algorithm[J]. Journal of Yangtze university (natural science edition), 2013, 10(7):34-36
[17] 徐付霞. 大型动态规划的分解算法[J]. 唐山师专学报, 1998, 22(5):6-9 XU Fuxia. Decomposable algorithm for large dynamic programming[J]. Journal of Tangshan normal university, 1998, 22(5):6-9
[18] 王军祥. 动态规划算法原理及应用研究[J]. 电脑知识与技术, 2006(36):150-151 WANG Junxiang. Research on the principle and application of dynamic programming algorithm[J]. Computer knowledge and technology, 2006(36):150-151
[19] ALLIS L V. Searching for solutions in games and artificial intelligence[D]. The Netherlands:University of Limburg, 1994.
[20] 涂志坚. 电脑象棋的设计与实现[D]. 广州:中山大学, 2004. TU Zhijian. Design and implementation of computer Xiangqi[D]. Guangzhou:Sun Yat-sen University, 2004.
[21] 徐心和, 王骄. 中国象棋计算机博弈关键技术分析[J]. 小型微型计算机系统, 2006, 27(6):961-969 XU Xinhe, WANG Jiao. Key technologies analysis of Chinese chess computer game[J]. Mini-micro systems, 2006, 27(6):961-969
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems