共计 3243 个字符，预计需要花费 9 分钟才能阅读完成。
背景
2017 年，Libratus 和 DeepStack 两个算法被提出，用于解决无限度德州扑克。DeepStack 和 Libratus 不谋而合的应用 Counterfactual Regret Minimization (CFR) 来找到靠近纳什平衡策略。
网上有很多介绍 CFR 算法的文章，这些文章零碎的介绍了博弈论的概念，CFR 算法中的公式和推导过程。本文尽量避免引入新概念和简单公式，尝试通过示例和读者相熟的形式介绍算法和背地的思路。因为工夫缓和以及能力所限，不免存在纰漏，敬请大家斧正。
遗憾最小化和 Regret Matching
在介绍算法之前，大家无妨花 30 秒应用“如果当初…，当初就不会…” 来造个句。
… …
好了，不晓得大家造了什么句子，可能是一个悲伤的故事。
CFR 算法正是基于这样的思路：如果一个智能体因为采取了某个动作而带来了损失，那么智能体须要防止采取这个动作。更进一步，计算机并不了解遗憾，CFR 算法将遗憾进行量化——最好的口头计划与理论采取行动计划之间的差距
以石头 - 剪刀 - 布游戏为例，假如博得较量收益为 1，输掉较量收益为 -1，平局收益 0。显然，最优策略是博得较量。当对手出石头时，咱们本人出石头，剪刀，布的收益和遗憾值如下表所示：
对手 本人 收益 遗憾值 = 最优策略收益 – 以后动作的收益
石头 剪刀 -1 2
石头 石头 0 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}10
160
，有人估算宇宙原子总数大抵是 10^{80}10
80
，现有的计算机还是没有能力存储这么多 信息集 - 口头对，也没有方法计算这些冀望：
信息集 - 口头对：这比较简单，和很多传统算法一样，能够通过神经网络来提取特色，升高维度，拟合出一个策略
计算冀望：计算冀望时，须要对所有的可能性进行累加。目前的解决方案是，通过采样形式升高搜寻空间，即只应用局部动作计算冀望；同时减少搜寻的次数，近似的估算出一个冀望。典型的算法有 outcome sampling、external sampling 等，这些算法都能够统称为 MCCFR。
总结
本文应用艰深形式介绍 CFR 算法思维和倒退脉络，实用于初学者的入门指南。MindSpore Reinforcement[https://gitee.com/mindspore/r…]近期会上线 DeepCFR 算法，有趣味进一步了深刻理解算法的读者欢送移步围观。
最初插入一波广告：MindSpore Reinforcement 是一个开源的强化学习框架，为强化学习算法提供了洁净整洁的 API 形象，将算法与部署和执行进行解耦，包含异构加速器、并行度和跨 worker 集群部署，欢送大家 Star，fork、共同开发。