社区首页 >专栏 >DeepMind VS Meta：实现纳什均衡理性最优解，还是多人非零和博弈算法更强大？

DeepMind VS Meta：实现纳什均衡理性最优解，还是多人非零和博弈算法更强大？

大数据文摘

发布于 2023-04-10 08:51:35

4680

文章被收录于专栏：大数据文摘大数据文摘

大数据文摘转载自AI科技大本营

编译 & 整理：杨阳

记得豆瓣高分电影《美丽心灵》中的约翰·纳什吗？

作为获得诺贝尔经济学奖的数学家，纳什在博弈论、微分几何学，以及偏微分方程等各个领域都作出卓越贡献。为表彰他在非合作博弈理论中对均衡（纳什均衡）的开创性分析，1994年瑞典中央银行授予纳什诺贝尔经济学奖。

纳什均衡在社科中的应用可谓成功，而在科技领域中，也经常引用博弈论的逻辑来进行技术实现，比如，通过密码学和博弈论的结合实现大数据安全。当下，这一逻辑也开始应用在AI的算法上。

DeepNash——DeepMind制造的最新款人工智能，它名字中的“Nash”即为纪念纳什而命名。在AlphaGo之后，谷歌已降低在棋牌领域的关注，之所以推出DeepNash，在于借鉴纳什均衡的逻辑设定基础上，这款AI模型得以在西洋陆军棋Stratego（策略）中击败专业玩家，这比在国际象棋、围棋和扑克的比赛中击败人类更加困难。

DeepNash是怎么做到的呢？

超越围棋的走法量，诉求“无模型”和强化学习

相较其他棋牌游戏，Stratego在规则上就包含了更多不确定性，包括玩家之间的信息非对称。比如，象棋和围棋的牌面和走位都是公开的，但Stratego的牌面却是看不到的，这点和玩扑克一样。另一方面，相较于围棋只有一个初始定位，德州扑克有106个，而Stratego有惊人的超过1066个可以选择的起始点。要知道，1066这个量级已经超过了宇宙中所有星辰的总量。

在博弈树的算法统计量上，Stratego可能的走法达到不可思议的10535种，围棋的这一数量为10360。

信息非对称、路径解极多，极度复杂性意味着通过通用的“蒙特卡洛树”模型玩转Stratego并不可行。DeepNash的研究者之一，DeepMind研究员Perolat表示：“那些适用于扑克的算法在Stratego中是完全行不通的，可能的结果量级太过庞大，因而非常复杂，信息的处理需要更为完备的方法。”

最终，团队找到的方法是“无模型”强化算法，意味着在任何模型都无法实现精确模拟的情况下，让DeepNash就像一个婴儿或者一张白纸一样进行从0开始的积累。但这使得预测变得困难，甚至完全不可能。

为了解决这个问题，团队使用了深度强化学习为DeepNash提供动力源，目的是找到最优的纳什均衡。

运用纳什均衡，在信息不对称中诉诸最优解

强化学习算法如同“钢铁侠”，可以处理大规模数据量的问题，但牌面的信息不对称又该如何解决？该DeepNash中“Nash”发挥作用了。

纳什均衡，也是非合作博弈均衡分析，社会学和经济学专业学生对这个名词非常熟悉。其中最著名的实验就是后来经常应用在犯罪心理中的囚徒困境。这一理论给出的现实命题是：对于处于非合作博弈中的双方，无论对方如何选择，当事一方只有一种确定的策略对自己来说是最优解，因而两方都会选择自己的最优，最后达成彼此最优下的博弈均衡。

比如，两个共同犯罪的嫌疑人分别接受审讯，如果双方都不坦白，两人各自获刑一年；其中只有一方坦白，坦白的无罪释放，不坦白的获刑十年；而如果双方都坦白，各获刑五年。在这个假想实验中，都不坦白才是整体最优。然而，对于两位囚徒来说，肯定都希望无罪释放，而无论对方是否坦白，自己坦白都是理性最优解，所以最终的结果就是各获刑五年。

如果将纳什均衡的逻辑放到DeepNash的算法设定中，游戏中互相看不到牌面的双方就像囚徒困境中无法串通的两个囚徒，彼此是非合作博弈。在信息不确定的情况下，只有走无论对方出什么牌“我”都是最优选的牌，才能确保在多轮博弈中获胜。

DeepNash获得同类竞技97%胜率

纳什均衡和加上强化学习，最终达成均衡下的最优解：通过“每位玩家获得任何收益都会导致对手损失”的逻辑，凭借强化学习在游戏的每一步中计算下一步的最佳算法。就这样，DeepNash开启了自我对抗训练。

训练的奖惩机制是：当DeepNash—A获胜时，该网络参数将会增强；同时，对手方DeepNash—B的参数将会被削弱。通过55亿次的对弈，DeepNash取得了很好的成绩，失误率越来越小，无限接近纳什均衡最优。

在算法测试中，DeepNash以97%的胜率压制了其他机器选手。而在Gravon游戏平台上，通过和人类专业棋手进行两周多的竞技，DeepNash最终在有20年历史的积分排名榜中升至第三位。

除了学习能力惊人，DeepNash更让人惊讶的地方在于，它在开局不会固定自己的起始位置，而是不断优化起始点。这样做究竟是随机在10535种可能性中寻找最优解，还是“有意识”地避免对手对自己出牌套路的破解而故意为之，目前不得而知。如果是后者，就让人不寒而栗了。不过，DeepNash确实会用一些看上去“诱骗”的方式来“引诱”对手落入陷阱，通过一些看似无意义（棋子重复跳动），或者牺牲高级棋子（让对方放松警惕），从而进行伏击。

加入非理性测算后的多方博弈

DeepNash确实相当厉害，但如果你仔细观察也不难发现，纳什均衡的状态是发生在两方之间的，而现实世界往往并非两者的零和博弈。当博弈均衡需要发生在多方，又会呈现怎样的态势呢？

对此，Meta AI研究员们的发明或许更具挑战性：创建了能够玩多方博弈游戏的AI模型——Cicero。在一款名为Diplomacy（外交风云）的游戏中，多个玩家每人代表一个国家，最多可以有7个玩家一起玩。游戏规则是进行军队和战舰的战略部署，从而获得对供应中心的控制权。