本文作者来自于清华大学电子工程系，北京大学人工智能研究院、第四范式、腾讯和清华-伯克利深圳学院。其中第一作者张瑞泽为清华大学硕士，主要研究方向为博弈算法。通讯作者为清华大学电子工程系汪玉教授、于超博后和第四范式研究员黄世宇博士。
**
引言
强化学习（ReinforcementLearning，RL）是机器学习中的一个重要范式，旨在通过与环境的交互不断优化策略。基本问题建模是基于马尔可夫决策过程（Markovdecisionprocess，MDP），智能体通过观察状态、根据策略执行动作、接收相应的奖励并转换到下一个状态。最终目标是找到能最大化期望累计奖励的最优策略。自博弈（self-play）通过与自身副本或过去版本进行交互，从而实现更加稳定的策略学习过程。自博弈在围棋、国际象棋、扑克以及游戏等领域都取得了一系列的成功应用。在这些场景中，通过自博弈训练得到了超越人类专家的策略。尽管自博弈应用广泛，但它也伴随着一些局限性，例如可能收敛到次优策略以及显著的计算资源需求等。本综述组织架构如下：首先，背景部分介绍了强化学习框架和基础的博弈论概念。其次，在算法部分提出了一个统一的框架，并根据该框架将现有的自博弈算法分为四类，进行系统的比较和分析。在之后的应用部分中，展示自博弈具体如何应用到具体的复杂博弈场景。最后，进一步讨论了自博弈中的开放问题和未来的研究方向，并进行总结。
背景
我们定义了一个统一的自博弈框架，并将自博弈算法分为四大类：传统自博弈算法、PSRO系列算法、基于持续训练的系列算法和后悔最小化系列算法。
类型一：传统自博弈算法
传统自博弈算法从单一策略开始，逐步扩展策略池，包括Vanillaself-play（训练时每次对手都选择最新生成的策略），Fictitiousself-play（训练时每次对手都在现有训练完的策略中均匀采样），δ-uniformself-play（训练时每次对手都在现有训练完的最近的百分之δ策略中均匀采样），PrioritizedFictitiousSelf-play（根据优先级函数计算当前训练完的策略的优先级，训练时每次对手都根据这个优先级进行采样），IndependentRL（训练时双方策略都会改变，对手策略不再固定）。
类型二：PSRO系列算法
类似于传统自博弈算法，Policy-SpaceResponseOracle（PSRO）系列算法同样从单一策略开始，通过计算ORACLE逐步扩展策略池，这些新加入的策略是对当前元策略的近似BR。PSRO系列与传统自博弈算法的主要区别在于，PSRO系列采用了更复杂的MSS，旨在处理更复杂的任务。例如，α-PSRO使用了基于α-rank的MSS来应对多玩家的复杂博弈。类型三：持续训练系列算法PSRO系列算法中存在的两个主要挑战：首先，由于训练成本大，通常在每次迭代中截断近似BR计算，会将训练不充分的策略添加到策略池；其次，在每次迭代中会重复学习基本技能，导致效率较低。为了解决这些挑战，基于持续训练系列的算法提倡反复训练所有策略。与前面提到的两类最大区别是，持续训练系列算法同时训练整个策略池策略。这类算法采用多个训练周期，并在每个训练周期内依次训练策略池所有策略，而不再是通过逐步扩展策略池进行训练。
类型四：后悔最小化系列算法
各类型算法比较与总结图
应用
在本节中，我们通过将三类经典场景来介绍自博弈的经典应用：棋类游戏，通常涉及完全信息；牌类游戏（包括麻将），通常涉及不完全信息；以及电子游戏，具有实时动作而非简单回合制游戏。
棋类游戏领域，绝大多数是完全信息游戏，曾因引入两项关键技术而发生革命性变化：位置评估和蒙特卡罗树搜索。这两项技术在象棋、西洋跳棋、黑白棋、西洋双陆棋等棋盘游戏方面展现了超越人类的效果。相比之下，当这些技术应用于围棋时，由于围棋棋盘布局种类远超于上述提到的棋类游戏，因此仅能达到业余水平的表现。直到DeepMind推出了AlphaGo系列而发生了革命性的变化，AlphaGo系列算法利用自博弈的强大功能显著提升了性能，为围棋领域设立了新的基准。除了围棋，还有一种难度较高的棋类游戏是“军棋”（Stratego）。与大多数完全信息的棋类游戏不同，“军棋”是一个两人参与的不完全信息棋盘游戏。游戏分为两个阶段：部署阶段，玩家秘密安排他们的单位，为战略深度奠定基础；以及游戏阶段，目标是推断对手的布局并夺取他们的旗帜。DeepNash采用基于进化的自博弈算法R-NaD达到了世界第三的人类水平。
德州扑克（TexasHold’em）是一种欧美流行的扑克游戏，适合2到10名玩家，当玩家数量增加，游戏变得更加复杂。此外，有三种下注形式：无限注、固定注和底池限注。每种形式在具有不同的游戏复杂度。在牌类游戏中，游戏抽象对于简化游戏复杂程度至关重要，可以将游戏的庞大状态空间减少到更容易处理的数量。Cepheus采用后悔最小化系列算法CFR+解决了最容易的双人有限注德州扑克。对于更复杂的双人无限注德州扑克，DeepStack和Libratus采用子博弈重新计算的方式来实时做出决策，击败职业德州扑克选手。Pluribus在Libratus基础上更进一步解决了六人无限注德州扑克。斗地主需要同时考虑农民之间的合作和农民地主之间的竞争。斗地主同样是不完全信息博弈，这为游戏增加了不确定性和策略深度。DeltaDou是基于AlphaZero开发的首个实现专家级斗地主表现的算法。之后的DouZero通过选择采样方法而非树搜索方法来降低训练成本，采用自博弈获取训练数据。麻将同样基于不完全信息做出决策，此外，麻将的牌数更多，获胜牌型也更为复杂，对AI更具挑战性。Suphx通过监督学习和自我博弈强化学习成为首个达到与人类专家水平的算法。NAGA和腾讯设计的LuckyJ同样也在在线平台上达到了人类专家水平。
与传统棋类游戏和牌类游戏不同，电子游戏通常具有实时操作、更长的动作序列以及更广泛的动作空间和观察空间。在星际争霸（StarCraft）中，玩家需要收集资源、建设基地并组建军队，通过精心的计划和战术执行，使对方玩家失去所有建筑物，来取得胜利。AlphaStar使用监督学习、端到端的强化学习和分层自博弈训练策略，在星际争霸II的1v1模式比赛中击败了职业玩家。MOBA游戏要求两支玩家队伍各自操控他们独特的英雄，互相竞争以摧毁对方的基地。每个英雄都有独特的技能，并在队伍中扮演特定的角色，也无法观测全部地图。OpenAIFive在简化版本的Dota2中击败了世界冠军队，其训练过程使用混合类型自博弈，有80%的概率进行Naiveself-play，20%的概率使用Prioritizedself-play。腾讯同样采用自博弈训练在王者荣耀游戏1v1和5v5模式中都击败了职业选手。GoogleResearchFootball（GRF）是一个开源的足球模拟器，输入是高层次的动作，需要考虑队友之间的合作和两个队伍之间的竞争，且每队有11人。TiKick通过WeKick的自博弈数据进行模仿学习，再利用分布式离线强化学习开发了一个多智能体AI。TiZero将课程学习与自博弈结合，无需专家数据，达到了比TiKick更高的TrueSkill评分。