·180· 智能系统学报 第15卷 策过程，博弈时棋面可以认为是状态空间。给定 果映射回原问题当中，于是得到原问题的纳什均 一个棋面，可以继续走子的位置有限，因此选择 衡解，如图2所示1。此外，强化学习越来越多地 可走子的位置就是当前状态下可以采取的动作集 应用于非完全信息博弈的策略求解，在连续动态 合。一旦走子之后，棋面发生改变，即以转移概 的环境中做出合理的决策正是强化学习的模型所 率p=1的概率转换到下一状态，因为围棋总是在 擅长的内容。 下棋的过程中逐步建立优势并最终取得胜利，所 原游戏博弈树 抽象所得游戏 以回报的大小可以由当前的双方局势的优劣来决 博弈树 定。这样就将围棋博弈转换成了马尔科夫决策过 抽象算法 程，而所求解的策略就是使得这个马尔科夫决策 过程总回报的期望最大的策略。AlphaGo Zero就 是在求取这样的策略。 AlphaGo Zero之所以能在自博弈的过程中提 反向映射 升自己的策略，是因为它使用了深度强化学习模 原游戏 抽象所得 纳什均衡解 纳什均衡解 型进行策略估计和策略提升。在深度强化学习 中，有两个深度神经网络，一个是策略网络，一个 图2非完全信息博弈的策略求解 是价值网络，这两个网络是同一个网络的两个分 Fig.2 Process of solving an incomplete information game 支，将棋面作为图像输入网络，经过卷积等操作， 3.2.2无限注多人德州扑克策略求解 最后输出当前状态的收益以及在当前状态下应当 与棋类游戏在完全信息条件下进行不同，扑 采取的策略。 克游戏是一种非完全信息博弈。在扑克游戏中， 这里的策略网络并不是直接输出当前局势下 每个玩家无法知道对手的手牌，这也使得求解博 的走子位置，而是输出几个预测位置，并按照策 弈策略变得极为困难。比如在这种博弈过程中无 略网络的预测进行蒙特卡洛树搜索，将蒙特卡洛 法计算局势的收益，这导致了不能按照完全信息 树搜索所得策略作为最终的落子策略。蒙特 博弈方法来解决非完全信息博弈问题。2018年， 卡洛树搜索是一种结合随机模拟和采样的最优决 智能体Libratus首次在双人德州扑克中击败人类 策方法，依靠快速的搜索效率和可靠的搜索结 选手向，2019年，使用类似算法的Pluribus在多人 果，它被广泛应用于完全信息博弈中。蒙特卡洛 德州扑克中也获得胜利。 树搜索的过程包括路径选择(selection)、节点扩展 在德州扑克游戏中，先要对庞大的博弈树进 (expansion)、模拟实验(simulation)和反向传播 行剪枝，形成一个抽象游戏。具体来说，需要将 (backpropagation)4个步骤，通过这4个步骤的不 相近的状态节点进行合并，压缩博弈树的大小， 断重复，确定不同行动的回报，并做出决策。在 此外还需要将每次下注的金额限制在几个固定数 AlphaGo Zero中，蒙特卡洛最终模拟的结果还被 额上，从而减小行为空间的大小。 反馈到了深度神经网络中，用于训练价值网络的 Pluribus和Libratus的训练不断通过自博弈过 参数。 程来完成。这个自博弈过程中使用了虚拟遗憾值 3.2非完全信息下的博弈 最小化算法。所谓遗憾值指在过去几轮模拟博 3.2.1非完全信息博弈的特点 弈中，某一局势下采取其他策略与当前的策略带 相对于完全信息的博弈，不完全信息下的博 来的收益之差的累加。利用遗憾值就可以更新策 弈更加符合现实场景，能够指导人们对现实问题 略，使得智能体对所采取的新策略“遗憾”较少， 的科学决策。在非完全信息的纳什均衡求解中， 也就收益更高。虽然扑克游戏的博弈过程比围棋 对手采取的行动不一定是可见的，仅能根据部分 所用时间短，但也无法立刻得知每一步博弈后的 已知的信息进行决策。非完全信息博弈树通常规 收益，所以需要通过“虚拟”方法来计算每一步行 模非常大，因为在中间状态下可能采取的行动一 为的期望收益。一旦计算得到期望收益，就可以 般有无穷多种，为了削减搜索空间，人们需要使 比较当前策略与其他策略的虚拟遗憾值，并根据 用一些抽象算法对原有博弈问题进行压缩，即合 遗憾值的大小来更新策略。 并博弈树中的相似状态、压缩搜索层数以及剪枝 在实际游戏时，由于局势是不断动态变化的， 等，最终得到一个相对简单的抽象问题，然后求 仅仅依靠预训练所得策略难以完成决策，因此在 解这个抽象问题的纳什均衡解，最后将所求解结 博弈的过程中还需要不断根据局势来缩小博弈搜策过程，博弈时棋面可以认为是状态空间。给定 一个棋面，可以继续走子的位置有限，因此选择 可走子的位置就是当前状态下可以采取的动作集 合。一旦走子之后，棋面发生改变，即以转移概 率 p=1 的概率转换到下一状态，因为围棋总是在 下棋的过程中逐步建立优势并最终取得胜利，所 以回报的大小可以由当前的双方局势的优劣来决 定。这样就将围棋博弈转换成了马尔科夫决策过 程，而所求解的策略就是使得这个马尔科夫决策 过程总回报的期望最大的策略。AlphaGo Zero 就 是在求取这样的策略。 AlphaGo Zero 之所以能在自博弈的过程中提 升自己的策略，是因为它使用了深度强化学习模 型进行策略估计和策略提升。在深度强化学习 中，有两个深度神经网络，一个是策略网络，一个 是价值网络，这两个网络是同一个网络的两个分 支，将棋面作为图像输入网络，经过卷积等操作， 最后输出当前状态的收益以及在当前状态下应当 采取的策略。 这里的策略网络并不是直接输出当前局势下 的走子位置，而是输出几个预测位置，并按照策 略网络的预测进行蒙特卡洛树搜索，将蒙特卡洛 树搜索[32] 所得策略作为最终的落子策略。蒙特 卡洛树搜索是一种结合随机模拟和采样的最优决 策方法，依靠快速的搜索效率和可靠的搜索结 果，它被广泛应用于完全信息博弈中。蒙特卡洛 树搜索的过程包括路径选择 (selection)、节点扩展 (expansion)、模拟实验 (simulation) 和反向传播 (backpropagation) 4 个步骤，通过这 4 个步骤的不 断重复，确定不同行动的回报，并做出决策。在 AlphaGo Zero 中，蒙特卡洛最终模拟的结果还被 反馈到了深度神经网络中，用于训练价值网络的 参数。 3.2 非完全信息下的博弈 3.2.1 非完全信息博弈的特点 相对于完全信息的博弈，不完全信息下的博 弈更加符合现实场景，能够指导人们对现实问题 的科学决策。在非完全信息的纳什均衡求解中， 对手采取的行动不一定是可见的，仅能根据部分 已知的信息进行决策。非完全信息博弈树通常规 模非常大，因为在中间状态下可能采取的行动一 般有无穷多种，为了削减搜索空间，人们需要使 用一些抽象算法对原有博弈问题进行压缩，即合 并博弈树中的相似状态、压缩搜索层数以及剪枝 等，最终得到一个相对简单的抽象问题，然后求 解这个抽象问题的纳什均衡解，最后将所求解结 果映射回原问题当中，于是得到原问题的纳什均 衡解，如图 2 所示[33]。此外，强化学习越来越多地 应用于非完全信息博弈的策略求解，在连续动态 的环境中做出合理的决策正是强化学习的模型所 擅长的内容[34]。 原游戏博弈树 抽象算法 反向映射 抽象所得游戏 博弈树 原游戏 纳什均衡解 抽象所得 纳什均衡解 图 2 非完全信息博弈的策略求解 Fig. 2 Process of solving an incomplete information game 3.2.2 无限注多人德州扑克策略求解 与棋类游戏在完全信息条件下进行不同，扑 克游戏是一种非完全信息博弈。在扑克游戏中， 每个玩家无法知道对手的手牌，这也使得求解博 弈策略变得极为困难。比如在这种博弈过程中无 法计算局势的收益，这导致了不能按照完全信息 博弈方法来解决非完全信息博弈问题。2018 年， 智能体 Libratus 首次在双人德州扑克中击败人类 选手[6] ，2019 年，使用类似算法的 Pluribus 在多人 德州扑克中也获得胜利[7]。 在德州扑克游戏中，先要对庞大的博弈树进 行剪枝，形成一个抽象游戏。具体来说，需要将 相近的状态节点进行合并，压缩博弈树的大小， 此外还需要将每次下注的金额限制在几个固定数 额上，从而减小行为空间的大小。 Pluribus 和 Libratus 的训练不断通过自博弈过 程来完成。这个自博弈过程中使用了虚拟遗憾值 最小化算法[35]。所谓遗憾值指在过去几轮模拟博 弈中，某一局势下采取其他策略与当前的策略带 来的收益之差的累加。利用遗憾值就可以更新策 略，使得智能体对所采取的新策略“遗憾”较少， 也就收益更高。虽然扑克游戏的博弈过程比围棋 所用时间短，但也无法立刻得知每一步博弈后的 收益，所以需要通过“虚拟”方法来计算每一步行 为的期望收益。一旦计算得到期望收益，就可以 比较当前策略与其他策略的虚拟遗憾值，并根据 遗憾值的大小来更新策略。 在实际游戏时，由于局势是不断动态变化的， 仅仅依靠预训练所得策略难以完成决策，因此在 博弈的过程中还需要不断根据局势来缩小博弈搜 ·180· 智 能 系 统 学 报 第 15 卷