点格棋博弈中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算法的并行化。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究现状

1．3 研究意义

1．4 本文工作

1．4．1 研究内容

1．4．2 论文组织结构

第二章 点格棋机器博弈技术

2．1 点格棋简介

2．1．1 规则

2．1．2 基本概念

2．2 重要定理

2．3 点格棋博弈系统构成要素

2．3．1 知识表示

2．3．2 着法生成

2．3．3 搜索算法

2．3．4 估值函数

2．4 本章小结

第三章 点格棋博弈中UCT算法的应用

3．1 搜索算法介绍

3．1．1 博弈树搜索

3．1．2 极大极小算法

3．1．3 α—β剪枝算法

3．2 传统搜索算法的局限性

3．3 UCT搜索算法原理

3．3．1 蒙特卡洛方法

3．3．2 UCB算法

3．3．3 UCT算法

3．4 点格棋博弈中OCT算法的应用

3．4．1 UCT算法应用

3．4．2 实验分析

3．5 本章小结

第四章 基于等价边裁剪的UCT算法

4．1 UCT算法拓展节点前期处理

4．2 UCT算法拓展节点问题分析

4．2．1 UCT算法博弈过程分析

4．2．2 拓展节点问题分析

4．3 基于等价边裁剪的UCT算法

4．3．1 等价边

4．3．2 算法描述

4．4 实验分析

4．4．1 拓展节点数量

4．4．2 博弈水平实验

4．5 本章小结

第五章 基于修正收益值的并行UCT算法

5．1 基于修正值的收益值计算方法

5．1．1 收益值的重要性

5．1．2 基于修正值的收益值计算方法

5．2 基于修正收益值的并行UCT算法

5．2．1 UCT算法的并行化

5．2．2 算法描述

5．3 实验分析

5．3．1 参数优化

5．3．2 搜索深度实验

5．3．3 模拟棋局数量实验

5．4 本章小结

第六章 点格棋博弈系统的设计与实现

6．1 系统设计

6．1．1 系统总体结构

6．1．2 系统流程图

6．2 系统实现

6．3 本章小结

第七章 总结与展望

7．1 本文的主要贡献与结论

7．2 未来工作与展望

参考文献

致谢

攻读硕士期间的科研项目与获奖