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

徐俊楚
2023-12-01

背景

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

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

遗憾最小化和Regret Matching

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

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

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

对手自己收益遗憾值 = 最优策略收益 - 当前动作的收益
石头剪刀-12
石头石头01
石头10

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

假设对手则采取以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、共同开发

 类似资料: