德州扑克战胜人类的AI用啥算法？Facebook田渊栋为你解析

照雷锋网所说：此文作者是田渊栋，他拥有卡耐基梅隆大学机器人系博士学位，还拥有上海交通大学硕士学位以及学士学位，他曾是前谷歌无人车项目组成员，如今担任Facebook人工智能组研究员，其主要负责的是Facebook的智能围棋项目Dark Forest。这篇文章是转载自知乎专栏，雷锋网已获得了授权。

最近听闻，我的那一所名为卡耐基梅隆大学的母校，其德州扑克的AI Libratus，在一场与职业玩家的比赛当中，以相当大的优势取得了胜利，这让我感到兴奋不已。在同一时期，另外还有一篇源自加拿大阿尔伯塔大学（Univ of Alberta）的文章，它对DeepStack进行了介绍。同样也是那种情况，DeepStack在一场达3000局的比赛里，击败了数位职业玩家。如此这般，在非对称信息游戏这个领域，人类又一次输给了AI。

当然存在AlphaGo的先例，这个对于广大吃瓜群众而言，冲击或许没那么大。不过我个人认为，非对称信息博弈的实用价值更大些。原因在于，非对称信息博弈的应用范围极为广泛，涵盖我们每日碰到的所有决策，从国家战略层面，到日常琐事方面，全部都能够以相同的方法进行建模。

非对称信息博弈难在哪里？

比如说，玩石头剪刀布，在看不到别人出招的情况下轮到自己出招，这时如果别人一直采用石头剪刀布各占三分之一的混合策略，那么自己就会发觉，好像无论怎么出招收益都是零，于是每次都出石头，然而这样一来，对手就能够利用这个策略的弱点来提高自身的收益。所以，一个好的算法就有这样的要求，即基于别人已有策略得出的新策略要尽可能做到少被别人利用（low exploitability） 。

此次的游戏是Head-up unlimited Texas Hold’em，直译成中文是两人无限注德州扑克，其中的两人指的是一对一的零和游戏情况，并非多人游戏德信竞技，所谓无限注，即加筹码时能够随意添加，像著名的把全部筹码都押上的All in这种情况，而限注也就是limited，是说加筹码时只能添加一个固定的数字，通常前两轮和大盲注相同，后两轮是大盲注的两倍 。

两人有限注德州扑克（HULHE），因玩家选择较少，能够进行暴力计算，于2015年被阿尔伯塔大学解决，所获策略极近似纳什均衡点（见此文章，发表于《科学》，人工智能名为Cepheus，采用的方法是CFR+）。

这次CMU用到的方法，和之前类似，是Counterfactual regret minimization (CFR) 的变种，而Alberta此次用到的同样是这种类似的方法，也是Counterfactual regret minimization (CFR) 的变种。这次存在主要贡献，在于：

CFR的思路特简洁，起始于随机策略，每次针对一个玩家的策略予以优化之举，目的在于提升其收益，而后进行反复的迭代操作，最终选取平均策略当作最终策略。每次进行优化时，采用的是悔恨值最小化，也就是Regret minimization的办法，所谓的悔恨值，指的是事后最优选择所产生的收益，减去当时进行的那一次选择所带来的收益，而悔恨值最小化，是将到当前为止的累计悔恨值拿来，查看哪一步的累计悔恨值高，往后就多走这一步，至于多走的概率，存在各种算法，比如说Regret Matching和Hedge 。

面对两人零和游戏，能够证实CFR会趋向于纳什均衡点，即类似“不管如何我就只有这一招，你根本没办法破解”这般的终极策略，故而计算机当下所运用的算法，其最终目标并非借助对方弱点来获取胜利，而是寻觅到某种神功，从而达成无人可与匹敌的境地；自然，为了至达此等境地，在训练进程里依旧是持续探寻对方弱点以使自身变得强大 。

CFR是一种带有理论界性质的通用算法，称其能够解决所有的非对称信息博弈问题，这样说着实不为过。然而呢，世界上自然而然并不存在免费的午餐，当运行CFR之时，每一回都需要对游戏全部可能展现的状态进行一次遍历，而随便哪一个稍微具备一定复杂度的游戏，都有着指数级别的状态，所以呢，在运行时间这方面，肯定是无法让人接受的。

这般便存在诸多折中办法，像是状态量化，即认定2至9皆为小牌，采用同一策略予以处理；还有剪枝，倘若对方不太可能行此步骤，那就无需再往下搜索；另外有随机采样，也就是采样一些路径用以替代全部的游戏分支；再者是函数拟合，比如运用值网络来取代深层搜索，等等 。

整体来讲，CFR跟几年之前的RL相像，二者皆是传统AI领域里理论界的陈旧方法，在现实问题当中均存在指数复杂度，如今都逐渐起始朝着深度学习方向转变，因而我坚信往后会拥有更为广阔的发展空间。