点格棋博弈中UCT算法的研究与实现

发布时间：2017-05-13 17:17

  本文关键词：点格棋博弈中UCT算法的研究与实现，，由笔耕文化传播整理发布。

【摘要】：2016年3月谷歌AlphaGo击败世界围棋冠军李世石九段,使人工智能、机器博弈再次成为大众焦点。人工智能是计算机科学的重要研究方向,主要研究用机器来模拟和执行人脑的智力功能,开发相关的理论和技术,从而达到让机器可以能像人一样进行学习、思考、判断等各种脑力活动的目标。机器博弈因使用计算机解决博弈问题而得名,它将博弈思想和计算机科学相融合,希望计算机能像人一样做出理性决策。机器博弈作为人工智能极具挑战的分支之一,一直以来都被誉为人工智能的“果蝇”,机器博弈的研究对于人工智能的发展具有积极的推动作用。机器博弈在国外的发展较早,并取得了一定的成就；在国内的发展还比较缓慢,以棋类为载体是目前研究机器博弈的主要方法。点格棋是法国数学家爱德华·卢卡斯在1891年提出的二人纸笔游戏。点格棋博弈系统主要由知识表示、着法生成、搜索算法和估值函数四部分组成,其中搜索算法是核心。搜索算法根据当前局面生成一颗一定深度的博弈树,对博弈树进行向下搜索,传统的点格棋博弈系统所采用的搜索算法多为α-β剪枝算法,采用α-β剪枝算法存在搜索深度浅、浪费时间等问题。另一方面α-β剪枝算法必须有一个估值函数对棋盘的优劣进行评估。目前常采用的估值方法当棋盘中不存在安全边的时候会比较准确,但是如果棋盘中含有安全边,估值会由于安全边占领的顺序不同而存在误差,所以点格棋博弈系统的估值函数设计相对较难。UCT算法是蒙特卡洛算法的一种延伸算法,根据大数定理以多次模拟的方式实现对博弈树中节点的价值评估,同时将UCB算法应用到博弈树搜索上,通过UCB算法选择进行评估的节点,引导博弈树向更好的方向生长,有利于更快的获得最优解。UCT算法根据大量模拟棋局的结果以概率的方法进行盘面优劣的判断,预估节点的好坏,优先选择表现好的节点。这种方法解决了点格棋目前存在的盘面评估问题。将UCT算法应用到点格棋博弈,最后通过实验证明采用UCT算法的点格棋博弈系统博弈水平高于α-β剪枝算法。根据点格棋博弈过程中棋盘会存在许多价值相同的边即等价边,这些边选择其中任意一条边进行搜索,与对这些全部进行搜索产生的结果相同,在进行博弈树搜索时只需要对其中一条边进行搜索,据此提出基于等价边裁剪的UCT算法在UCT算法拓展节点阶段进行等价边裁剪。最后通过实验证明改进算法能够减少博弈树搜索时搜索节点的数量,大幅度提高UCT算法的博弈水平。在UCT算法模拟棋局阶段,为提高模拟棋局结束后收益值计算的准确性,在原有计算方法的基础上提出了基于修正值的收益值计算方法,不仅对模拟棋局胜负进行了区分,还对胜负的程度进行了量化,使收益值更加的精确；其次,为提高模拟棋局的次数,实现了基于多核CPU的UCT算法的并行化,充分利用了多核CPU的计算性能,提高棋局的模拟数量。综合以上两点改进提出基于修正收益值的并行UCT算法,通过实验证明基于修正收益值的并行UCT算法可以提高博弈树搜索深度和模拟棋局数量,使UCT算法的博弈水平更高。本文的创新点如下：1.在认真分析点格棋博弈中经常使用的搜索算法后,发现UCT算法相对于传统的α-β剪枝算法有着时间和空间方面的优势,将UCT算法运用到点格棋博弈中。2.提出基于等价边裁剪的UCT算法：给出等价边的定义,在拓展之前进行等价边裁剪,减少博弈树的搜索空间,提高博弈水平。3.提出基于修正收益值的并行UCT算法,包括两个方面改进：第一,提出基于修正值的收益值计算方法,对胜负程度进行区分、量化,提高收益值准确性；第二,为充分利用了计算机性能,提高模拟棋局次数,实现了UCT算法的并行化。
【关键词】：点格棋 机器博弈 UCT算法 等价边 修正收益值
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• Abstract5-10
• 第一章 绪论10-16
• 1.1 研究背景10-12
• 1.2 研究现状12-13
• 1.3 研究意义13-14
• 1.4 本文工作14-16
• 1.4.1 研究内容14-15
• 1.4.2 论文组织结构15-16
• 第二章 点格棋机器博弈技术16-27
• 2.1 点格棋简介17-21
• 2.1.1 规则17-18
• 2.1.2 基本概念18-21
• 2.2 重要定理21-23
• 2.3 点格棋博弈系统构成要素23-26
• 2.3.1 知识表示24-25
• 2.3.2 着法生成25
• 2.3.3 搜索算法25
• 2.3.4 估值函数25-26
• 2.4 本章小结26-27
• 第三章 点格棋博弈中UCT算法的应用27-40
• 3.1 搜索算法介绍27-31
• 3.1.1 博弈树搜索27-29
• 3.1.2 极大极小算法29-30
• 3.1.3 α-β剪枝算法30-31
• 3.2 传统搜索算法的局限性31-33
• 3.3 UCT搜索算法原理33-36
• 3.3.1 蒙特卡洛方法33-34
• 3.3.2 UCB算法34-35
• 3.3.3 UCT算法35-36
• 3.4 点格棋博弈中UCT算法的应用36-39
• 3.4.1 UCT算法应用36-37
• 3.4.2 实验分析37-39
• 3.5 本章小结39-40
• 第四章 基于等价边裁剪的UCT算法40-49
• 4.1 UCT算法拓展节点前期处理40-41
• 4.2 UCT算法拓展节点问题分析41-43
• 4.2.1 UCT算法博弈过程分析41-42
• 4.2.2 拓展节点问题分析42-43
• 4.3 基于等价边裁剪的UCT算法43-46
• 4.3.1 等价边43-45
• 4.3.2 算法描述45-46
• 4.4 实验分析46-48
• 4.4.1 拓展节点数量46-47
• 4.4.2 博弈水平实验47-48
• 4.5 本章小结48-49
• 第五章 基于修正收益值的并行UCT算法49-57
• 5.1 基于修正值的收益值计算方法49-51
• 5.1.1 收益值的重要性49-50
• 5.1.2 基于修正值的收益值计算方法50-51
• 5.2 基于修正收益值的并行UCT算法51-53
• 5.2.1 UCT算法的并行化51-52
• 5.2.2 算法描述52-53
• 5.3 实验分析53-56
• 5.3.1 参数优化53-54
• 5.3.2 搜索深度实验54-55
• 5.3.3 模拟棋局数量实验55-56
• 5.4 本章小结56-57
• 第六章 点格棋博弈系统的设计与实现57-62
• 6.1 系统设计57-59
• 6.1.1 系统总体结构57-58
• 6.1.2 系统流程图58-59
• 6.2 系统实现59-61
• 6.3 本章小结61-62
• 第七章 总结与展望62-65
• 7.1 本文的主要贡献与结论62-63
• 7.2 未来工作与展望63-65
• 参考文献65-69
• 致谢69-70
• 攻读硕士期间的科研项目与获奖70

【相似文献】

中国期刊全文数据库 前2条

1 苏黔;;如何调整彩电的会聚[J];电气时代;1986年02期

2 ;[J];;年期

中国重要报纸全文数据库 前1条

1 王石川;年轻人稍微出点格，不是坏事[N];东莞日报;2014年

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

1 刘洋;点格棋博弈中UCT算法的研究与实现[D];安徽大学;2016年

2 刘慧慧;改性涤纶织物的结构设计及性能研究[D];北京服装学院;2012年

  本文关键词：点格棋博弈中UCT算法的研究与实现，由笔耕文化传播整理发布。

本文编号：363150