博弈AI崛起，人工智能算法进入“人类+机器”大时代

（上图为卡耐基梅隆大学计算机系教授、德扑AI之父 Tuomas Sandholm）

“人工智能时代，针对机器的算法是机器学习，针对人类的算法是博弈论。”这是清华大学交叉信息研究院青年千人助理教授、博士生导师、计算经济学研究室主任唐平中，在2017年7月20日钛媒体与杉数科技联合举办的“AI大师圆桌会之AI时代的博弈与行为分析”活动上提出的观点。

唐平中在加入清华之前，于美国卡耐基梅隆大学计算机系从事博士后研究工作，师从德扑AI之父Tuomas Sandholm，从事人工智能、电子商务和机制设计的研究工作。

Tuomas Sandholm是卡耐基梅隆大学计算机系教授，研究兴趣包括人工智能、机制设计、优化理论、博弈论、电子商务、多代理系统、自动谈判及合同等广泛领域，迄今已经发表450多篇论文，还是Optimized Markets和Strategic Machine两家公司的创始人。

Tuomas Sandholm 在“AI时代的博弈与行为分析”圆桌会上，分享了在他带领下完成的人工智能系统Libratus（中文名：冷扑大师）及其在今年以来击败全球德州扑克世界高手的经历。

Tuomas表示，Libratus系统结合了优化的博弈论和机器学习等算法，是迄今为止唯一击败人类德州扑克世界最顶级高手的人工智能系统，在战略推理和战略思维方面达到了超越人类的水平。

与AlphaGo围棋的完美信息场景不同，德州扑克是典型的非完美信息场景，已经挑战人工智能+博弈论数十年之久。Tuomas表示，Libratus算法无应用领域限制，可广泛应用到多种商业与经济场景中。

在此次圆桌会上，除了唐平中和Tuomas Sandholm，上海财经大学教授、奥数金牌、杉数科技科学家何斯迈与上海财经大学交叉科学研究院院长、杉数科技首席科学家葛冬冬以及不列颠哥伦比亚大学（UBC）Sauder商学院助理教授丁弋川等也进行了分享。

有人的地方就有博弈。从囚徒困境到智猪博弈再到美女的硬币，博弈论一再说明一个道理，就是人类的思维不同于机器，特别由于人类的社会化属性，但凡有两个人以上的地方就充满着博弈的思想。因为有人的地方就有竞争，有竞争就有博弈。

作为数据、计算机与经济学的交叉学科，博弈论已经成为经济学的标准分析工具之一，在金融学、证券学、生物学、经济学、国际关系、计算机科学、政治学、军事战略和其它很多领域都有广泛的应用。博弈分为合作博弈与非合作博弈、完全信息博弈与非完全信息博弈、静态博弈与动态博弈等多种类型。

唐平中表示，博弈论在西方已经有近90年的历史，而在中国则是于近5年得到了广泛的关注和应用。从2009年开始的互联网广告拍卖设计算法，使博弈论在国内经济界得到了重视，如今国内工业界对博弈AI的算法也有大量的需求。

究其原因是在研究人工智能的时候，发现仅处理针对机器的算法远不能满足实际商业的需求，在现代商业中往往是“人+机器”的复杂场景，而博弈论恰好是针对人类的智能算法。

丁弋川在解读Tuomas Sandholm对AI的观点时，强调博弈论与最优化决策的结合。正如Tuomas Sandholm所解释，博弈论本身只是一个描述性工具，并不做出具体的决策，而最优化决策则指出每一步的最优化结果，但同时并没有考虑对方的情况，AI就把二者结合起来做出二人博弈时的最优化决策平衡点。

这就是德州扑克在人工智能学术上不亚于甚至是超过AlphaGo的意义所在，它提供了一种新模型去分析在没有或缺乏信息的情况下，如何计算平衡点。

Tuomas Sandholm强调，扑克游戏本身就是非完美信息的场景，德州扑克更是非完美信息的典型场景。在德州扑克进行的过程中，缺乏甚至没有任何数据，在这种情况如何计算出每一步的最优平衡点，同时还要考虑进对手的每一步情况。德州扑克有10的161次方个决策点，是非完美信息博弈算法的标准测试场景，国际上一直有学术团队在挑战这一场景。

葛冬冬介绍说，在杉数科技从事项目算法开发与实施的过程，发现很多现实中的商业问题不仅仅需要考虑最优化，很多时候还需要考虑到人类的行为，这些人类行为将给问题的解决带来额外的难度。

比如在考虑电商定价的时候，不仅要根据以前的价格历史来计算未来的最优价格，还要考虑到与顾客和竞争对手的反应。当价格低的时候，电商顾客会根据情况囤积自己的小库存，便宜就多买、不便宜就不买，同时竞争对手也会实时比价跟随定价。因此，在新零售等场景中，不再仅仅是数据驱动，还要考虑复杂情况下的顾客和竞争对手博弈等，这就应用了很多AI技巧。

博弈AI的崛起，正是复杂商业需求驱动的结果。

2017年1月，在宾夕法尼亚州匹兹堡的赌场里，Libratus冷扑大师挑战了世界排名前15中的4位“一对一无限注”德州扑克人类高手，在设计了非常保守的对人类极为友好的对战环境后，Libratus在20天赛程内一共进行了12万手牌比赛，最后Libratus以绝对优势战胜4位人类选手。

2017年4月，Libratus应邀以“冷扑大师”之名到中国与来自中国的一组扑克、AI和计算机高手组成的“龙之队”对决，冷扑大师最终以792,327总记分牌的战绩获胜，获得了此次表演赛的200万奖励。Libratus冷扑大师完胜中外的德州扑克高手，说明其代表的博弈AI算法已经到了相当成熟的高度。

Tuomas Sandholm在“AI时代的博弈与行为分析”分享会上介绍了Libratus的历史，这是一项长达12年的研究。

从最早的2005年Rhode Island Hold’em扑克游戏起步，该游戏是一种小型的扑克游戏，但也有高达31亿个决策节点，具备大型德州扑克的许多特征。Tuomas Sandholm与Andrew Gilpin于2005年在AAAI会议上发表了论文，介绍了该项研究的初步成果。

从2005年起步，Tuomas Sandholm和团队在2014年5月推出了Tartanian7人工智能系统并赢得了2014年ACAP计算机扑克大赛，2015年4月推出了下一代Claudico人工智能系统，但Claudico在2015年败给了人类选手。

2015年12月推出的下一代Baby Tartanian8赢得了2016年ACAP大赛，接着又推出了Tartanian8。最后，就是2017年1月的Libratus赢得了人机对战的胜利。

Libratus包括了三个模块，分别是赛前的游戏规则抽取和纳什均衡近似，赛中用到的残局解算（Endgame Solving）以及持续自我强化。

博弈论中的纳什均衡主要指博弈双方的理性参与者都不会有单独改变策略的冲动，而该系统中采用纳什均衡，使得不论对手用什么样的策略，都不能取胜。

在前期寻求纳什均衡的过程中，采用了CFR算法（Counterfactual Regret Minimization，反事实遗憾最小化）的强化学习，这是一个源自心理学的算法，即“如果当初做了另外一种选择就好了”的反向思考方式，这种强调试错的方法可以让机器自己和自己玩大量游戏。

通过CFR算法，Tuomas Sandholm向Libratus描述了游戏规则后，经过几个月的随机训练100万亿手牌后，达到了足以挑战最优秀人类选手的水平，还开发出了一些人类没有的玩法。

而在残局解算中，Libratus的改进算法包括考虑进了对方所犯下的错误、尽早开始残局解算、对手每出一招即实时展开残局解算（Nested Endgame Solving）等等。

而在持续自我强化模块，Libratus在比赛的每晚不是分析对手的问题，而是总结自己当天的主要败笔，这就好像人类每天总结自己的弱点再有针对性的弥补，这样自己的弱点越来越少，给对手的可趁之机也越来越少，这种主动防守型的打法，最坏的结果就是双方打成平手，所谓纳什均衡追求的就是一种平衡。

当然，12年的研究成果并不是聊聊几句就可以完全解释清楚。除了主要算法的改进外，Libratus在计算方面也有所改进以适应庞大的分布式计算需求。根据匹兹堡超算中心的数字，Libratus约使用了150台服务器。随着硬件能力的提升，Libratus有望使用越来越少的计算资源，甚至将来有可能运行在手机里。

Libratus是博弈AI的最新成果和高度，当然这并不意味着Libratus就已经完美。Libratus针对的是一对一比赛的场景，主要是纳什均衡即针对一对一对场景，在多人博弈场景下纳什均衡就不太适用。此外，Libratus针对的是每场重置筹码的比赛，而人类不重置筹码的比赛也未必适用。

尽管Libratus还有局限性，但Libratus至少打开非完美信息世界的大门。

目前Libratus已经取得的成就，可以通过机器自动化的方式在很多商业场景中替人类做出战略决策和最优化策略选择，这就是人工智能梦寐以求的决策自动化。

Tuomas Sandholm表示，如果机器能够替代人类做出战略决策，那么结合深度学习的机器学习，就可以形成自动化的学习-决策-再学习-再决策的闭环，这才是完整的人工智能算法。

何斯迈介绍了杉数科技在新零售行业，特别是收益和库存管理中应用博弈论和人工智能的例子。

很多国内企业开始进入数字化和数据化时代，基于数据积累要开始量化管理，需要用到博弈AI算法。比如根据友商价格、顾客价格敏感度、顾客心理价位、季节性、产品替代及互补性、促销及拉升效应等多种量价关系要素来进行动态博弈，解决方案包括使用网络爬虫及机器学习来捕捉友商实际价格及分析友商价格策略，分析产品市场定位（主导者/跟随者/竞争者），再寻找远期利益与近期利益的动态平衡点。

何斯迈表示，现在普遍商业企业的规模很大，在一个调度管理问题的实例中，可能涉及决策变量就有上百万个，而且对实时性要求非常高，必须在秒级别完成上百万个决策变量的问题求解。何斯迈一直在杉数科技进行这方面的工作。

葛冬冬也强调，在杉数科技等的推动下，特定类型问题中百万级变量的整数规划问题求解，可以在1秒钟完成。实际上，对整数规划来说，哪怕只有几百个变量都求解都非常困难，极端情况下最好的商业软件也需要很长时间才能计算出来。

杉数这方面的进展，是与斯坦福大学的叶荫宇教授、乔治亚理工的蓝光辉教授、上海财经大学的“Leaves”优化实验室长期艰苦合作，才能实现特定场景下秒级百万规模变量的最优化求解。

有了Libratus这样成熟的博弈AI算法，其算法并没有行业领域的应用限制，再加上超大规模最优化问题秒级求解的工程化能力，就能在战略定价、产品组合优化、金融、商业谈判、业务战略、下一代安全、拍卖、医疗健康等广泛的非完美信息场景中实现机器决策+机器学习的完整人工智能体系，这将对整个社会、经济和商业带来深远的影响。