摘要
寻找棋类游戏的理想解是计算机博弈研究的目标,而计算复杂性是不可逾越的障碍。首先介绍了计算复杂性类中的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.
出处
《重庆理工大学学报（自然科学）》
CAS
2014年第8期85-91,131,共8页
Journal of Chongqing University of Technology：Natural Science
基金
国家自然科学基金资助项目(61370153)
