近日，DeepMind的AI智能体DeepNash在Stratego中成功击败职业人类选手，顺利进入前3。12月1日，该论文正式发表在Science上。论文地址：http://www.science.org/doi/10.1126/science.add4679用这个AI向JohnNash致敬。在这个时代，玩游戏的AI已经发展到一个全新的阶段。以前很多科学家会用国际象棋和围棋来训练AI，但这次DeepMind使用的Stratego是一款经典的棋盘游戏，比国际象棋和围棋复杂，比扑克更巧妙。而这个名为DeepNash的AI代理通过与自己对战从头开始学习Stratego。现在，DeepNash在全球最大的在线Stratego平台Gravon中跻身人类专家前三名。DeepNash采用了一种基于博弈论和无模型深度强化学习的全新玩法。可见，取名也是为了向美国著名数学家约翰·纳什（JohnNash）致敬。他提出的纳什均衡，又称非合作博弈均衡，是博弈论中非常重要的一个组成部分。Stratego的奥妙在哪里？棋盘游戏在历史上一直是衡量人工智能进步的标准，因为它们使我们能够研究人类和机器如何在受控环境中制定和执行策略。而这个Stratego的奥妙在哪里呢？与国际象棋和围棋不同，Stratego是一种不完全信息游戏：玩家无法直接观察对手棋子的身份。正因为如此复杂，基于AI的Stratego系统无论怎么努力，都处于业余水平，不可能达到“专家”的水平。以往，各种AI之所以能在比赛中获胜，打爆人类，是因为一种叫做“游戏树搜索”的AI技术。虽然“游戏树搜索”可以秒杀各种信息充足的游戏，但对于Stratego这样的游戏来说有些无奈，因为它的可扩展性不够。至此，DeepNash已经彻底打爆了博弈树搜索。事实上，DeepNash掌握Stratego的价值，已经远远超过了游戏本身。现实世界往往是复杂的，信息是有限的。一个真正先进的人工智能系统面临着像Stratego这样的环境。DeepNash已经成功地向我们展示了人工智能如何在不确定的情况下成功地平衡结果和解决复杂问题。如何玩StrategoStratego是一款回合制夺旗游戏。在游戏中，玩家需要虚张声势、诡计多端、搜集情报、熟练操作。这是一个零和博弈，任何一方的收益都代表着对手等量的损失。听起来很像我们的军棋。Stratego与军棋的区别在于它的棋子数量更多，军衔更多，棋盘设计更简单，没有铁路、营地和裁判。双方布阵时，所有的棋子都要竖起来，让对方看不到。阵法完成后，红方先走，然后依次走一子。棋子中，军旗和地雷不能移动，侦察兵可以横竖移动任意格子，不能越过棋子，其余棋子只能横竖移动一格。当双方的棋子在同一个格子时，一起揭开判断大小，赢的棋子放回原位，面朝后，输的棋子移走。Stratego的取胜方式与中国军棋相似。夺取对方军旗或消灭所有可移动棋子即为胜利。为什么Stratego对AI如此具有挑战性？部分原因是它是不完全信息博弈。Stratego中的两名玩家互相隐藏，同时在起始阵型中安排40个棋子。由于玩家无法获得相同的知识，因此他们在做出任何决定时都需要平衡所有可能的结果。Stratego棋子的类型和排名左：国际象棋排名。游戏中，除了10（元帅）被间谍攻击外，排名较高的棋子获胜；炸弹总是赢，唯一的例外是被矿工捕获。中间：可能的起始阵型。旗帜要安全地塞在后面，两侧有炸弹保护。两个浅蓝色区域是永远不能进入的“湖泊”。右图：正在进行的游戏，如您所见，蓝队的间谍抓获红队的元帅。这场比赛难倒了AlphaZero。在Stratego中，信息是隐藏的。只有遇到其他玩家时，对方棋子的身份才会暴露。国际象棋和围棋的区别在于它们是“完全信息游戏”，因为双方棋手都确切地知道每个棋子的位置和身份。DeepMind的AlphaZero在完美信息博弈中一直表现出色，但在Stratego中，却被难住了。在国际象棋中，AlphaZero在4小时后超越了Stockfish；在国际象棋中，AlphaZero在2小时后超越了Elmo；而在围棋方面，AlphaZero超越了AlphaGoStratego，后者在30小时后击败了李世石，这更类似于德州扑克。类人能力——人类需要在信息不足和虚张声势的情况下做出决定。美国作家杰克·伦敦曾指出：“在生活中，我们并不总是拿着好牌，但有时我们可以用一手烂牌打出好牌。”其实很多AI也很会打扑克，但是在面对Stratego的时候，我惊呆了——这游戏的过程太长了！玩家需要走数百步才能获胜。因此，游戏中的推理必须针对大量的连续动作。在这个过程中，很难看清每个动作对最终结果的影响。Chess、Poker、Go和Strateg之间的规模差异而且，与Chess、Go和Poker相比，可能的游戏状态（“游戏树复杂性”）的数量超出了图表，而且解决起来异常困难。这就是Stratego如此令人兴奋的原因——它代表了AI社区长达数十年的挑战。Stratego：高地AI必将征服多年来，如何让人工智能在Stratego游戏中脱颖而出成为AI研究者关注的焦点。在这个游戏中击败人类玩家主要有两个困难。首先，游戏的博弈树有10535个状态，即一场游戏有10535种可能的布局。相比之下，Go只有10种可能的布局。其次，在Stratego中，人工智能需要推理出对手的10的66次方以上的部署策略，而扑克只有一千种可能的牌对。因此，破解Stratego复杂的布局并非易事。如何打败人类Stratego玩家，对AI研究人员来说是前所未有的挑战。如何打爆其他AI？R-NaD的核心武器DeepNash之所以能爆出其他AI，是因为它采用了一种基于博弈论与无模型深度强化学习相结合的新颖方法。“无模型”是指DeepNash不尝试在游戏中显式模拟对手的状态。尤其是在对局初期，当DeepNash对对方的棋子知之甚少时，这种建模，即使可能，也极有可能是无效的。而且，由于Stratego的博弈树过于复杂，DeepNash无法使用其他AI玩博弈时使用的蒙特卡洛树搜索。后者是人工智能在不太复杂的棋盘游戏和扑克中取得里程碑式成就的关键。可见，均衡策略虽然在双方轮流行动的完全信息博弈中可以发挥作用，但在不完全信息博弈中显得力不从心。DeepNash采用了一种新的博弈论算法思想——RegularizedNashDynamic(R-NaD)。这种无模型的强化学习算法是DeepNash的核心。它引导DeepNash使其学习行为朝着纳什均衡的方向发展。DeepNash将R-NaD与深度神经网络架构相结合，并收敛到纳什均衡。包括三个步骤：奖励变换（rewardtransformation）、动态规划（dynamics）和更新迭代（udate）。研究团队通过反复应用这三个步骤，直到产生一系列不动点，证明算法收敛于原博弈的纳什均衡。对抗最强的Stratego机器人（包括计算机策略世界锦标赛的几位获胜者），DeepNash的胜率高达97%，经常达到100%的胜率。在Gravon游戏平台上，与人类顶级玩家对战时，DeepNash取得了84%的胜率，蝉联历史前三名次。当然，在博弈中，纳什均衡是无法通过博弈论无限制地达到的，因为这样并不能保证玩家的胜率。均衡策略只适用于完全信息博弈。在不完全信息博弈中，需要其他策略才能出奇制胜。在最初的阵型中，DeepNash采用了一些非凡的玩法。为了变得难以利用（hardtoexploit），DeepNash制定了一种不可预测的策略（unpredictablestrategy）。这意味着初始部署必须足够多样化，以防止对手在随后的一系列比赛中发现自己的模式。在游戏阶段，DeepNash也会尝试在看似相同的动作之间进行随机化（randomise），以防止自己变得可用。在这个过程中，隐藏信息非常重要。隐藏信息以迷惑对手在现实中，人们还使用其他手段取胜，比如虚张声势。正如“博弈论之父”冯·诺依曼所描述的那样：“现实生活中充满了‘虚张声势’、‘欺骗小把戏’和‘猜测别人会怎么想我要做什么’。”陶哲轩《红眼蓝眼自杀问题》：我知道，我知道他知道，我知道他知道他知道……在这方面，DeepNash也不甘落后。研究团队演示了DeepNash的两种诈唬技巧：正诈唬和负诈唬。所谓主动唬人，就是假装自己的棋子水平高，以震慑对手。简单来说，就是“唬人”。在这个例子中，DeepNash给我们上了很好的一课：在与人类玩家（红方）对战时，DeepNash（蓝方）在开局时牺牲了7（少校）和8（上校）等棋子。找出对手的10（元帅）、9（将军）、一个8和两个7。至此，DeepNash（蓝方）已经找到了对方很多最厉害的棋子，同时隐藏了自己的关键棋子。乍一看，DeepNash似乎处于明显的劣势：它的7和8都出局了，但人类对手保留了所有排名7及以上的棋子。然而，DeepNash笑到了最后——依靠它发现的对方高层团队的可靠情况，估计自己的胜算有70%。最后，它确实赢了。虚张声势的“艺术”在扑克中，优秀的玩家会玩心理战，在对手很弱的时候恐吓他们。DeepNash也学会了这种诈唬战术——负诈唬。也就是我们常说的“扮猪吃老虎”：把自己的高级棋子伪装成低级棋子，等对方上当了再一举拿下。在下面的例子中，DeepNash用2（作为侦察兵很弱）追击对方暴露的8。据此，人类对手判断追击者很可能是10，因此试图将其引诱到间谍的伏击圈中.最终DeepNash用小棋子2成功击杀对方关键棋子间谍，人类玩家（红色方块）确信追自己8的未知棋子一定是DeepNash的10（因为此时DeepNash已经输了hisonly9.下面是DeepNash与（匿名）人类专家对战的这四个完整游戏视频，Game1,Game2,Game3,Game4，点击进入，更多惊喜等你来。（视频地址已列在参考资料中）DeepNash的游戏水平让我感到惊讶。我从来没有听说过话虽如此，没有一个人工Stratego玩家接近与人类玩家打赢所需的水平。但是在我自己与DeepNash对战之后，我并不感到惊讶它在Gravon上排名前三。我的预测：如果它参加人类世界锦标赛，它会做得很好。——VincentdeBoer，论文合著者，前Stratego世界冠军未来不可估量可以看出，DeepMind的这种新颖的R-NaD方法可以直接应用到其他具有完美或完美的双人零和博弈中不完善的信息。R-NaD有潜力超越双人游戏设置来解决大规模的现实世界问题。此外，R-NaD还有望在不同目标的其他领域解锁人工智能的新应用。例如，在交通管理的规模优化中，人们不知道他人的意图或环境信息。此时，R-NaD有望优化司机的出行时间。人类世界本来就是不可预测的。现在，人们创造了一个在面对不确定性时具有鲁棒性的通用人工智能系统，这让我们对人类的未来充满了想象。参考资料：http://www.science.org/doi/10.1126/science.add4679https://www.nature.com/articles/d41586-022-04246-7https://www.deepmind.com/blog/mastering-战略不完美信息的经典游戏https://youtu.be/HaUdWoSMjSYhttps://youtu.be/L-9ZXmyNKgshttps://youtu.be/EOalLpAfDSshttps://youtu.be/MhNoYl_g8mo
