基于UCT算法的非完备信息多人军棋博弈系统

论文摘要

博弈游戏的分类方法之一是根据其游戏的参与者是否拥有完备的游戏信息。据此,博弈游戏可以被分为完备信息博弈和非完备信息博弈两个大类。在非完备信息博弈过程中,每个游戏者拥有自己单独的信息集,也就是说,他只拥有整个游戏的部分信息。围绕着完备信息博弈的研究已经取得了相对成熟的结果。很多人工智能程序的核心架构是:当电脑走棋的时候,根据当前棋局创建一个部分的博弈树,利用估值函数对叶结点进行估值,通过估值的结果来进行极大极小值搜索,找到一个在根结点的最佳走步。然而,迄今为止非完备信息下的非常成功的人工智能博弈程序很少。非完备信息博弈问题的解决技术和完备信息有很大的差异,应用于完备信息的技术不一定能够成功的应用到非完备信息博弈中。蒙特卡罗抽样算法是现今应用于非完备信息博弈中的一个基本方法,它通过随机抽样将非完备信息博弈问题转换为完备信息博弈问题,同时通过大规模的抽样次数来逼近真实的情况。该方法在一些非完备信息博弈游戏中,例如Alberta的桥牌程序,已经取得了较好的效果。UCT (Upper Confidence Bound Apply to Tree):应用于博弈搜索树的上限置信区间算法。这种新兴的搜索算法采用以上限置信值为依据的先深于先广搜索相结合的方法,在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上,可以在可控的时间内得到当前局势下的相对较优的解决方案。本文探讨了UCT算法在非完备信息博弈中超大规模搜索树搜索过程中的应用,并基于该算法结合蒙特卡罗抽样技术和风险评估模型实现了一个具有自动网上挂载功能的四国军棋博弈系统。本文的主要研究成果和创新之处在于:1.实现了UCT搜索算法,并将之应用为博弈系统的搜索核心。提高了系统的搜索速度和深度;2.进一步扩充和精确化了四国军旗博弈中的蒙特卡罗抽样技术;3.在已有四国军棋的框架系统上,将蒙特卡罗抽样技术、UCT算法和一个简单的风险模型有效结合成了一个具有更强的博弈能力和更高的人工智能水平的新系统。4.新的四国军棋系统可以自动挂载到网络和人类玩家进行博弈,该功能解决了系统棋力客观评估的问题,同时使大规模博弈过程以及对局信息数据库的建立成为了可能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究目的和意义
• 1.3 UCT 搜索算法的历史和现状
• 1.3.1 UCT 搜索算法的历史
• 1.3.2 UCT 搜索算法研究的现状
• 1.4 课题主要研究内容及论文结构
• 第2章 基于蒙特卡罗抽样的非完备信息博弈
• 2.1 完备信息博弈
• 2.1.1 机器博弈系统
• 2.1.2 机器博弈中的搜索算法
• 2.2 非完备信息博弈和蒙特卡罗抽样
• 2.3 蒙特卡罗抽样过程示例
• 2.3.1 对当前世界的猜测过程
• 2.3.2 最佳走步链表的建立与查询
• 2.4 本章小结
• 第3章 基于 UCT 搜索算法的非完备信息博弈
• 3.1 UCT 搜索算法原理
• 3.1.1 K-臂赌博机问题
• 3.1.2 UCB1 算法描述
• 3.1.3 UCT:UCB 算法的博弈树搜索应用
• 3.1.4 UCT 搜索与经典博弈树搜索算法的比较
• 3.2 UCT 在非完备信息博弈中的应用
• 3.2.1 UCT 算法模块与蒙特卡罗抽样算法的结合
• 3.2.2 非完备信息机器博弈中的上限置信区间
• 3.3 简单风险模型——UCT 算法的进一步完备
• 3.3.1 风险的博弈论定义
• 3.3.2 与 UCT 搜索相结合的风险规避
• 3.4 本章小结
• 第4章 四国军旗机器博弈系统
• 4.1 四国军旗系统简介
• 4.1.1 数据表示
• 4.1.2 系统构架
• 4.1.3 估值函数
• 4.2 实验结果分析
• 4.2.1 与四国军棋博弈系统 V2.0 版的对比试验
• 4.2.2 与人类玩家的网络测试
• 4.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢
• 简历