学界丨CMU风头被抢，新型DeepStack算法抢先攻克德州扑克图灵测试

在国外的学术圈里，有一份论文火了。论文里进行的研究表明，人类历史上第一次，AI在德州扑克游戏上赢得了人类职业玩家。而这份论文的突破性意义在于：AI在非完整信息的博弈游戏中，赢得人类职业对手。

这篇论文的名字是《DeepStack：无限下注扑克里的专家级人工智能》（DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker），1月6号提交到了ArXiv上。

论文作者是来自加拿大Alberta大学、捷克Charles大学、布拉格捷克理工大学的研究人员。而论文题目里的DeepStack，是一种新型的算法名称，论文里说明到“DeepStack 是一种通用算法，可用于一大类非完整信息的序列博弈”。在一项涉及到数十位参与者和4.4万手扑克的研究中，DeepStack 成为了世界上第一个在“一对一无限注德州扑克”上击败了职业扑克玩家的计算机程序。

什么是“一对一无限注德州扑克”（HUNL）

德州扑克的英文名称是“Texas Hold'em”，而“一对一无限注德州扑克”（Heads-up no-limit，简称 HUNL）的意思，就是有2个玩家且不限下注筹码。这篇论文里的自然就是计算机和职业玩家挨个对局。

虽然是扑克，但跟斗地主还是很不一样的，它是“赌场”十分受欢迎的项目。这里祭出视频，帮大家理解一下德州扑克的规则和玩法。

从上面的视频中，我们大致能了解一场德州扑克会有两类信息：玩家每人手里分到2张底牌的“私有信息”和桌子上公共牌的“公开信息”。玩家选择5张公共牌里的3张，与手里的2张底牌组合，最后以期得到最好的5张牌的组合。按照“Card Ranking”决定最后的胜者。

在中国玩德州扑克的名人，一个是汪峰老师，另一个就是李开复老师。在知乎上“扑克有哪些技巧、经验或者原则？”的提问下，排名第一的，就是李开复老师的答案，他尤其提到玩好诈唬（Bluffing，高手惯用技巧）的关键在于学好统计。

德州扑克是新一代的图灵测试？

德州扑克已经成为十分流行的人工智能研究测试地，每一个扑克玩家手里握着的底牌“私有信息”，是其它玩家看不到的，所以被称为是“非完整信息”（Imperfect information）的博弈。这跟围棋有很大不同，围棋是完整信息公开的博弈，玩家们可以看到棋盘上的每个旗子，考虑所有落子的可能性。所以德州扑克对于人工智能来说，更加具有挑战性。

《DeepStack》这篇论文的通信作者 Michael Bowling曾经在2015年初接受《New Scientist》采访时说道：“德州扑克最有趣的地方，就是你无法获得完整的信息”。

而卡耐基梅隆大学（CMU）Tuomas Sandholm教授也说道：“扑克已经成为在非完整信息情况下，衡量（计算机）智能水平的标准......而它可以看做是一种超越图灵测试的存在。”

有趣的是，这两位教授都在领导自己的团队攻克这个新型图灵测试，一位在加拿大Alberta大学，一位在美国CMU大学。

几天前，CMU已经发出预告：由Tuomas Sandholm教授领导研发出的Libratus人工智能系统，将于当地时间1月11日，在宾夕法尼亚州匹兹堡的 Rivers 赌场，与四个顶级职业玩家玩12万手的HUNL，并角逐20万美元的奖金。早在2015年，Libratus的前身Claudico与人类玩家首次对战，在8万手的对决中完败，这次算是CMU的卷土重来。

但是我们已经知道了结果，Alberta赶在CMU之前，把就论文发出来了。学术圈人士纷纷表达赞美，称DeepStack具有里程碑意义（当然这份论文还未通过同行审议阶段），然而跟CMU Libratus提前好几天的预热盛况相比，DeepStack并没有得到等量的媒体待遇，也引发一些人的不满。

CMU走的是当年AlphaGo的路线，在华丽的赌场搞一场秀，与人类顶尖玩家对战，还有20万美金的噱头。所以这份DeepStack论文虽然比CMU更早取得突破，但阵仗不如后者大，媒体对其忽视了，也在情理。

总之一句话，Alberta抢了先，CMU抢了热闹（学术界的竞争也是异常激烈的）。

此份DeepStack论文的成果

DeepStack总共与33位人类选手进行了4.4万手的较量，分别在2016年11月7日和12月12日之间于线上举行对局。最终获胜的前三位选手，分别有5000、2500和1250加元的奖励。以下是对局结果。结果显示，DeepStack的平均赢率为492 mbb/g（一般人类玩家到50 mbb/g就被认为拥有较大优势，750mbb/g 就是对手每局都弃牌的赢率）。

前面我们提到，一场扑克的信息可以分为“私有”和“公开”，放在桌子中间的5张公开牌形成一种动态的“公开状态”。游戏中的公开状态的可能序列构成一个公开树（Public tree），其中每一个公开状态都有一个相关的公开子树（Public subtree）。

上图是HUNL 中公开树的一部分。红色和蓝色线条表示玩家动作，绿色线条表示公开的公共牌。圆形节点表示游戏结束。

这张图是DeepStack整体架构，分为（a）（b）（c）三个部分。在（a）中，DeepStack在每一个公开状态里， 都要重新计算它需要的动作，其中子树值（Subtree value）会通过一个训练好的深度神经网络 Neural net（b）来计算，而训练Neural net的样本就是（c）。

总的来说，DeepStack结合了递归推理（Recursive reasoning）来处理信息不对称性，还结合了分解（Decomposition）集中计算到相关决策上，并形成了一种关于任意牌的直觉（Intuition），这种直觉可以使用深度学习进行自我玩牌而自动学习到。

而对于DeepStack和1月11日的CMU的Libratus赌场大战，AI 科技评论将跟踪深入报道。