DeepNash 通过结合博弈论和无模型深度 RL 从头开始学习玩 Stratego
游戏人工智能 (AI) 系统已发展到一个新的领域。Stratego 是一款比国际象棋和围棋更复杂、比扑克更狡猾的经典棋盘游戏，现已被掌握。我们在《科学》杂志上发表了DeepNash，这是一种人工智能代理，它通过与自己对战从头开始学习游戏到人类专家水平。
DeepNash 使用一种基于博弈论和无模型深度强化学习的新颖方法。它的打法风格收敛于纳什均衡，这意味着它的打法很难被对手利用。事实上，DeepNash 的难度如此之大，以至于在全球最大的在线 Stratego 平台 Gravon 上，DeepNash 已经跻身人类专家排行榜前三名。
棋盘游戏历来是衡量人工智能领域进步的标准，它使我们能够研究人类和机器如何在受控环境中制定和执行策略。与国际象棋和围棋不同，战略棋是一种信息不完全的游戏：玩家无法直接观察对手棋子的身份。
这种复杂性意味着其他基于人工智能的 Stratego 系统很难超越业余水平。这也意味着一种非常成功的人工智能技术，称为“博弈树搜索”，以前用于掌握许多完美信息的游戏，但对于 Stratego 来说，其扩展性不够。因此，DeepNash 远远超出了博弈树搜索的范围。
掌握 Stratego 的价值不仅仅局限于游戏。为了实现解决智能问题以推动科学进步和造福人类的使命，我们需要构建先进的人工智能系统，该系统可以在复杂的现实情况下运行，而其他代理和人员的信息有限。我们的论文展示了 DeepNash 如何应用于不确定的情况并成功平衡结果以帮助解决复杂的问题。
了解策略
Stratego 是一款回合制夺旗游戏。这是一场虚张声势和战术、信息收集和微妙策略的游戏。这是一场零和游戏，因此一个玩家的任何收益都意味着对手的相同程度的损失。
Stratego 对人工智能来说具有挑战性，部分原因是它是一种不完美信息的游戏。两名玩家一开始都会将自己的 40 个棋子排列成他们喜欢的任何起始阵型，在游戏开始时最初是相互隐藏的。由于两个参与者无法获得相同的知识，因此他们在做出决策时需要平衡所有可能的结果 - 为研究战略互动提供具有挑战性的基准。棋子的类型及其排名如下所示。
左：作品排名。在战斗中，等级较高的棋子获胜，但 10（元帅）在被间谍攻击时会失败，而炸弹总是获胜，除非被矿工捕获。
中：可能的起始阵型。请注意旗帜是如何安全地藏在后面的，两侧是防护炸弹。这两个淡蓝色区域是“湖泊”，永远不要进入。
右：正在进行的游戏，显示 Blue 的间谍捕获 Red 的 10。
在 Stratego 中，信息来之不易。对手的棋子的身份通常只有当它在战场上遇到其他玩家时才会被揭示。这与国际象棋或围棋等完美信息游戏形成鲜明对比，在这些游戏中，棋手双方都知道每颗棋子的位置和身份。
在完美信息游戏中表现出色的机器学习方法（例如 DeepMind 的AlphaZero）并不容易转移到 Stratego。需要在不完全信息的情况下做出决策，并且可能会虚张声势，这使得 Stratego 更类似于德州扑克，并且需要像人类一样的能力，美国作家杰克·伦敦曾指出：“生活并不总是拿着牌的问题好牌，但有时也能把烂牌打好。”
然而，在德州扑克等游戏中非常有效的人工智能技术并没有转移到 Stratego 中，因为游戏的长度非常长——通常需要数百步才能获胜。Stratego 中的推理必须通过大量连续的动作来完成，而无法清楚地了解每个动作如何对最终结果做出贡献。
最后，与国际象棋、围棋和扑克相比，可能的游戏状态数量（表示为“游戏树复杂性”）超出了图表，这使得解决起来非常困难。这就是 Stratego 令我们兴奋的原因，也是它代表着人工智能社区长达数十年的挑战的原因。
国际象棋、扑克、围棋和策略游戏之间的差异程度。
寻求平衡
DeepNash 采用了一种基于博弈论和无模型深度强化学习相结合的新颖方法。“无模型”意味着 DeepNash 不会尝试在游戏过程中显式地建模对手的私人游戏状态。特别是在游戏的早期阶段，当 DeepNash 对对手的棋子知之甚少时，这种建模即使不是不可能，也是无效的。
而且由于 Stratego 的游戏树复杂性如此之大，DeepNash 无法采用基于人工智能的游戏的可靠方法——蒙特卡罗树搜索。对于不太复杂的棋盘游戏和扑克来说，树搜索一直是人工智能领域许多里程碑式成就的关键要素。
相反，DeepNash 由一种新的博弈论算法思想提供支持，我们称之为正则化纳什动力学 (R-NaD)。R-NaD 以无与伦比的规模工作，将 DeepNash 的学习行为引导至所谓的纳什均衡（深入研究我们论文中的技术细节）。
随着时间的推移，导致纳什均衡的博弈行为是无法利用的。如果一个人或机器玩出完美的不可利用的策略，他们能达到的最差胜率将是 50%，而且只有在面对同样完美的对手时。
在与最好的 Stratego 机器人（包括计算机 Stratego 世界锦标赛的几位获胜者）的比赛中，DeepNash 的胜率高达 97%，并且经常达到 100%。在 Gravon 游戏平台上与顶级人类高手玩家对决时，DeepNash 取得了 84% 的胜率，历史排名前三。
期待意想不到的事情
为了实现这些结果，DeepNash 在最初的棋子部署阶段和游戏阶段都展示了一些显着的行为。为了变得难以被利用，DeepNash 制定了一种不可预测的策略。这意味着创建足够多样化的初始部署，以防止对手在一系列游戏中发现模式。在游戏阶段，DeepNash 在看似相同的操作之间进行随机分配，以防止出现可利用的倾向。
战略玩家努力做到不可预测，因此隐藏信息是有价值的。DeepNash 展示了它如何以非常引人注目的方式评估信息。在下面的例子中，在对抗人类玩家时，DeepNash（蓝色）在游戏初期牺牲了 7（大）和 8（上校）等棋子，因此能够找到对手的 10（元帅）， 9（一般）、一个 8 和两个 7。
在游戏早期的情况下，DeepNash（蓝色）已经找到了对手许多最强大的棋子，同时对自己的关键棋子保密。
这些努力使 DeepNash 在物质上处于显着的劣势；它失去了 7 和 8，而它的人类对手保留了所有 7 及以上的棋子。尽管如此，凭借对对手高层的可靠情报，DeepNash 评估其获胜机会为 70%，并且最终获胜。
虚张声势的艺术
就像在扑克中一样，优秀的策略玩家有时必须表现出力量，即使是在很弱的时候。DeepNash 学会了多种此类虚张声势的策略。在下面的示例中，DeepNash 使用 2（弱侦察兵，对手未知），就好像它是高级棋子一样，追击对手已知的 8。人类对手认为追击者最有可能是 10，因此尝试引诱它进入间谍的伏击。DeepNash 的这种策略，只冒一小部分风险，成功地冲掉并消除了对手的 Spy（关键棋子）。
人类玩家（红色）确信追逐他们 8 的未知棋子一定是 DeepNash 的 10（注：DeepNash 已经失去了唯一的 9）。
通过观看 DeepNash 与（匿名）人类专家玩的四个完整游戏视频来了解更多信息：游戏 1、游戏 2、游戏 3、游戏 4。
“DeepNash 的比赛水平让我感到惊讶。我从未听说过有哪个人工 Stratego 玩家的水平能够接近赢得与经验丰富的人类玩家的比赛所需的水平。但在亲自与 DeepNash 交手后，我对它后来在 Gravon 平台上取得的前三名并不感到惊讶。我预计如果能参加人类世界锦标赛，它会表现得很好。”
-
Vincent de Boer，论文合著者、前 Stratego 世界冠军
未来发展方向
虽然我们为高度定义的 Stratego 世界开发了 DeepNash，但我们新颖的 R-NaD 方法可以直接应用于其他完美或不完美信息的两人零和游戏。R-NaD 有潜力推广到远远超出两人游戏设置的范围，以解决大规模的现实世界问题，这些问题通常以不完美的信息和天文状态空间为特征。
我们还希望 R-NaD 能够帮助解锁人工智能在具有大量目标不同的人类或人工智能参与者的领域的新应用，这些参与者可能不知道其他人的意图或他们的环境中发生的事情，例如在大型- 大规模优化交通管理，以减少驾驶员的行程时间和相关的车辆排放。
在创建一个能够应对不确定性的通用人工智能系统时，我们希望将人工智能解决问题的能力进一步带入我们本质上不可预测的世界。
阅读我们在《科学》杂志上的论文，了解有关 DeepNash 的更多信息。
对于有兴趣尝试 R-NaD 或使用我们新提出的方法的研究人员，我们已经开源了我们的代码。
