学位论文 > 优秀研究生学位论文题录展示
基于UCT算法的非完备信息多人军棋博弈系统
作 者: 张加佳
导 师: 王轩
学 校: 哈尔滨工业大学
专 业: 计算机科学与技术
关键词: UCT算法 非完备信息博弈 蒙特卡罗抽样 风险评估模型 自动博弈
分类号: O225
类 型: 硕士论文
年 份: 2008年
下 载: 75次
引 用: 1次
阅 读: 论文下载
内容摘要
博弈游戏的分类方法之一是根据其游戏的参与者是否拥有完备的游戏信息。据此,博弈游戏可以被分为完备信息博弈和非完备信息博弈两个大类。在非完备信息博弈过程中,每个游戏者拥有自己单独的信息集,也就是说,他只拥有整个游戏的部分信息。围绕着完备信息博弈的研究已经取得了相对成熟的结果。很多人工智能程序的核心架构是:当电脑走棋的时候,根据当前棋局创建一个部分的博弈树,利用估值函数对叶结点进行估值,通过估值的结果来进行极大极小值搜索,找到一个在根结点的最佳走步。然而,迄今为止非完备信息下的非常成功的人工智能博弈程序很少。非完备信息博弈问题的解决技术和完备信息有很大的差异,应用于完备信息的技术不一定能够成功的应用到非完备信息博弈中。蒙特卡罗抽样算法是现今应用于非完备信息博弈中的一个基本方法,它通过随机抽样将非完备信息博弈问题转换为完备信息博弈问题,同时通过大规模的抽样次数来逼近真实的情况。该方法在一些非完备信息博弈游戏中,例如Alberta的桥牌程序,已经取得了较好的效果。UCT (Upper Confidence Bound Apply to Tree):应用于博弈搜索树的上限置信区间算法。这种新兴的搜索算法采用以上限置信值为依据的先深于先广搜索相结合的方法,在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。在与风险评估模型相结合的基础上,可以在可控的时间内得到当前局势下的相对较优的解决方案。本文探讨了UCT算法在非完备信息博弈中超大规模搜索树搜索过程中的应用,并基于该算法结合蒙特卡罗抽样技术和风险评估模型实现了一个具有自动网上挂载功能的四国军棋博弈系统。本文的主要研究成果和创新之处在于:1.实现了UCT搜索算法,并将之应用为博弈系统的搜索核心。提高了系统的搜索速度和深度;2.进一步扩充和精确化了四国军旗博弈中的蒙特卡罗抽样技术;3.在已有四国军棋的框架系统上,将蒙特卡罗抽样技术、UCT算法和一个简单的风险模型有效结合成了一个具有更强的博弈能力和更高的人工智能水平的新系统。4.新的四国军棋系统可以自动挂载到网络和人类玩家进行博弈,该功能解决了系统棋力客观评估的问题,同时使大规模博弈过程以及对局信息数据库的建立成为了可能。
|
全文目录
摘要 4-6 Abstract 6-10 第1章 绪论 10-14 1.1 课题背景 10 1.2 研究目的和意义 10-11 1.3 UCT 搜索算法的历史和现状 11-13 1.3.1 UCT 搜索算法的历史 11-12 1.3.2 UCT 搜索算法研究的现状 12-13 1.4 课题主要研究内容及论文结构 13-14 第2章 基于蒙特卡罗抽样的非完备信息博弈 14-29 2.1 完备信息博弈 14-20 2.1.1 机器博弈系统 14-16 2.1.2 机器博弈中的搜索算法 16-20 2.2 非完备信息博弈和蒙特卡罗抽样 20-23 2.3 蒙特卡罗抽样过程示例 23-27 2.3.1 对当前世界的猜测过程 24-27 2.3.2 最佳走步链表的建立与查询 27 2.4 本章小结 27-29 第3章 基于 UCT 搜索算法的非完备信息博弈 29-42 3.1 UCT 搜索算法原理 29-35 3.1.1 K-臂赌博机问题 29 3.1.2 UCB1 算法描述 29-30 3.1.3 UCT:UCB 算法的博弈树搜索应用 30-32 3.1.4 UCT 搜索与经典博弈树搜索算法的比较 32-35 3.2 UCT 在非完备信息博弈中的应用 35-38 3.2.1 UCT 算法模块与蒙特卡罗抽样算法的结合 35-36 3.2.2 非完备信息机器博弈中的上限置信区间 36-38 3.3 简单风险模型——UCT 算法的进一步完备 38-41 3.3.1 风险的博弈论定义 38-40 3.3.2 与 UCT 搜索相结合的风险规避 40-41 3.4 本章小结 41-42 第4章 四国军旗机器博弈系统 42-51 4.1 四国军旗系统简介 42-46 4.1.1 数据表示 42-43 4.1.2 系统构架 43-44 4.1.3 估值函数 44-46 4.2 实验结果分析 46-50 4.2.1 与四国军棋博弈系统 V2.0 版的对比试验 47-48 4.2.2 与人类玩家的网络测试 48-50 4.3 本章小结 50-51 结论 51-53 参考文献 53-57 攻读硕士学位期间发表的学术论文 57-59 致谢 59-60 简历 60-62
|
相似论文
- 科技型企业并购的文化风险评估研究,F276.44;F224
- Q-学习在非完备信息机器博弈中的应用,TP18
- 计算机围棋博弈中UCT算法的应用及改进,TP18
- 基于BS7799的信息安全风险评估研究与设计,TP309
- 神经网络技术在商业银行信用风险评估系统中的应用研究,TP319
- 银行贷款风险评估,F830.5
- 大中型穿越河流输油管道的风险评估,TE973
- 我国商业银行信用风险管理研究,F224
- 商业银行信息系统风险评估模型的设计与实现,TP311.52
- 信息安全风险评估模型的研究及其应用,TP309
- 我国商业银行中小企业信用评级体系研究,F832.2
- 河南省养猪业风险管理研究,F326.3
- 建筑火灾风险评估模型研究,TU998.1
- 河南省冬小麦干旱风险分析与评估技术研究,S423
- 商业银行业务流程再造前风险的评估与规避研究,F830.33
- 基于GIS的地质灾害风险评估系统研发与应用,P208
- 软件项目风险评估与控制研究,F224
- 资本充足率要求与银行对策研究,F830
- 商业银行风险评估方法浅析,F832.3
- 风险投资项目综合评价模式及应用研究,F830.59
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 对策论(博弈论)
© 2012 www.xueweilunwen.com
|