2023/11/18 10:17

玩转围棋、国际象棋、扑克，DeepMind推出通用学习算法SoG

2016 年 3 月，一场机器人与围棋世界冠军、职业九段棋手李世石展开的围棋人机大战受到全球的高度关注。我们知道，最后的结果是 DeepMind 的机器人 AlphaGo 以 4 比 1 的总比分获胜。这是人工智能领域一个里程碑性的事件，也让「博弈」成为一个热门的 AI 研究方向。

AlphaGo 之后，DeepMind 又推出了赢得国际象棋的 AlphaZero、击败《星际争霸 II》的 AlphaStar 等等。使用搜索和学习的方法，AI 在许多完美信息博弈中表现出强大的性能，而使用博弈论推理和学习的方法在特定的不完美信息博弈中表现出强大的性能。

然而，大多数成功案例有一个重要的共同点：专注于单一博弈项目。例如，AlphaGo 不会下国际象棋，而 AlphaZero 虽然掌握了三种不同的完美信息博弈，但 AlphaZero 无法玩扑克牌，也不清楚能否扩展到不完美信息博弈。此外，现有研究往往会使用特定领域的知识和结构使 AI 实现强大的性能。

现在，来自 Google Deepmind 的研究团队提出了一种利用自我博弈学习、搜索和博弈论推理实现强大博弈性能的通用学习算法 ——Student of Games（SoG）。研究论文发表在《Science Advances》上。

论文地址：https://www.science.org/doi/full/10.1126/sciadv.adg3256

SoG 算法结合了引导式搜索（guided search）、自我对弈（self-play）学习和博弈论推理（game-theoretic reasoning）。实验结果表明，SoG 可以在大型完美和不完美信息博弈中表现出强大的性能，这是迈向任意环境真正通用算法的重要一步。

方法简介

SoG 模型可以在不同的游戏中自由发挥，并教会自己如何与自己的另一个版本进行对战，能够学习新策略并逐渐变得更有能力。虽然 AlphaZero 也可以适应完美信息博弈，但 SoG 可以适应完美和不完美信息博弈，从而具有更强的通用性。

SoG 采用成长树虚拟遗憾最小化（growing-tree counterfactual regret minimization，GT-CFR）算法。GT-CFR 算法是一种随时可以进行局部搜索，非均匀地构建子博弈，并将树扩展至最相关的未来状态，同时可以迭代地细化价值与策略。

此外，SoG 还采用了有效的自我对弈：利用博弈结果和递归子搜索来训练价值与策略网络，并应用于之前搜索中出现过的情况。

SoG 算法通过声音自我对弈来训练智能体：每个玩家在面临决策时，使用配备虚拟价值与策略网络（Counterfactual Value-and-Policy Network，CVPN）的声音 GT-CFR 搜索来生成当前状态的策略，并根据该策略采取行动。

自我对弈过程会生成两种类型的训练数据，用于更新价值与策略网络，一种是搜索查询，一种是完整博弈轨迹。在实际应用中，自我对弈数据生成和训练是并行发生的：参与者生成自我对弈数据（并解决查询）；训练者学习新网络并定期更新参与者。

实验结果

众所周知，传统搜索在不完美信息博弈中存在缺陷，并且评估集中在单一领域（如扑克牌），SoG 填补了这一空白。通过重新解决子博弈，SoG 保证可以找到近似纳什均衡，并且在小型博弈中保证可计算性。

具体来说，SoG 在四种不同的游戏中展示了强大的性能：两种完美信息博弈（国际象棋和围棋）和两种不完美信息博弈（扑克和 Scotland Yard）。值得注意的是，与扑克相比，Scotland Yard 的搜索范围和游戏长度要长得多，需要长期规划。

SoG 与 AlphaZero 一样，利用最少的领域知识，将搜索与自我对弈相结合。与 MCTS 不同，SoG 的搜索算法基于虚拟遗憾最小化，对完美和不完美信息博弈都是有效的。

下图展示了 SoG 在不同数量 GT-CFR 下的可利用性。

^{A 表为 Leduc 扑克，B 表为苏格兰场}

下图展示了 SoG 随着神经网络评估次数的增加与 AlphaZero 可扩展性的比较，测量方式为相对 Elo 评分尺度。

^{A 表为国际象棋，B 表为围棋}

^{参考链接：https://www.newscientist.com/article/2402645-game-playing-deepmind-ai-can-beat-top-humans-at-chess-go-and-poker/}

工程Student of Games

相关数据

DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年，最初名称是DeepMind科技（DeepMind Technologies Limited），在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯，谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后，Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏，例如即时战略游戏《星际争霸II》（StarCraft II）。深度AI如果能直接使用在其他各种不同领域，除了未来能玩不同的游戏外，例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作，基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

https://deepmind.com/

纳什均衡技术

纳什平衡，又称为非合作赛局博弈，是在非合作博弈状况下的一个概念解，在博弈论中有重要地位，以约翰·纳什命名。如果某情况下无一参与者可以通过独自行动而增加收益，则此策略组合被称为纳什均衡点。

来源：维基百科

AlphaZero技术

DeepMind 提出的 AlphaZero 不仅征服了围棋，也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。DeepMind 推出的 AlphaGo 曾在围棋项目中取得了超越人类的表现，其研究曾经两次登上 Nature。2018 年 12 月，AlphaGo 的「完全自我博弈加强版」AlphaZero 的论文又登上另一大顶级期刊 Science 的封面。在论文中，AlphaZero 不仅征服了围棋，也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。

来源：机器之心

局部搜索技术

在计算机科学中，局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。局部搜索的优点是简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。

来源：维基百科

人工智能技术

在学术研究领域，人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体（intelligent agent）

来源：Russell, S., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach.

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度，其目的是进行资源的优化。常见的规划方法包括经典规划（Classical Planning）、分层任务网络（HTN）和 logistics 规划。

来源：机器之心

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

策略网络技术

在强化学习中，策略网络指一组相对稳定的关系，这些关系具有非等级和相互依赖的性质，将各个行为者（actor）联系起来。

来源：igi-global

博弈论技术

博弈论，又译为对策论，或者赛局理论，应用数学的一个分支，1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》，标志着现代系统博弈理论的的初步形成，因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

来源：维基百科

查询技术

一般来说，查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域，查询指的是数据库和信息系统对信息检索的精确要求

来源：Wikipedia

完美信息博弈技术

在经济学中，完全的信息是完美竞争的特征。随着市场信息的完善，所有消费者和生产者都被假定在对自由市场体系进行理论化和财务政策效应时，对产品的价格，效用，质量和生产方法有完整的认识。

来源：Wikipedia

AlphaStar技术

AlphaStar是2019年1月DeepMind推出的打星际争霸2的AI系统。在1月的首次亮相中，DeepMind播放的比赛视频显示AlphaStar击败了两名人类职业选手TOL与MaNa，引起了业内极大的关注。DeepMind 官方博客介绍，AlphaStar 的行为是由一种深度神经网络生成的，该网络从原数据界面（单位列表与它们的特性）接收输入数据，输出构成游戏内行为的指令序列。具体来说，该神经网络使用了一个 transformer 作为躯干，结合了一个深度 LSTM 核、一个带有 pointer 网络的自动回归策略 head 以及一个中心价值基线。

来源：机器之心官网 DeepMind博客

围棋技术

围棋是一种策略性棋类，使用格状棋盘及黑白二色棋子进行对弈。起源于中国，中国古时有“弈”、“碁”、“手谈”等多种称谓，属琴棋书画四艺之一。西方称之为“Go”，是源自日语“碁”的发音。

来源：维基百科