一种融合劫的开放域UCT算法研究

发布时间：2017-10-12 16:29

  本文关键词：一种融合劫的开放域UCT算法研究

  更多相关文章： 计算机围棋 开放域UCT算法 劫

【摘要】：UCT(信心上限树)算法的提出在计算机围棋领域具有重大的意义,它在很大程度上提高了计算机围棋程序的水平。基于UCT算法的围棋程序在小型棋盘上已经达到了专业棋手的水平,例如9×9棋盘,但是在大型棋盘仍然不尽人意,仅仅达到业余水平,例如19×19棋盘。一个重要的原因是在大型棋盘中,多个局部争夺战比较容易同时出现。而它们的出现使UCT算法顾此失彼,性能很差。一种流行的改进方案是全局搜索算法和局部搜索算法的结合。在局部搜索中我们首先需要确定搜索范围。本文我们提出一种独特的确定搜索范围的方法,并通过实验分析它的准确性和有效性,并从中发现了一些有关于劫的问题。本文主要内容如下：1)讨论计算机围棋的特点,困难,并简单介绍了围棋搜索中的经典算法。2)提出在开放域棋谱中确定搜索范围的方法。通过计算棋子和边界吸收空白点影响力的大小,来确定空白点的归属区间,从而划定搜索范围。最终实现开放域UCT算法的局部搜索。最后在围棋死活问题集上通过实验证明该方法的有效性。3)在开放域UCT算法的实验中,我们发现,在处理围棋死活问题时,UCT算法对劫的处理效果很差。因此,我们在UCT中加入对劫的识别和处理,并且通过实验来说明加入劫之后的UCT算法的性能的改善。
【关键词】：计算机围棋 开放域UCT算法 劫
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：G891.3;TP18
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-16
• 1.1 研究背景与意义10-11
• 1.2 国内外研究现状11-13
• 1.3 本文的主要工作13-14
• 1.3.1 开放域UCT算法的实现13
• 1.3.2 融合劫的开放域UCT算法13-14
• 1.4 本文的章节安排14-16
• 第二章 围棋基本知识16-24
• 2.1 围棋基本规则16-19
• 2.1.1 围棋下棋规则17-18
• 2.1.2 围棋终局规则和胜负计算规则18-19
• 2.2 围棋基本概念19-21
• 2.2.1 紧气与长气19-20
• 2.2.2 劫20
• 2.2.3 眼20-21
• 2.3 围棋等级21-22
• 2.4 围棋的死活问题22-23
• 2.5 本章小结23-24
• 第三章 计算机围棋24-38
• 3.1 计算机围棋的特点24-26
• 3.1.1 目标的总体效应性24
• 3.1.2 搜索空间巨大24-25
• 3.1.3 复杂的形式判断25
• 3.1.4 盘面评估和博弈树搜索的紧密性25-26
• 3.2 计算机围棋的主要困难26
• 3.3 计算机围棋的经典搜索算法26-36
• 3.3.1 负极大搜索27-28
• 3.3.2 α-β搜索算法28-30
• 3.3.3 蒙特卡洛树搜索算法30-33
• 3.3.4 围棋中的蒙特卡洛树搜索算法33-34
• 3.3.5 UCB算法34-36
• 3.4 本章小结36-38
• 第四章 开放域UCT算法38-54
• 4.1 引言38-39
• 4.2 相关工作39-40
• 4.3 开放域空间40-41
• 4.4 UCT算法41-45
• 4.5 开放域UCT算法45-48
• 4.5.1 Fuego46-47
• 4.5.2 开放域UCT的实现47-48
• 4.6 实验以及结果分析48-53
• 4.6.1 实验数据48-49
• 4.6.2 围棋边界颜色测试49-50
• 4.6.3 准确性50-51
• 4.6.4 有效性51-53
• 4.7 本章小结53-54
• 第五章 融合劫的开放域UCT算法54-60
• 5.1 引言54-55
• 5.2 相关工作55
• 5.3 融合劫的开放域UCT算法55-57
• 5.3.1 劫的识别55-57
• 5.3.2 劫价值的处理57
• 5.4 实验和结果分析57-58
• 5.5 本章小结58-60
• 第六章 结论和展望60-62
• 6.1 本文的主要工作总结60
• 6.2 下一步的工作展望60-61
• 6.3 本章小结61-62
• 致谢62-64
• 参考文献64-68
• 附录A 攻读学位期间发表的论文及参加科研项目68

，

本文编号：1019774