基于蒙特卡罗树搜索的计算机扑克程序

发布时间：2017-03-29 19:16

  本文关键词：基于蒙特卡罗树搜索的计算机扑克程序，由笔耕文化传播整理发布。

【摘要】：计算机博弈是测试人工智能所达到水平的一个重要平台。早期的研究主要集中在确定性完全信息博弈之上。然而由于与现实之中的问题更加贴近,非确定性非完全信息博弈逐渐引起学术界的重视。 德州扑克是一种非确定性非完全信息博弈。因为它的规则简单同时富于变化,所以其作为这种博弈的一个典型,正在成为计算机博弈研究领域的又一个热点。机器学习中的蒙特卡罗树搜索算法,是一种集成了蒙特卡罗方法作为评估的博弈树搜索算法,毋需引入过多的领域知识,同时具有巨大的可扩展性。多臂匪徒问题是一种从多重决策选择问题之中抽象出来的一种机器学习模型。UCB策略是求解多臂匪徒问题的一种方法。集成UCB策略的基于UCT的蒙特卡罗树搜索算法被证明可以极大地提升计算机博弈引擎水平。 本文结合德州扑克的相关特性改进并设计了德州扑克的蒙特卡罗博弈树,同时对博弈树中的相关节点设计了对应的模拟、选择、回溯更新策略。本文使用C++编程序语言、面向对象技术以及设计模式思想实现了一个德州扑克的博弈引擎。 本文为基于蒙特卡罗树搜索算法的博弈引擎引入了与德州扑克的相关的领域知识,其包括Bucketing的底牌提取,以及在此基础上的基于统计的对手模型用于模拟对手以及估计对手的底牌的概率分布。最后我们提出了一个保守度的概念用于将引擎的下注行为改造成一个比较“松”的策略。 本文设计四个实验来验证纯粹的蒙特卡罗树搜索引擎的性能,并通过分析输出日志,发现了过“紧”的下注策略对于博弈的负面影响。我们测试了在引入保守度后执行一个比较“松”的下注策略时对博弈结果的影响,同时验证集成了对手模型后对于程序博弈水平的提升。 最终,通过实验结果的分析,可以确认,蒙特卡罗树搜索算法可以应用于求解非确定性非完全信息博弈问题。同时在求解德州扑克博弈的问题中,集成领域知识以及对手模型可以提高蒙特卡罗树搜索引擎的性能。
【关键词】：计算机博弈 德州扑克 蒙特卡罗树搜索 对手模型
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 绪论9-12
• 1.1 研究背景9
• 1.2 课题研究内容9-10
• 1.3 课题意义10
• 1.4 论文结构10-12
• 第二章 德州扑克12-21
• 2.1 德克萨斯扑克12-15
• 2.1.1 德州扑克的起源与现状12
• 2.1.2 德州扑克的游戏规则12-14
• 2.1.3 德州扑克的打牌规则14-15
• 2.2 德州扑克的特性描述15-18
• 2.2.1 德州扑克的博弈特性15-17
• 2.2.2 德州扑克的问题复杂度17-18
• 2.3 相关研究18-20
• 2.3.1 基于博弈论理论的研究18-19
• 2.3.2 基于领域知识的研究19
• 2.3.3 基于博弈树的研究19-20
• 2.4 本章小结20-21
• 第三章 传统蒙特卡罗树搜索21-28
• 3.1 博弈树理论21-22
• 3.2 蒙特卡罗树搜索算法22-24
• 3.2.1 蒙特卡罗方法22-23
• 3.2.2 蒙特卡罗树搜索23-24
• 3.3 基于UCT策略的蒙特卡罗树搜索算法24-27
• 3.3.1 UCB1策略25-26
• 3.3.2 博弈树的信息上限UCT策略26-27
• 3.4 本章小结27-28
• 第四章 基于德州扑克的蒙特卡罗树搜索28-45
• 4.1 基于德州扑克的博弈树构造28-32
• 4.1.1 博弈树节点的设计28-30
• 4.1.2 节点状态的转移30-32
• 4.2 博弈树节点的蒙特卡罗模拟32-34
• 4.2.1 叶子节点的蒙特卡罗模拟32
• 4.2.2 决策节点以及对手节点的蒙特卡罗模拟32-33
• 4.2.3 随机节点的蒙特卡罗模拟33-34
• 4.3 博弈树节点的更新回溯以及选择策略34-37
• 4.3.1 叶子节点的更新回溯策略34-35
• 4.3.2 随机节点的回溯与选择策略35
• 4.3.3 决策节点的回溯与选择策略35-36
• 4.3.4 对手节点的回溯与选择策略36-37
• 4.4 博弈引擎的设计与实现37-44
• 4.4.1 博弈树节点的构造37-39
• 4.4.2 蒙特卡罗树搜索的设计与实现39-42
• 4.4.3 博弈引擎的设计与实现42-44
• 4.5 本章小结44-45
• 第五章 领域知识的集成45-53
• 5.1 Buckting底牌提取45-47
• 5.2 基于统计的对手模型47-50
• 5.3 翻牌前的策略积极化50-52
• 5.4 本章小结52-53
• 第六章 实验与结果分析53-56
• 6.1 实验设计与结果分析53-55
• 6.2 本章小结55-56
• 第七章 总结与展望56-58
• 参考文献58-60
• 致谢60-61
• 攻读学位期间发表的学术论文61

【参考文献】

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

1 孙杰;;浅析人工智能[J];内江科技;2011年07期

  本文关键词：基于蒙特卡罗树搜索的计算机扑克程序，由笔耕文化传播整理发布。

，

本文编号：275218