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

发布时间：2017-04-17 02:19

  本文关键词：基于改进博弈树的黑白棋设计与实现，由笔耕文化传播整理发布。

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

• 摘要5-7
• Abstract7-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

【引证文献】

中国硕士学位论文全文数据库 前1条

1 曹森;对α-β剪枝算法的性能改进研究[D];内蒙古师范大学;2012年

  本文关键词：基于改进博弈树的黑白棋设计与实现，，由笔耕文化传播整理发布。

本文编号：312215