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

基于改进博弈树的黑白棋设计与实现

作　者: 李小舟
导　师: 吴一民；李时锦
学　校: 华南理工大学
专　业: 软件工程
关键词: 黑白棋博弈树搜索模板匹配自学习
分类号: TP18
类　型: 硕士论文
年　份: 2010年
下　载: 171次
引　用: 0次
阅　读: 论文下载

内容摘要

计算机的人工智能(Artificial Intelligence,简称AI)研究一直是人类一个富于挑战的实践。让计算机具有智能,是科研学者一直为之奋斗的课题。而在计算机AI的研究领域中,让传统的棋类博弈游戏具有智能,一直是人们关注和研究的内容。棋类博弈人工智能,一般包括博弈搜索、局面评估两个方面。顶尖的博弈智能系统还具备自学习的能力,在对局中通过学习不断地提高AI。各种棋类游戏虽然玩法各异,都是基本的博弈算法是通用。其中,作为博弈游戏AI最核心的博弈树搜索算法,是整个博弈AI的基础,同时也是最核心的内容。所以,对博弈树搜索算法的研究和设计,具有重要的现实意义。本论文就是通过对博弈搜索关键技术的分析,设计和实现一个基于改进博弈树搜索算法的黑白棋对弈系统。本论文对基于改进博弈树的黑白棋设计与实现工作,主要体现在以下几个方面:一、对博弈游戏核心的博弈树搜索算法等关键技术进行了较全面的研究和分析。从基本的min-max算法、alpha-beta剪枝、到基于启发式的优化策略、基于期望窗口和有损剪枝的优化策略,到使用多处理器的并行博弈计算等;尽量做到了全面而又系统,为后面的博弈树搜索算法的设计和改进奠定了基础。二、以面向对象的设计思想,设计和实现黑白棋的人工智能对弈系统。在设计上,采用了完全面向对象的方法,把人工智能的各个方面抽象成人类智能对应的推理、分析、记忆和自学习几个方面,然后对这几个部分分别进行设计,改变了以往以算法为核心的形式。三、在黑白棋博弈树搜索算法的实现上,对原来的博弈树搜索算法进行了一定改进。自行设计了一个基于双置换表、浅层探测启发和―杀手‖启发的搜索算法,并且具备动态选择要排序的结点进行排序的能力。这样大大提高了alpha-beta剪枝的效率。同时使用零窗口搜索的MTD(f)方法,一方面提高了效率,另一方面有利于以后的并行计算实现的扩展。四、黑白棋的下棋规则和局面评估方面,使用了位棋盘的数据结构的设计和基于模板匹配的局面评估方法,最大程度地提高了下棋的效率和AI。位棋盘和基于模板匹配的方法是黑白棋程序现阶段先进的设计方法,同时也是其它棋类系统设计的发展趋势。五、在黑白棋对弈系统开局库和自学习方面:开局库并没有使用传统的树型结构,而是使用基于一维线性表的二分查找方法来实现。同时,区别于一般的系统的自学习能力,就是自学习除了可以提高AI之外,还可以不断地提高下棋效率。最后,通过测试,改进的启发式博弈树搜索比原alpha-beta搜索和传统的启发搜索在效率上有了相当的提高。同时经测试,本黑白棋人工智能对弈系统已经具备了较高的智能,具有一定的研究和使用意义。

全文目录

摘要  5-7
Abstract  7-11
第一章绪论  11-16
  1.1 计算机棋弈人工智能的发展概况  11-13
    1.1.1 冯诺依曼的博弈论和图灵的纸上机器  11
    1.1.2 alpha-beta 剪枝的博弈搜索的出现  11-12
    1.1.3 基于alpha-beta 剪枝的算法发展  12-13
    1.1.4 棋局分析技术的发展  13
    1.1.5 自学习能力的引入  13
  1.2 黑白棋计算机博弈的发展概况  13-14
  1.3 本文的主要研究内容及意义  14-15
  1.4 本文结构  15-16
第二章博弈树搜索理论与技术的分析  16-29
  2.1 博弈树和极大-极小搜索  16-18
  2.2 局面评估——叶子结点的计算  18-19
  2.3 alpha-beta 剪枝搜索  19-22
  2.4 提高alpha-beta 剪枝的方法  22-25
    2.4.1 结点有序  22-24
    2.4.2 期望窗口  24-25
  2.5 一些其它的策略  25-29
    2.5.1 并行与串行的优化  25-27
    2.5.2 选择性搜索策略  27-29
第三章黑白棋系统基于面向对象的设计  29-36
  3.1 黑白棋的概述  29-30
  3.2 面向对象的系统设计  30-32
  3.3 棋盘数据结构的设计  32-35
  3.4 本章小结  35-36
第四章黑白棋博弈树搜索的改进设计  36-47
  4.1 基于启发式alpha-beta 搜索的优化设计  36-40
    4.1.1 启发式的搜索  36-37
    4.1.2 使用0-窗口的alpha-beta 搜索  37-40
  4.2 置换表启发  40-44
    4.2.1 置换表的设计  40-42
    4.2.2 基于双置换表的优化实现  42-44
  4.3 “杀手”启发的实现  44-45
  4.4 动态选择排序结点  45-46
  4.5 终局搜索的实现  46
  4.6 本章小结  46-47
第五章黑白棋局面评估和基于开局库学习的实现  47-54
  5.1 黑白棋局面评估的实现  47-50
    5.1.1 基于模板匹配的局面评估的实现  47-49
    5.1.2 基于统计学计算模板分值  49-50
    5.1.3 棋局样本的选择  50
  5.2 开局库的实现  50-52
    5.2.1 基础开局库的实现  50-51
    5.2.2 开局库基于胜率下棋的改进  51-52
  5.3 基于开局库的自学习  52
  5.4 本章小结  52-54
第六章系统AI 的测试与分析  54-58
  6.1 改进的博弈树搜索效果测试  54
  6.2 系统AI 效果的测试  54-56
  6.3 结果分析  56-58
结论  58-60
参考文献  60-62
致谢  62

基于改进博弈树的黑白棋设计与实现

内容摘要

全文目录

相似论文