冷扑大师背后的AI算法和博弈论：CFR算法是核心

昨天下午，量子位在中关村举办了一个技术沙龙，邀请创新工场AI工程院技术VP李天放、联想智慧医疗CEO林林等，从技术和实战的角度，对德州扑克人机大战进行解读。

以下是李天放对德州扑克AI的技术解读

文字版本整理如下

AI算法和博弈论，这两个交叉点还是有一点难度的。

先从博弈论开始。

大家需要对GTO/纳什平衡有一个初期的理解。在德州扑克，翻硬币，剪刀石头布这类游戏里面，纳什平衡点的定义是如果双方都在用一个比较好的战略，任何一方做出调整结果都会更糟糕，也就是存在一个平衡点，使得两个人都不能再进步。

我们用一个简单的游戏解释。

如果我们玩一手剪刀石头布，可能靠运气；玩二十万手，就要看战略是什么。如果我们想解这个问题，也是很简单，下面这个就是所谓的完美战略

· 33%剪刀33%石头33%布

· 无论对手用什么战略，都不可能战胜我们

· 但我们也赢不了…

想要接近一个真正的完美战略是非常难的，大部分人有些偏好，更接近的可能是这样一个情况，对手比较笨不知道能出剪刀

· 假设对手#1从来不出剪刀，50%布，50%石头

· 我们的老战略有问题么？（各33%）

老战略可能还是不输的，但也不是最佳战略(GTO)。纳什平衡的意思是双方都不能改进，如果知道对手从来不出剪刀，我们的战略是能改进的。针对上面的对手#1，我们的战略可以改成50%剪刀，50%布。

为什么不用100%布的战略？因为对方可能也调整成100%布。使用50%剪刀，50%布的战略至少可以比打平做的更好。

从博弈论来说，我们找到了对手的弱点，但没有暴露自己的弱点。也就是说，我们找到了一个新的平衡点。

这就是Libratus在做的事情。

相比于石头剪刀布，一对一的德州扑克，是一个复杂度非常高的博弈。如何找到德州扑克的GTO和纳什平衡点？这是此类AI算法的核心。

CounterFactual Regret Minimization(CFR，反事实遗憾最小化)，这是一个类似强化学习的算法，更高效。让AI之间对战德扑，采用随机的策略，然后每局过后看看在什么地方后悔了，然后尝试不同的战略，再在决策点上复盘。

这个算法与人类学习德州类似累积经验、评判自己的选择，但需要注意的是，这里正确的“后悔点”非常重要。德州扑克有很强的随机性，所以很容易陷入错误的学习方式。

算法很简单，问题是无限德州的空间太大了，复杂度是10的160次方。有几种解决方案合并简化+CFR(Claudico)，CFR+“直觉”(DeepStack)，CFR+End Game Solver+RL(Libratus)。

一下

· CFR类似于强化学习。权重调整基于概率。

· AI的战略和学习方式和职业牌手相似，更准确。