论文总字数：24426字

摘 要

随着蒙特卡洛树搜索在完全信息博弈领域尤其是在围棋中取得巨大成功，研究者开始将目光投向非完全信息博弈。德州扑克作为一款风靡全球的非完全信息博弈游戏，也同样受到研究者的青睐。

本论文基于蒙特卡洛树搜索算法，结合Smooth UCT算法和虚拟博弈的思想，在德州扑克环境中实现了一个有一定竞争力的AI程序，并在库恩扑克和德州扑克环境下对UCT算法和Smooth UCT算法进行了比较和分析，当应用于大规模游戏德州扑克游戏时，在短时间的训练中，两种算法的差距并不能完全体现，但在库恩扑克这种小规模游戏中，两种算法的差距明显，Smooth UCT算法快速收敛于近似纳什均衡，不仅继承了UCT算法快速的学习速度，而且相比UCT算法可以学得更优的策略。

关键词：蒙特卡洛树搜索，UCT算法，虚拟博弈，纳什均衡

ABSTRACT

With the Monte Carlo tree search in the field of complete information game, especially in Go, the researchers have begun to look at the incomplete information game. As a global non-complete information game, Texas Hold'em is also favored by researchers.

Based on the Monte Carlo tree search algorithm, combined with the idea of Smooth UCT algorithm and virtual game, this paper implements a competitive AI program in the Texas Hold'em environment, and UCT algorithm in Kuhn Poker and Texas Hold'em. The Smooth UCT algorithm is compared and analyzed. When applied to large-scale game Texas Hold'em, the gap between the two algorithms is not fully reflected in the short-time training, but in the small-scale game of Kuhn Poker, two The gap between the algorithms is obvious. The Smooth UCT algorithm converges to the approximate Nash equilibrium quickly, which not only inherits the fast learning speed of the UCT algorithm, but also can learn a better strategy than the UCT algorithm.

Keywords: Monte Carlo tree search, UCT algorithm, virtual game, Nash equilibrium

目 录

摘 要 3

ABSTRACT 4

第一章 绪论 1

1.1引言 1

1.2相关研究现状 1

1.3研究目标和内容 2

1.4论文组织结构 2

第二章 背景知识 3

2.1蒙特卡洛树搜索 3

2.1.1蒙特卡洛树搜索过程简介 3

2.1.2蒙特卡洛树搜索中的UCT算法 3

2.2博弈论相关背景知识 5

2.2.1对称与非对称博弈 5

2.2.2完全信息与非完全信息博弈 5

2.2.3零和与非零和博弈 5

2.2.4扩展形式博弈 5

2.2.5纳什均衡 6

2.2.6正则形式博弈 6

2.3虚拟博弈 6

2.4德州扑克简介及其他相关工作 7

2.5德州扑克中的抽象方法 8

2.5.1手牌同构算法 9

2.5.2基于手牌强度的抽象算法 9

2.5.3基于对手集群手牌强度的抽象算法 9

2.6本章小结 11

第三章 基于蒙特卡洛树搜索的自博弈算法 12

3.1非完全信息博弈下的UCT算法 12

3.2结合虚拟博弈的Smooth UCT算法 13

3.3本章小结 14

第四章 实验环境及设置 15

4.1Kuhn扑克 15

4.2二人有限注德州扑克 15

4.3本章小结 16

第五章 实验结果 17

5.1 Kuhn扑克 17

5.2二人有限注德州扑克 18

5.3本章小结 20

第六章 总结 21

参考文献 22

致谢 24

第一章 绪论

1.1引言

计算机博弈是人工智能领域的重要的研究方向之一，通常，根据博弈的信息是否可以完全获取，博弈问题可以分为完全信息博弈和非完全信息博弈。近几年研究者在很多大规模完全信息博弈如围棋等问题上获得了很大的成功，因此研究者们开始将目光渐渐转移向一些相对复杂的非完全信息博弈问题上。相对于完全信息博弈，非完全信息博弈意味着参与者无法得到全部的信息，只能获得一部分信息，这与现实生活相近，更加复杂的同时也更具有现实意义。

德州扑克作为一款全球风靡的非完全信息游戏，也是非完全信息博弈游戏中的典型，德州扑克玩法并不复杂，但却拥有大量的游戏状态，未知的公共牌和对手手牌等构成了各种不完整的信息和不确定性的元素，这对于研究者来说，无疑是巨大的挑战。

1.2相关研究现状

1998年，阿尔伯塔大学的Billings等人基于手牌牌力的估计开发了第一个扑克AI程序Lokibot，并达到了人类玩家的平均水平，由于 Lokibot应对所有的对手的方法都相同，策略缺乏足够的变化，不能根据不同的对手调整策略，因此研究者针对这个问题，提出对手建模的概念^[26]，算法经过改进后可以在游戏的过程中不断统计对手的历史行为，并根据对手的历史行为信息动态的调整自己的策略。

Darse等人在2003年提出^[27]，由于德州扑克游戏规模过大，可以以一定的方法对游戏状态进行合理的抽象，进一步推进了扑克游戏人工智能的发展，随后卡内基梅隆大学的研究者Glipin等人提出了一种不需要结合人类经验的自动的状态抽象算法，使用自动的抽象算法来合并德州扑克游戏中的相似的状态，可以在很大程度上降低博弈树的规模，研究者据此实现的人工智能程序在当年的ACPC比赛中拿下了第一名的成绩，在之后的研究和改进的过程中，该团队有提出可以对下注等动作离散化来进一步降低非限制德州扑克的环境下巨大动作空间。

2007年，阿尔伯塔大学的Zinkevich等人提出了CFR算法^[12]，这种算法通过最小化虚拟的遗憾值，来求解二人德州扑克环境下的近似纳什均衡，但由于CFR算法需要在每次迭代过程中遍历整个博弈树，这大大降低了算法的效率，对此Johanson等人在2012年提出了基于采样的CFR算法，不需要在每次迭代过程中遍历整个博弈树，而是通过抽样的方式选择性的遍历一部分，从而在很大程度上提高了CFR算法收敛的速度。虽然如此，CFR算法在在迭代过程中的收敛速度依然缓慢，对此，卡内基梅隆大学提出了基于蒙特卡洛抽样的虚拟遗憾最小化算法，采用蒙特卡洛抽象的方法来提高算法的性能，经过在匹兹堡超级计算机中心的长时间的计算之后，在第二届的二人非限制德州扑克比赛中击败了人类中的德州扑克顶尖选手，取得了巨大的成功。

剩余内容已隐藏，请支付后下载全文，论文总字数：24426字