基于蒙特卡洛搜索树的德州扑克AI算法设计与实现文献综述

1、MCTS

MCTS是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是计算机围棋程序，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

MCTS通常分为四步，第一步是Selection，就是在树中找到一个最好的值得探索的节点，一般策略是先选择未被探索的子节点，如果都探索果就通过UCB算法选择一个子节点。第二步是Expansion，就是在前面选中的子节点走一步创建一个新的子节点。第三步是Simulation，就是在前面新创建的节点开始模拟游戏，直到游戏结束，这样就可以得到游戏的结果。第四步是Backpropagation，就是把前面得到的信息更新到之前的父节点中。

蒙特卡洛树搜索的一个很成功的应用是AlphaGo Zero，它相比AlphaGo更强，通过结合强化学习与蒙特卡洛树，不需要专家经验的参与，系统从一个一无所知的神经网络开始，然后通过将这种神经网络与强大的搜索算法相结合，MCTS通过神经网络来指导它的模拟过程，神经网络通过自我强化学习训练，使用MCTS计算每个落子动作。经过仅仅三天的自我训练，就击败了之前的AlphaGo版本。

2、UCT

蒙特卡洛树搜索中选择子结点的主要困难是在较高平均胜率的移动后对深层次变型的利用和对少数模拟移动的探索二者中保持某种平衡。第一个在游戏中平衡利用与探索的公式被称为UCT（Upper Confidence Bounds to Trees，上限置信区间算法 ），由匈牙利国家科学院计算机与自动化研究所高级研究员列文特·科奇什与阿尔伯塔大学全职教授乔鲍·塞派什瓦里提出。UCT基于奥尔（Auer）、西萨-比安奇（Cesa-Bianchi）和费舍尔（Fischer）提出的UCB1公式，并首次由马库斯等人应用于多级决策模型（具体为马尔可夫决策过程）。

Ponsen等在计算机扑克游戏中比较了UCT 和结果采样两种算法，结果表示UCT算法可以很快的找到一个较好但是并非最好的策略，而结果采样最初的学习速度很慢，但最终可以收敛到最优策略。

Smooth UCT是UCT算法的一个变种，这个算法让AI将平均策略和他们通常采用的效用最大的策略结合，试图在保留UCT快速学习速度的同时，克服UCT算法无法收敛到纳什均衡的缺点。Johannes Heinrich等人在两种小型扑克游戏kuhn扑克和Leduc扑克中比较了这两种算法，与UCT相比，Smooth UCT更接近与纳什均衡。此外，在二人和三人LHE中，Smooth UCT的表现也优于UCT，并在2014年ACPC上获得了三枚银牌。