[1]魏印福,李舟军.动态规划求解中国象棋状态总数[J].智能系统学报,2019,14(1):108-114.[doi:10.11992/tis.201803008]
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]
点击复制
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]
动态规划求解中国象棋状态总数
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
14
期数:
2019年第1期
页码:
108-114
栏目:
学术论文—自然语言处理与理解
出版日期:
2019-01-05
- Title:
- A method for calculating the total number of states of Chinese chess on the basis of dynamic programming
- Keywords:
- computer games; Chinese chess; combinatorial counting; space complexity; dynamic programming; counting method; problem solving; state space
- 分类号:
- TP301.6
- 摘要:
- 中国象棋空间复杂度是分析中国象棋博弈难度的重要指标，中国象棋空间复杂度分析是一个计数问题，即求解中国象棋状态总数。根据中国象棋棋子的着法特征，该问题可分解为若干子问题，利用动态规划分别解决这些子问题，能够求出中国象棋状态总数的精确解。实验得出中国象棋状态总数约为7.54×1039.88，过去许多文献描述的中国象棋状态总数是不准确的，远远高估了中国象棋状态总数。基于动态规划的计数方法也可以用于计算其他棋类的空间复杂度，也能够用于寻找空间复杂度较低的残局棋型，为构建中国象棋残局库提供依据。
- 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
- 相似文献/References:
-
[1]魏钦刚,王? 骄,徐心和,等.中国象棋计算机博弈开局库研究与设计[J].智能系统学报,2007,2(1):85.
WEI Qin gang,WANG Jiao,XU Xin he,et al.A study and design of openingbook of computer Chinese C h ess[J].CAAI Transactions on Intelligent Systems,2007,2():85.
[2]黄? 晨.棋类游戏中的先行权[J].智能系统学报,2007,2(3):91.
HUANG Chen.The firstmove advantage in board games[J].CAAI Transactions on Intelligent Systems,2007,2():91.
[3]王亚杰,邱虹坤,吴燕燕,等.计算机博弈的研究与发展[J].智能系统学报,2016,11(6):788.[doi:10.11992/tis.201609006]
WANG Yajie,QIU Hongkun,WU Yanyan,et al.Research and development of computer games[J].CAAI Transactions on Intelligent Systems,2016,11():788.[doi:10.11992/tis.201609006]
[4]李霞丽,吴立成,李永集.基于棋型的藏族“久”棋计算机博弈研究[J].智能系统学报,2018,13(4):577.[doi:10.11992/tis.201609023]
LI Xiali,WU Licheng,LI Yongji.Tibetan JIU computer game research based on chess form[J].CAAI Transactions on Intelligent Systems,2018,13():577.[doi:10.11992/tis.201609023]
[5]高强,徐心和,王昊,等.一种基于经验的德州扑克博弈系统架构[J].智能系统学报,2020,15(3):468.[doi:10.11992/tis.201803043]
GAO Qiang,XU Xinhe,WANG Hao,et al.System architecture of Texas Hold’em based on experience[J].CAAI Transactions on Intelligent Systems,2020,15():468.[doi:10.11992/tis.201803043]
[6]李淑琴,陈子鹏,郑蓝舟,等.竞技二打一游戏中同等牌力的研究[J].智能系统学报,2021,16(3):466.[doi:10.11992/tis.202007005]
LI Shuqin,CHEN Zipeng,ZHENG Lanzhou,et al.Research on the equal card force competition system of competitive two against one game[J].CAAI Transactions on Intelligent Systems,2021,16():466.[doi:10.11992/tis.202007005]
备注/Memo
收稿日期:2018-03-08。
作者简介:魏印福,男,1993年生,硕士研究生,主要研究方向为自然语言处理、计算机博弈;李舟军,男,1963年生,教授,博士生导师。IEEE会员,ACM会员,AAAI会员,中国计算机学会高级会员,计算机安全专业委员会常务委员,主要研究方向为网络安全、数据挖掘、自然语言处理。发表学术论文180余篇,其中被SCI和EI收录150余篇,合著出版的2部教材分别获得部委级科技成果二、三等奖。
通讯作者:魏印福.E-mail:wei.yinfu@qq.com
更新日期/Last Update:
1900-01-01