中国象棋属于EXPTIME-complete问题  

Chinese Chess Being EXPTIME-complete

作　　者：高强[1] 徐心和[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004

出　　处：《重庆理工大学学报（自然科学）》2014年第8期85-91,131,共8页Journal of Chongqing University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61370153)

摘　　要：寻找棋类游戏的理想解是计算机博弈研究的目标,而计算复杂性是不可逾越的障碍。首先介绍了计算复杂性类中的EXPTIME-complete问题及它的一个实例——G3游戏。构建了一个n×n中国象棋的归约模型,模型由6部分组成,分别为布尔控制器、开关、子句通道与文字通道的交叉区域、兑子区域、延迟区域及九宫。在该模型上模拟进行G3游戏,并最终证明了G3游戏可多项式时间内归约到n×n的中国象棋,从而证明了n×n的中国象棋属于EXPTIMEcomplete问题。The main objective of research on computer game is looking for an ideal invincible solution of the board games. However,computational complexity is an insurmountable obstacle in the process of solving. Firstly,this article introduces EXPTIME-complete problem of computational complexity and an example of it,G3 game. An n × n Chinese Chess position is constructed,and this position consists of six components which include Boolean controller,switch,the crossing of clause-channel and literal-channel,exchanging chess zone,delay zone and Nine-palace. G3 game is simulated on the position,and hence it is proved that G3 is reducible to n × n Chinese Chess in polynomial time,and then Chinese Chess is EXPTIME-complete.

关 键 词：计算机博弈 中国象棋 计算复杂性 指数时间的完全问题 归约 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]