| 摘要 | 第5-7页 |
| Abstract | 第7-9页 |
| 第一章 绪论 | 第14-26页 |
| 1.1 研究背景与动机 | 第14-18页 |
| 1.2 国内外相关研究的现状与分析 | 第18-22页 |
| 1.2.1 机器博弈研究的现状与分析 | 第18-19页 |
| 1.2.2 机器博弈问题计算复杂性研究的现状与分析 | 第19-20页 |
| 1.2.3 机器博弈问题理论解研究的现状与分析 | 第20-22页 |
| 1.2.4 证据计数法研究现状与分析 | 第22页 |
| 1.3 研究内容 | 第22-24页 |
| 1.3.1 博弈问题的计算复杂性 | 第23页 |
| 1.3.2 博弈问题的状态复杂度和博弈树复杂度 | 第23页 |
| 1.3.3 证据计数法 | 第23-24页 |
| 1.3.4 博弈问题的理论解 | 第24页 |
| 1.4 本文组织结构 | 第24-26页 |
| 第二章 面向非合作动态博弈问题的搜索算法综述 | 第26-44页 |
| 2.1 引言 | 第26-29页 |
| 2.2 非合作动态博弈问题的复杂性与可解性 | 第29-31页 |
| 2.2.1 非合作动态博弈问题的复杂性 | 第29-30页 |
| 2.2.2 非合作动态博弈问题的可解性 | 第30-31页 |
| 2.3 基本搜索算法 | 第31-34页 |
| 2.3.1 极小-极大搜索(Mini-Max Search) | 第31-32页 |
| 2.3.2 Alpha-Beta搜索(Alpha-Beta Search) | 第32-33页 |
| 2.3.3 负极大值算法(Nega-Max Algorithm) | 第33-34页 |
| 2.4 基于Alpha-Beta剪枝的高级搜索算法 | 第34-39页 |
| 2.4.1 迭代加深搜索(Iterative deepening search) | 第34-35页 |
| 2.4.2 面向着法排序的alpha-beta搜索 | 第35页 |
| 2.4.3 面向窗口大小的alpha-beta搜索 | 第35-36页 |
| 2.4.4 几种启发式搜索 | 第36-39页 |
| 2.5 几种新算法 | 第39-43页 |
| 2.5.1 基于蒙特卡洛模拟的博弈树搜索 | 第39-41页 |
| 2.5.2 基于威胁的搜索(TSS-Threat Space Search) | 第41-42页 |
| 2.5.3 证据计数搜索(PN-Proof Number Search) | 第42-43页 |
| 2.6 本章小结 | 第43-44页 |
| 第三章 计算复杂性研究 | 第44-60页 |
| 3.1 引言 | 第44页 |
| 3.2 有关计算复杂性 | 第44-49页 |
| 3.2.1 可判定问题 | 第44页 |
| 3.2.2 语言 | 第44-45页 |
| 3.2.3 有穷自动机与下推自动机 | 第45-46页 |
| 3.2.4 确定型图灵机及非确定型图灵机 | 第46-48页 |
| 3.2.5 映射可归约性 | 第48-49页 |
| 3.3 时间复杂性 | 第49-54页 |
| 3.3.1 P(确定型多项式时间复杂性) | 第49-50页 |
| 3.3.2 NP(非确定型多项式时间复杂性) | 第50-51页 |
| 3.3.3 NP问题是非多项式时间问题 | 第51页 |
| 3.3.4 NP-complete (NP的完全问题) | 第51-53页 |
| 3.3.5 EXPTIME(指数时间复杂性) | 第53-54页 |
| 3.4 空间复杂性 | 第54-56页 |
| 3.4.1 PSPACE(确定型多项式空间复杂性) | 第54-55页 |
| 3.4.2 NPSPACE | 第55页 |
| 3.4.3 PSPACE-complete(PSPACE的完全问题) | 第55-56页 |
| 3.5 各种复杂性类之间的关系 | 第56-58页 |
| 3.5.1 P与NP的关系 | 第57页 |
| 3.5.2 时间复杂性(P和NP)与空间复杂性的关系 | 第57页 |
| 3.5.3 空间复杂性与EXPTIME的关系 | 第57-58页 |
| 3.6 本章小结 | 第58-60页 |
| 第四章 中国象棋计算复杂性研究 | 第60-78页 |
| 4.1 引言 | 第60-64页 |
| 4.1.1 EXPTIME-complete问题 | 第63页 |
| 4.1.2 G_3游戏 | 第63-64页 |
| 4.2 中国象棋计算复杂性的证明 | 第64-66页 |
| 4.2.1 n×n中国象棋的定义 | 第64-65页 |
| 4.2.2 n×n中国象棋的计算复杂性 | 第65-66页 |
| 4.3 归约模型的构建 | 第66-73页 |
| 4.3.1 归约模型中各构件的说明 | 第66-71页 |
| 4.3.2 赢棋策略 | 第71-73页 |
| 4.4 不恰当走法分析 | 第73-75页 |
| 4.4.1 布尔控制器(RBC)中可能存在的不恰当走法 | 第73-74页 |
| 4.4.2 开关中可能存在的不恰当走法 | 第74页 |
| 4.4.3 子句通道与文字通道的交叉点处可能存在的不恰当走法 | 第74-75页 |
| 4.5 结论 | 第75-76页 |
| 4.6 本章小结 | 第76-78页 |
| 第五章 博弈问题状态复杂度和博弈树复杂度估算方法研究 | 第78-86页 |
| 5.1 引言 | 第78-79页 |
| 5.2 博弈问题的状态复杂度 | 第79-82页 |
| 5.2.1 博弈问题的状态复杂度定义 | 第79页 |
| 5.2.2 亚马逊棋的状态复杂度 | 第79-81页 |
| 5.2.3 苏拉卡尔塔棋的状态复杂度 | 第81-82页 |
| 5.3 博弈问题的博弈树复杂度 | 第82-85页 |
| 5.3.1 博弈树搜索算法原理 | 第82页 |
| 5.3.2 博弈树复杂度的定义 | 第82-83页 |
| 5.3.3 六子棋的博弈树复杂度 | 第83-84页 |
| 5.3.4 点格棋的博弈树复杂度 | 第84-85页 |
| 5.4 本章小结 | 第85-86页 |
| 第六章 证据计数法研究 | 第86-100页 |
| 6.1 引言 | 第86页 |
| 6.2 证据计数法( Proof-Number search) | 第86-90页 |
| 6.2.1 一种与或树模型 | 第86-88页 |
| 6.2.2 证据计数法的定义及工作原理 | 第88-89页 |
| 6.2.3 证据计数法的特点及应用 | 第89-90页 |
| 6.3 证据计数法在落子类机器博弈中的应用 | 第90-91页 |
| 6.3.1 证据计数法在五子棋(Go-Moku)中的应用 | 第90页 |
| 6.3.2 证据计数法在六子棋中的应用 | 第90-91页 |
| 6.3.3 证据计数法在围棋中的应用 | 第91页 |
| 6.4 证据计数法存在的缺陷及PN~2算法 | 第91-92页 |
| 6.4.1 证据计数法的缺点 | 第91-92页 |
| 6.4.2 PN~2搜索算法 | 第92页 |
| 6.5 一种改进的两级PN算法 | 第92-96页 |
| 6.5.1 PN-DFPN算法的定义 | 第92-95页 |
| 6.5.2 应用于求解六子棋的PN-DFPN算法设计 | 第95-96页 |
| 6.6 实验 | 第96-98页 |
| 6.7 本章小结 | 第98-100页 |
| 第七章 计算机博弈问题的理论解研究 | 第100-116页 |
| 7.1 引言 | 第100页 |
| 7.2 计算机博弈问题理论解的相关知识 | 第100-101页 |
| 7.2.1 博弈问题被求解等级的分类 | 第100-101页 |
| 7.2.2 博弈问题的复杂度与求解方法的关系 | 第101页 |
| 7.3 一些已被求解的常见博弈问题 | 第101-104页 |
| 7.3.1 五子棋(Go-Moku) | 第101-102页 |
| 7.3.2 西洋跳棋 | 第102-104页 |
| 7.3.3 围棋残局 | 第104页 |
| 7.4 求解牛角棋 | 第104-107页 |
| 7.4.1 牛角棋的走棋规则 | 第104-105页 |
| 7.4.2 牛角棋的状态复杂度及博弈树复杂度 | 第105-106页 |
| 7.4.3 牛角棋求解采用的搜索策略 | 第106-107页 |
| 7.4.4 结果 | 第107页 |
| 7.5 一种基于连珠类型的六子棋求解策略 | 第107-114页 |
| 7.5.1 基于连珠类型的着法产生器 | 第108-109页 |
| 7.5.2 搜索策略 | 第109-111页 |
| 7.5.3 用到的一些主要的辅助算法 | 第111页 |
| 7.5.4 一种基于迫着数的搜索算法调用策略 | 第111-112页 |
| 7.5.5 实验 | 第112-114页 |
| 7.6 本章小结 | 第114-116页 |
| 第八章 结束语 | 第116-118页 |
| 8.1 本文的主要贡献 | 第116-117页 |
| 8.2 未来研究工作的展望 | 第117-118页 |
| 参考文献 | 第118-126页 |
| 致谢 | 第126-128页 |
| 攻博期间参加的科研项目 | 第128-130页 |
| 攻读博士期间发表的论著 | 第130页 |
