中国象棋属于EXPTIME-complete问题

• 作者: 徐心和 高强
• 来源期刊: 重庆理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 计算机博弈 中国象棋 计算复杂性 指数时间的完全问题 归约
• 年，卷（期）: 2014,（8）
• 所属期刊栏目: 信息?计算机
• 页码范围: 85-91,131
• 页数: 8页
• 分类号: TP301.5
• 字数: 6207字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-8425(z).2014.08.018

摘要

寻找棋类游戏的理想解是计算机博弈研究的目标，而计算复杂性是不可逾越的障碍。首先介绍了计算复杂性类中的EXPTIME-complete问题及它的一个实例---G3游戏。构建了一个n×n中国象棋的归约模型，模型由6部分组成，分别为布尔控制器、开关、子句通道与文字通道的交叉区域、兑子区域、延迟区域及九宫。在该模型上模拟进行G3游戏，并最终证明了G3游戏可多项式时间内归约到n ×n的中国象棋，从而证明了n ×n的中国象棋属于EXPTIME-complete问题。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐心和	东北大学信息科学与工程学院	295	7536	42.0	73.0
2	高强	东北大学信息科学与工程学院	4	8	2.0	2.0