学位论文 > 优秀研究生学位论文题录展示

中国象棋博弈树搜索算法研究与实现

作　者: 宋兴亮
导　师: 田翠华
学　校: 沈阳工业大学
专　业: 计算机应用技术
关键词: 计算机博弈搜索算法博弈系统评估函数
分类号: TP391.3
类　型: 硕士论文
年　份: 2012年
下　载: 125次
引　用: 0次
阅　读: 论文下载

内容摘要

计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。二者相辅相成,相互促进。国际象棋计算机博弈已经比较成熟,历史悠久的中国象棋计算机博弈很多技术还不够成熟,随着对人工智能的深入研究,对中国象棋博弈的研究成为人工智能研究的热点之一。本文对中国象棋博弈树搜索算法以及博弈系统进行研究,介绍了中国象棋计算机博弈的关键技术,分析了数据结构设计和评估函数在系统中所起的作用。深入研究博弈树的特性以及基于α-β剪枝的博弈树搜索算法的改进策略,包括窗口原则、历史表法、置换表法、空着搜索等,结合不同的改进策略得到不同的搜索引擎,对这些引擎的性能进行测试,验证它们的剪枝效率。研究了静态搜索,在静态搜索中加入吃子走法排序和将军延伸,解决了博弈树搜索的水平效应。实现一个人机博弈系统,实现生成并显示棋谱,统计搜索引擎每次搜索的叶节点和所用的时间,结合不同的优化策略得到不同的搜索引擎,通过实验证明综合多种改进策略的搜索算法的剪枝效率得到了提高。选取剪枝效率较高的搜索引擎结合静态搜索提高棋力,让这些新的搜索引擎对弈,证明了剪枝效率最高的PVSHNTIQ搜索算法的棋力也最高。

全文目录

摘要  5-6
Abstract  6-9
第一章绪论  9-13
  1.1 课题的研究背景  9
  1.2 国内外研究现状  9-11
    1.2.1 国外研究现状  9-10
    1.2.2 国内研究现状  10-11
  1.3 论文结构  11-13
第二章数据结构设计  13-20
  2.1 棋局状态表示  13-16
    2.1.1 棋盘表示  13-15
    2.1.2 棋子表示  15-16
  2.2 走法生成  16-18
    2.2.1 走法表示  17
    2.2.2 走法生成  17-18
  2.3 棋局辅助信息  18-20
第三章局面评估函数  20-24
  3.1 局面评估函数组成部分  20-22
    3.1.1 固定子力价值  20-21
    3.1.2 棋子的位置价值  21
    3.1.3 其它评估因素  21-22
  3.2 局面评估函数与博弈系统的关系  22-24
第四章博弈树搜索算法研究  24-48
  4.1 博弈树搜索  24-26
    4.1.1 搜索  24-25
    4.1.2 中国象棋博弈树  25-26
  4.2 基本的搜索算法  26-35
    4.2.1 极大极小值算法  26-29
    4.2.2 α-β剪枝算法  29-33
    4.2.3 α-β剪枝算法的性能分析  33-35
  4.3 基于窗口原则的改进策略  35-40
    4.3.1 Fail-Soft alpha-beta算法  35-36
    4.3.2 渴望搜索  36-38
    4.3.3 极小窗口搜索  38-39
    4.3.4 基于窗口原则搜索算法小结  39-40
  4.4 博弈树节点排序  40-42
    4.4.1 吃子走法启发  40-41
    4.4.2 杀手启发  41
    4.4.3 历史表启发  41-42
  4.5 置换表  42-44
  4.6 迭代加深  44-45
  4.7 水平效应与静态搜索  45-46
  4.8 裁剪算法  46-48
    4.8.1 无害裁剪  46
    4.8.2 空着裁剪  46-48
第五章系统实现与实验分析  48-66
  5.1 走法生成与局面评估函数  48-50
  5.2 优化策略实现  50-57
    5.2.1 历史表实现  50
    5.2.2 置换表实现  50-52
    5.2.3 迭代加深实现  52-55
    5.2.4 静态搜索实现  55-57
  5.3 系统实现  57-63
    5.3.1 系统功能介绍  57-59
    5.3.2 综合搜索算法  59-63
  5.4 实验分析  63-66
第六章结论  66-67
参考文献  67-69
在学研究成果  69-70
致谢  70

中国象棋博弈树搜索算法研究与实现

内容摘要

全文目录

相似论文