“德州扑克AI之父”再发新论文：“冷扑大师2.0”要来了？

2018 年 11 月 23 日 全球人工智能

来源：arXix,新智元

最近，Arxiv上的一篇题为《Solving Imperfect-Information Games via Discounted Regret Minimization》引发关注，原因主要在于本文的两位作者的鼎鼎大名，CMU计算机系博士生Noam Brown，以及该校计算机系教授Tuomas Sandholm。这两位就是去年的著名的德州扑克AI程序“冷扑大师”（Libratus）的缔造者，堪称德州扑克AI之父。

“冷扑大师”在去年曾与4位人类专业德州扑克牌手大战20天，最后全面获胜。两位作者还去Reddit论坛的机器学习板块上搞了一次“Ask me anything”的网友问答互动，一时名声大噪。阐述“冷扑大师”背景技术的论文也被评为NIPS 2017最佳论文。

“冷扑大师”在2017年的人机德州扑克大赛面对4位专业人类牌手，全部获胜

时隔一年多，二位大师再次发布关于不完全信息博弈策略的论文，仍主要以德州扑克为测试基准平台，难道“冷扑大师”2.0就要来了？人类牌手们，准备好（再次）被碾压了吗？

一起看看这篇文章都讲了些什么。

论文地址：

https://arxiv.org/abs/1809.04040

摘要

Counterfactual regret minimization（CFR）是目前很流行的一系列迭代算法，实际上也是近似解决大型不完美信息游戏的最快的AI算法。本算法系列中提出了一个“后悔值” （regrets）的概念，即在当前状态下，选择行为A，而不是行为B，后悔的值是多少。

在本文中，我们介绍了一些CFR算法的一些新变化，其中包括1）采用多种方法从早期迭代中减低“后悔值”（regret）（在某些情况下对正面和负面后悔值使用不同策略）。（2）以各种方式对迭代进行重新加权，以获得更佳的输出策略。（3）使用非标准化的后悔值最小化策略。（4）利用optimistic regret matching。这些方法可以在诸多环境中显著提高性能。

首先，我们在每个测试的游戏中引入一个优化的CFR +的变体算法，这是之前最先进的算法。CFR+是一个强大的基准，没有其他算法能够超越它。我们表明，与CFR +不同，许多基于CFR的重要的新算法与现代不完全信息游戏修剪技术兼容，而且与游戏树中的样本兼容。

论文内容提要

不完全信息博弈模拟互相拥有隐藏信息的玩家之间的战略互搏，比如谈判、网络安全和拍卖都是属于此类。扑克游戏是这类博弈的常用测试基准。

这种测试的一般目标是找到一种（近似的）均衡，在这种均衡状态下，没有玩家可以通过偏离该均衡状态来提高自己的收益。对于线性程序无法应对的的极大规模的不完全信息博弈，通常使用迭代算法来近似均衡。

CFR方法的主要思想是把游戏中所有状态都考虑到，生成一颗完整的状态树。对树的每一个节点都初始化一个策略，然后根据这个策略来玩游戏。每次都走状态树的一条边，然后根据游戏的结果来更新相关节点的策略。

当CFR进行了许多次迭代之后，这个状态树的每条路径都被遍历了很多次，每个节点的策略都被更新趋于均衡了，从而得到一个可以玩游戏的AI。

实验中使用的游戏——德州扑克和Goofspiel

德州扑克是测试不完全信息博弈算法表现的典型游戏。在本文中使用无限制Heads-up德州扑克规则。两位玩家（P1和P2）起手筹码各为20000美元，大/小盲注为50/100美元。每轮加注不得少于100美元。让对方筹码降至0者获胜。

除了德州扑克外，本文采用了另一种纸牌游戏Goofspiel，两位玩家各拥有5张手牌(A、2、3、4、5)，牌桌中间有5张牌的奖励牌堆，牌堆中的牌也是A\2\3\4\5。每轮从牌堆中先翻开最上面的牌作为奖励牌，然后两名牌手同时出一张手牌比大小，胜者赢得奖励牌，用过的手牌被弃掉。最后以奖励牌总分数（A为1分、2为2分，以此类推）多者获胜。

实验：CFR的几种变体和CFR+基准

我们的实验针对德州扑克进行了32768次迭代，对Goofspiel进行了8192次迭代。由于是近似均衡，而不是精确均衡，所以何时终止迭代计算很大程度上取决于实验者，一般取100-1000次迭代的结果就是有意义的。

所有实验都使用CFR的交替更新形式。我们衡量两个玩家的平均可利用性。我们的实验表明，在某些游戏中，线性CFR（LCFR）可以在合理的时间范围内显着提高CFR +的性能。

然而，LCFR在实际实验中的表现似乎比CFR+差。线性CFR在Subgame1和3中的表现特别好，与Subgame2和4相比，相对于每个玩家可以下注的最高金额，底池中筹码价值很小，这时更容易出现严重的错误行为。在Goofspiel中，线性CFR同样表现不佳，这表明线性CFR特别适合可能出现严重错误的游戏。

NormalHedge CFR（NH）是一个在游戏中每个信息集中独立应用regret最小化的框架。通常，我们使用Regret Matching（RM）作为实现后悔最小化的工具，主要是由于无参数的特点和简单的实现形式。但是，我们也可以应用任何其他实现regret最小化的工具。