重庆理工大学学报（自然科学版）Issue(8)：85-91,131,8.DOI:10.3969/j.issn.1674-8425(z).2014.08.018
中国象棋属于EXPTIME-complete问题
Chinese Chess Being EXPTIME-complete
摘要
Abstract
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.关键词
计算机博弈/中国象棋/计算复杂性/指数时间的完全问题/归约Key words
computer games/Chinese chess/computational complexity/EXPTIME-complete/reduc-ibility分类
信息技术与安全科学引用本文复制引用
高强,徐心和..中国象棋属于EXPTIME-complete问题[J].重庆理工大学学报（自然科学版）,2014,(8):85-91,131,8.基金项目
国家自然科学基金资助项目 （）
