MindSpore：一文带你入门虚拟遗憾最小化CFR算法

背景

2017年，Libratus和DeepStack两个算法被提出，用于解决无限制德州扑克。DeepStack 和 Libratus不约而同的使用 Counterfactual Regret Minimization (CFR) 来找到接近纳什均衡策略。

网上有很多介绍CFR算法的文章，这些文章系统的介绍了博弈论的概念，CFR算法中的公式和推导过程。本文尽量避免引入新概念和复杂公式，尝试通过示例和读者熟悉的方式介绍算法和背后的思路。由于时间紧张以及能力所限，难免存在纰漏，敬请大家指正。

遗憾最小化和Regret Matching

在介绍算法之前，大家不妨花30秒使用“如果当初…，现在就不会…"来造个句。
… …
好了，不知道大家造了什么句子，可能是一个悲伤的故事。

CFR算法正是基于这样的思路：如果一个智能体因为采取了某个动作而带来了损失，那么智能体需要避免采取这个动作。更进一步，计算机并不理解遗憾，CFR算法将遗憾进行量化——最好的行动方案与实际采取行动方案之间的差距

以石头-剪刀-布游戏为例，假设赢得比赛收益为1，输掉比赛收益为-1，平局收益0。显然，最优策略是赢得比赛。当对手出石头时，我们自己出石头，剪刀，布的收益和遗憾值如下表所示：

在石头-剪刀-布游戏中，我们并不知道对方接下来会出什么，但是仍然通过历史对局的累计遗憾值来选择动作，累计遗憾值反映了对手历史的策略。

假设对手则采取以1/3概率出石头、剪刀和布，而我们自己是一个总结和善于改进的智能体——游戏过程中记录遗憾值，并选择遗憾值最低的动作。

import numpy as np
from prettytable import PrettyTable
 
class Opponent:
    def __init__(self):
        # 对手采取石头，剪刀，布的概率
        self.probs = (1/3, 1/3, 1/3)
 
    def action(self):
        return np.random.choice(len(self.probs), 1, p=self.probs).item(0)
 
class Agent:
    def __init__(self):
        self.cum_regret = np.array([0.1, 0.1, 0.1])
 
    def action(self):
        # regret matching
        return np.argmin(self.cum_regret)
 
    def update_regret(self, action, regret):
        self.cum_regret[action] += regret
 
class Game:
    def __init__(self):
        self.payoff = [
            #石头  剪刀  布
            [0,   1,  -1], # 石头
            [-1,   0,  1], # 剪刀
            [1,   -1,  0]  # 布
          ]
 
    @property
    def best_payoff(self):
        return 1
 
    def play(self, agent_action, opponent_action):
        return self.payoff[agent_action][opponent_action]
 
game = Game()
opponet = Opponent()
agent = Agent()
table = PrettyTable(['round','opponent','agent', 'current round regret', 'cum_regret'])
for round in range(100):
    agent_action = agent.action()
    opponent_action = opponet.action()
    payoff = game.play(agent_action, opponent_action)
    regret = game.best_payoff - payoff
    agent.update_regret(agent_action, regret)
    table.add_row([round, opponent_action, agent_action, regret, str(agent.cum_regret)])
 
print(table)

随着博弈次数的增加，我们也会逐渐采用1/3的概率选择石头、剪刀和布。有了解过博弈论的同学应该可以发现，CFR算法使得智能体在石头-剪刀-布游戏中达到了纳什均衡

+-------+----------+-------+----------------------+---------------+
| round | opponent | agent | current round regret |   cum_regret  |
+-------+----------+-------+----------------------+---------------+
|   0   |    2     |   0   |          2           |   [2. 0. 0.]  |
|   1   |    0     |   1   |          2           |   [2. 2. 0.]  |
|   2   |    1     |   2   |          2           |   [2. 2. 2.]  |
|   3   |    0     |   0   |          1           |   [3. 2. 2.]  |
|   4   |    1     |   1   |          1           |   [3. 3. 2.]  |
|   5   |    2     |   2   |          1           |   [3. 3. 3.]  |
|   6   |    1     |   0   |          0           |   [3. 3. 3.]  |
|   7   |    2     |   0   |          2           |   [5. 3. 3.]  |
... ...
|   94  |    0     |   2   |          0           | [36. 35. 34.] |
|   95  |    0     |   2   |          0           | [36. 35. 34.] |
|   96  |    0     |   2   |          0           | [36. 35. 34.] |
|   97  |    2     |   2   |          1           | [36. 35. 35.] |
|   98  |    0     |   1   |          2           | [36. 37. 35.] |
|   99  |    1     |   2   |          2           | [36. 37. 37.] |
+-------+----------+-------+----------------------+---------------+

在实际算法中，为了平衡探索-利用，智能体通常通过采样的方式选择动作，这意味着即时某个动作的遗憾值很大，也有较小的概率被采样到。

考虑更加复杂的情况

接下来，我们尝试将石头-剪刀-布的算法套用到扑克游戏中来，这时候会遇到一些问题

• 玩家不知道自己处于何种状态：
  在一局游戏结束之前，玩家得到的信息是有限的。例如：玩家只知道自己的手牌、公牌，以及所有玩家出牌的记录，并不知道对手的手牌。
  解决方案：既然没有办法准确区分那就不区分，干脆将这些可能的状态放在一个集合里，起个高大上的名字——信息集(Information Set)

• 某个动作产生的收益不唯一：
  玩家执行某个动作之后，并不能立刻得到反馈，需要再经历多次交互之后，才能得到最终的收益。
  最终的收益不仅和当前采取的动作有关，还和自己后续的动作，对手后续的动作、以及对手底牌有关。
  解决这个问题比较简单：将上述不确定性作为随机变量，计算统计学意义上的收益——期望。

• 最优的策略和收益：
  和上面的情况类似，玩家不知道最优的策略(事实上这正是我们的求解目标)，也不知道最优策略下的收益
  解决方案：虽然我们不知道最优策略的收益，我们可以退而求其次，找到一个还不错的策略，例如计算当前信息集下各个动作收益的期望。随着智能体水平越来越高，这个替代品也越来越接近最优策略收益。
  这里暂时略过难懂的证明过程和公式，整个过程类似EM(Expectation Maximization Algorithm)算法：

  • 利用 当前策略的期望收益 来改进 智能体的策略
  • 利用 智能体的策略 来估算 当前策略期望收益
  • 如此往复…

继续增加难度

双人无限制德州扑克 的决策点个数超过10^{160}10160，有人估算宇宙原子总数大致是10^{80}1080，现有的计算机还是没有能力存储这么多 信息集-行动对，也没有办法计算这些期望：

• 信息集-行动对：这比较简单，和很多传统算法一样，可以通过神经网络来提取特征，降低维度，拟合出一个策略
• 计算期望：计算期望时，需要对所有的可能性进行累加。目前的解决方案是，通过采样方式降低搜索空间，即只使用部分动作计算期望；同时增加搜索的次数，近似的估算出一个期望。典型的算法有outcome sampling、external sampling等，这些算法都可以统称为MCCFR。

总结

本文使用通俗方式介绍CFR算法思想和发展脉络，适用于初学者的入门指南。MindSpore Reinforcement[reinforcement: A high-performance, scalable MindSpore reinforcement learning framework.]近期会上线DeepCFR算法，有兴趣进一步了深入了解算法的读者欢迎移步围观。

最后插入一波广告：MindSpore Reinforcement是一个开源的强化学习框架，为强化学习算法提供了干净整洁的API抽象，将算法与部署和执行进行解耦，包括异构加速器、并行度和跨worker集群部署，欢迎大家Star，fork、共同开发。