基于虚拟遗憾最小化算法的德州扑克机器博弈研究

摘要

德州扑克是风靡全球的扑克游戏，是非完备信息机器博弈的典型代表。游戏中的随机发牌导致了信息的不确定性，博弈者无法得到对手的手牌信息致使信息具有不完备性，四轮的押注决策使游戏具有重复性等。德州扑克的非确定性非完备性等特点决定了其博弈树具有指数级的游戏状态，如简单的两人限注德州扑克玩法，游戏的整个博弈树包括3.19×1017个游戏状态。对于德州扑克这类博弈状态呈指数级增长的游戏，虚拟遗憾最小化算法(Counterfactual Regret Minimization,CFR)是目前最先进的能够生成高效策略的技术之一。CFR算法通过多次迭代计算博弈树中每个信息集的动作遗憾值和平均策略值，预测下一时刻的决策动作，使其是当前最小遗憾动作。如何存储大量迭代计算产生的遗憾值、平均策略值和计算效率是CFR算法面临的两大挑战。本课题针对以上问题展开研究，对CFR算法进行了改进，实现了具有较高智能水平的德州扑克机器博弈系统。
　　本课题实现的德州扑克智能体使用基于9-Bucketing策略的底牌抽取技术对德州扑克游戏进行抽象，降低了德州扑克状态空间复杂度。基于蒙特卡罗CFR算法的抽样思想和Pure CFR算法的整数运算思想，本课题提出了两种改进的CFR算法，根据离线训练和在线博弈时处理对手策略的不同方式，课题将改进的算法称为离线学习对手策略的CFR算法和在线自适应对手策略的CFR算法。这两种改进算法与原始的CFR算法相比，提高了计算效率和博弈的胜率，降低了存储要求。本课题根据改进的CFR算法产生的最优化策略选取未来的决策行为时，结合使用欺诈策略，避免了被对手建模。2014年，本课题使用CFR算法实现的3-Kuhn扑克机器博弈智能体在国际人工智能协会(AAAI)举办的世界年度计算机扑克机器博弈大赛(ACPC)的3-Kuhn扑克项目中获得了铜奖，随后根据本课题改进的两种CFR算法实现的德州扑克机器博弈智能体在与往年ACPC大赛决赛阶段的部分参赛智能体的机器博弈对比实验中也取得了胜利。
　　在日常生活中，经常需要在信息不完善或不确定的情况下做决策，这和德州扑克等非完备信息机器博弈游戏的决策过程相似。CFR算法从使遗憾最小化的角度调整策略，这可以用来解决很多现实问题，比如拍卖场上与谈判桌上的最优策略、股票博弈系统等等。

目录

第1章 绪 论

1.1 课题背景及意义

1.2 国内外相关技术研究现状

1.3 主要研究内容和组织结构

第2章 机器博弈基本理论

2.1 正则博弈和扩展式博弈

2.2 信息集

2.3 纳什均衡和劣策略

2.4 Kuhn扑克

2.5 德州扑克

2.6 本章小结

第3章 虚拟遗憾最小化算法研究

3.1 遗憾最小化算法

3.2 虚拟遗憾最小化算法(CFR)

3.3 蒙特卡罗虚拟遗憾最小化算法(MCCFR)

3.4 纯虚拟遗憾最小化算法(Pure CFR)

3.5 一种改进的虚拟遗憾最小化算法(CFR+)

3.6 虚拟遗憾最小化算法的德州扑克决策模型

3.7 本章小结

第4章 实验与结果分析

4.1 实验系统结构

4.2 实验数据的搜集与整理

4.3 实验结果分析

4.4 本章小结

结论

参考文献

附录

附录A 德州扑克游戏

附录B 计算机德州扑克大赛

声明

致谢