浅谈德州扑克 AI 核心算法：CFR

本文首发于行者AI

引言

自 2017 年 AlphaGo 打败世界围棋冠军柯洁后，人工智能彻底进入大众视野，一时间棋牌类的 AI 在人工智能界掀起了一股大风。其实早在 AlphaGo 之前，人们就对棋牌类的人工智能发起了挑战，从简单的跳棋、五子棋，到更加复杂的中国象棋、国际象棋，以及最近非常热门的围棋和德州扑克,数十年间也是硕果累累。而相对于跳棋、象棋等完全信息游戏，德州扑克不仅要根据不完全信息进行复杂决策，还要应付对手的虚张声势、故意示弱等招数，其对应的博弈树无论是广度还是深度都十分庞大，它也一直都是科学家们想要攻克的高山。而在 AlphaGO 打败柯洁的同年，德扑 AI DeepStack 和 Libratus 也先后在 “一对一无限注德州扑克” 上击败了职业扑克玩家,在不完全信息博弈中做出了里程碑式的突破，而他们所采用的的核心算法就是 Counterfactual Regret Minimization(CFR)。

1. Regret Matching

1.1 算法原理

CFR 算法的前身是 regret matching 算法，在此算法中，智能体的动作是随机选择的，其概率分布与 positive regret 呈正比， positive regret 表示一个人因为过去没有选择该行动而受到的相对损失程度。

这里对 Regret Matching 算法中的符号做出若干定义：

• N=\left{1,2,...,n\right} 表示博弈玩家的有限集合。玩家$i$ 所采用的的策略为${\sigma }_i$ 。

• 对于每个信息集$I_i\in {\xi }_i,{\sigma }_i(I_i):A(I_i)\to [0,1]$，是在动作集$A(I_i)$上的概率分布函数。玩家$i$的策略空间用${\Sigma }_i$表示 。

• 一个策略组包含所有玩家策略，用$\sigma =({\sigma }_1,{\sigma }_2,...,{\sigma }_n)$.

• 在博弈对决中，不同玩家在不同时刻会采取相应策略以及行动。策略下对应的动作序列发生概率表示为${\pi }^{\sigma }(h)$，且${\pi }^{\sigma }(h)={\prod }_{i\in N}{\pi }_i^{\sigma }(h)$
  

• 这里的${\pi }_i^{\sigma }(h)$表示玩家$i$使用策略${\sigma }_i$促使行动序列$h$发生的概率，除了玩家$i$以外，其他玩家通过各自策略促使行动序列$h$发生的概率为：${\pi }_{-i}^{\sigma }(h)={\prod }_{i\in N/i}{\pi }_j^{\sigma }(h)$。

• 对于每个玩家$i\in N,u_i:Z\to R$，表示玩家的收益函数。

• 计算玩家在给定策略下所能得到的期望收益：$u_i(\sigma )={\Sigma }_{h\in Z}{u}_i(h){\pi }^{\sigma }(h)$。

• 纳什均衡：策略组 $\sigma=(\sigma^_1,\sigma^_2,...,\sigma^n)$是纳什平衡当且仅当对每个玩家$i∈N$,满足条件：$u_i(\sigma)\geq max{\sigma_i^`}(\sigma^_1,\sigma^_2,...,\sigma^_n)$。

• 遗憾值：玩家在第 T 次采取策略的遗憾值为：$$R_i^T(a)={\Sigma }_{T=1}^T({\mu }_i(a,{\sigma }_{-i}^t)-{\mu }_i({\sigma }_i^t,{\sigma }_{-i}^t))$$

• 策略：根据遗憾值更新策略 $${\sigma }_i^{T+1}(a)=\frac{R_i^T(a)}{{\Sigma }_{b\in A_i}{R}_i^T(b)}$$

• 平均遗憾值：假设博弈能够重复进行，令第次的博弈时的策略组为，若博弈已经进行了次，则这次博弈对于玩家的平均遗憾值定义为：$${Regret_i^M}=\frac{1}{M}max_{\sigma_i^∈\Sigma_{i=1}^M}(u_i(\sigma_i^,\sigma_{-t}^t)-u_i(\sigma^t))$$

Regret matching 算法流程为：

• 对于每一位玩家，初始化所有累积遗憾为 0。

• for from 1 to T(T:迭代次数)：

• ​ a)使用当前策略与对手博弈

• ​ b)根据博弈结果计算动作收益，利用收益计算后悔值

• ​ c)历史后悔值累加

• ​ d)根据后悔值结果更新策略

• 返回平均策略（累积后悔值/迭代次数）

1.2 实例

石头剪子布是最为简单的零和博弈游戏，是典型的正则式博弈，其 payoff table 如下：

<div align='center'>图 1·石头剪刀布收益图</div>

Regret matching 算法流程在本例中为：

​ a)首次迭代，player1 和 player2 都以$\frac{1}{3}$概率随机选择动作，假设 player1 选择布，player2 选择剪刀。

​ b)以 player1 视角，首次博弈结果收益为：$u_{(r,s)}=1、u_{(p,s)}=-1、u_{(s,s)}=0$。

​ c)根据结果收益计算后悔值，

​ d)进行归一化处理更新 player1 的行动策略：$(\frac{2}{3}R,0P,\frac{1}{3}S)$.

​ e)根据更新后的策略选择动作进行多次博弈，直至达到纳什平衡

​ f)返回平均策略

核心代码如下（具体代码戳这儿）：

​ 1）获得策略方法：1.清除遗憾值小于零的策略并重置策略为 0；2.正则化策略，保证策略总和为 13.在某种情况下，策略的遗憾值总和为 0，此时重置策略为初始策略。

def get_strategy(self):       """       Get current mixed strategy through regret-matching       :return:       """       normalizing_sum = 0        # add this overcome initial best response opponent       # if min(self.strategy) < 0:       #     min_val = min(self.strategy)       #     self.strategy = [_ - min_val for _ in self.strategy]        for i in range(NUM_ACTIONS):           self.strategy[i] = max(self.regret_sum[i], 0)           normalizing_sum += self.strategy[i]        # normalize       for i in range(NUM_ACTIONS):           if normalizing_sum > 0:               self.strategy[i] /= normalizing_sum           else:               self.strategy[i] = 1 / NUM_ACTIONS           self.strategy_sum[i] += self.strategy[i]        return self.strategy

​ 2）训练方法：1.玩选择策略进行博弈，根据博弈结果计算动作效益；2.根据动作效益计算后悔值。

def train(self, iterations: int):    action_utility = [0] * NUM_ACTIONS     opponent_stats = [0] * NUM_ACTIONS    cum_utility = 0    for i in range(iterations):        # Get regret-matched mixed-strategy actions        strategy = self.get_strategy()        # strategy = self.get_average_strategy()         my_action = self.get_action(strategy)         other_action = self.get_action(self.opp_strategy)         opponent_stats[other_action] += 1         # Compute action utilities        action_utility[other_action] = 0        action_utility[(other_action + 1) % NUM_ACTIONS] = 1        action_utility[other_action - 1] = -1         # Accumulate action regrets        for a in range(NUM_ACTIONS):            self.regret_sum[a] += action_utility[a] - action_utility[my_action]             # self.regret_sum[a] = opponent_stats         cum_utility += action_utility[my_action]     print(f'opponent_stats: {opponent_stats}, {[_ - min(opponent_stats) for _ in opponent_stats]}')    print(f'cum utility: {cum_utility}')

实验结果：

​ 1)当固定对手策略为{0.4, 0.3, 0.3}时

<div align='center'>图 2·固定对手策略，玩家策略</div>

​ 2)当玩家和对手都采用 Regret Matching 更新策略时

<div align='center'>图 3·玩家和对手策略</div>

2. Counterfactual Regret Minimization

2.1 算法原理

石头剪子布是典型的“一次性”博弈，玩家做出动作即得到结果。而生活中显然许多的博弈属于序列化博弈，博弈由一系列的动作组成，上一步的动作可能会导致下一步的动作选择变更，最终的动作组合形成博弈结果。这种序列游戏我们不再使用 payoff table 表示，而是使用博弈树的形式。博弈树由多种状态组成，边表示从一个状态到另一个状态的转换。状态可以是机会节点或决策节点。机会节点的功能是分配一个机会事件的结果，因此每个边代表该机会事件的一个可能结果以及事件发生的概率。在决策节点上，边代表行动和后续状态，这些状态是玩家采取这些行动的结果。

同样地，对 CFR 算法中的符号进行若干定义：

• 每个信息集$I$发射部分的概率${\pi }^{\sigma }(I)={\Sigma }_{h\in I}{\pi }^{\sigma }(h)$，表示所有能到达信息集的行动序列的概率累加。

• 当采取策略$\sigma$下，施加博弈行动序列$h$后达到最终局势$z$的概率为：${\pi }^{\sigma }(h,z)$。

• 当采用策略$\sigma$时，其所对应的行动策略的虚拟收益:$u_i(\sigma ,h)={\Sigma }_{z\in Z}{\pi }^{\sigma }(h,z)u_i(z)$。

• 玩家$i$采取行动$a$所得到的的虚拟后悔值：$r(h,a)=v_i({\sigma }_{I\to a},h)-v_i(\sigma ,h)$。

• 行动序列$h$所对应的信息集$I$后悔值为：$r(I，a)=\Sigma r(h,a)$。

• 玩家$i$在第$T$轮次采取行动$a$的后悔值为：$Regre{t}_t^T(I,a)={\Sigma }_{t=1}^T{r}_i^t(I,a)$。

• 同样地，对于后悔值为负数不予考虑，记：$Regre{t}_t^{T,+}(I,a)=max(R_i^T(I,a),0)$。

• 在$T+1$轮次，玩家$i$选择行动$a$的概率计算如下：$\sigma_i^{T+1}(I,a)=\begin{cases}\frac{Regret_i^{T,+}(I,a)}{\Sigma a∈A(I)Regret_i^{T,+}(I,a)} &\text{if \Sigma_{a∈A(I)}Regret_i^{T,+}(I,a)>0}\\frac{1}{A(I)},&\text{otherwise}\end{cases}$

算法流程：

• 针对每个信息集，初始化后悔值和策略

• 使用当前策略与对手博弈

• 计算在本次博弈中所访问到的每个信息集的收益和后悔值

• 通过 Regret Matching 算法更新策略

• 多次迭代，直到纳什平衡

• 返回平均策略（累积后悔值/迭代次数）

2.2 实例

库恩扑克(Kunh’s pocker)是最简单的限注扑克游戏，由两名玩家进行游戏博弈，牌值只有 1，2 和 3 三种情况。每轮每位玩家各持一张手牌，根据各自判断来决定加定额赌注过牌(P）还是加注(B)。具体游戏规则如下：

<div align='center'>图 4·库恩扑克规则</div>

以玩家α视角构建库恩扑克博弈树：

<div align='center'>图 5·先手玩家博弈树</div>

CFR 算法流程在本例中为：

​ a)初始策略为随机策略，假设玩家α抽到的牌值为：3

​ b)第一轮迭代时，节点选择动作 P 的虚拟收益计算方法为：$u_A^{\sigma }(3,P)={\Sigma }_{i=1}^3{\pi }_B^{\sigma }(3P){\pi }^{\sigma }(z_i|3P)u_A(z_i)$。结合博弈树求解得到：${\pi }_B^{\sigma }(3,P)=1$、${\pi }^{\sigma }(z_1|3P)=0.5$、${\pi }^{\sigma }(z_2|3P)=0.25$、${\pi }^{\sigma }(z_3|3P)=0.25$；$u_A(z_1)=1$、$u_A(z_2)=1$ $u_A(z_3)=2$ $。\therefore u_A(3,P)=1.25$。同理，计算节点选择动作 B 的虚拟收益为：$u_A(3,B)=0.5$

​ c)利用虚拟收益更新后悔值：$R^1(3,P)=R^0(3,P)+u_A^{\sigma }(3,P)-(\sigma (3,B)u_A^{\sigma }(3,B)+\sigma (3,P)u_A^{\sigma }(3,P))=0+1.25-(0.5\times 0.5+0.5\times 1.25)=0.375$

​ d)利用后悔值更新策略：${\sigma }_A^1(3,P)=0.375÷(0.375+0)=1$，${\sigma }_A^1(3，B)=1÷|A(3)|=0.5$

​ e)归一化策略：${\sigma }_A^1(3,P)=\frac{2}{3}$，${\sigma }_A^1(3,B)=\frac{1}{3}$

​ f)多次迭代，直至达到纳什平衡

核心代码实现：

class KuhnTrainer:    """    P = pass    B = bet     payoff table:     P   P       higher player +1    P   B   P   player2 +1    P   B   B   higher player +2    B   P       player1 +1    B   B       higher player +2    """     def __init__(self):        self.node_map: Dict[str, Node] = {}     def train(self, iterations):        """        Train Kuhn poker        :param iterations:        :return:        """        cards = [1, 2, 3]        util = 0        for i in range(iterations):            # shuffle cards            self.shuffle_cards(cards)            cur_util = self.cfr(cards, "", 1, 1)            util += cur_util        print("Average game value: ", util / iterations)        for k, v in self.node_map.items():            print(v)     def shuffle_cards(self, cards):        random.shuffle(cards)     def cfr(self, cards, history: str, p0, p1):        """        Counterfactual regret minimization iteration         P   P       higher player +1        P   B   P   player2 +1        P   B   B   higher player +2        B   P       player1 +1        B   B       higher player +2         :param cards:        :param history:        :param p0:        :param p1:        :return:        """        plays = len(history)        player = plays % 2        opponent = 1 - player         # Return payoff for terminal states        if plays > 1:            terminal_pass = history[plays - 1] == 'p'            double_bet = history[plays - 2: plays] == 'bb'            is_player_card_higher = cards[player] > cards[opponent]            if terminal_pass:                if history == 'pp':                    return 1 if is_player_card_higher else -1                else:                    return 1            elif double_bet:                return 2 if is_player_card_higher else -2         info_set = str(cards[player]) + history         # Get information set node or create it if nonexistant        node = self.node_map.get(info_set, None)        if node is None:            node = Node()            node.info_set = info_set            self.node_map[info_set] = node         # For each action, recursively call cfr with additional history and probability        strategy = node.get_strategy(p0 if player == 0 else p1)        util = [0] * NUM_ACTIONS        node_util = 0        for i in range(NUM_ACTIONS):            next_history = history + ("p" if i == 0 else "b")            util[i] = -self.cfr(cards, next_history, p0 * strategy[i], p1) if player == 0 else \                -self.cfr(cards, next_history, p0, p1 * strategy[i])             node_util += strategy[i] * util[i]         # For each action, compute and accumulate counterfactual regret        for i in range(NUM_ACTIONS):            regret = util[i] - node_util            node.regret_sum[i] += regret * (p1 if player == 0 else p0)         return node_util

实验结果：

<div align='center'>图 6·库恩扑克，玩家和对手策略</div>

3.引申

CFR 算法出现时就已经能够解决德州扑克，但面对 52 张底牌、加注、过牌、河牌等复杂多变的情况使得德扑的博弈树无论是深度还是广度都十分的庞大，对计算资源和储存资源上的开销过于巨大，使得仅仅靠 CFR 算法攻克德扑十分困难。而 CFR 后续的研究者们都在费尽心力优化 CFR 算法的效率，致力于提高计算速度和压缩存储空间。在此，笔者简单介绍几种 CFR 变种算法，仅做了解。

3.1 CFR+：

与 CFR 算法不同的是，CFR+算法对累计平均策略做折减，对迭代的策略进行平均时，给近期迭代的策略赋予更高的权重；直观上，越到后期，策略表现越好，因此在都策略做平均时，给近期策略更高的权重更有助于收敛。

在 CFR+算法中，counterfactual utility 被定义为以下形式：

在的基础上，CFR+算法定义了一个$regretlikevalue$，此时 CFR+算法中的$regret$为一个累加值，而 CFR 算法定义$Regret$的为平均值，因此 CFR+算法中的 regret 计算方式为：

另外，在 CFR+算法中，最后输出的平均策略为一下形式：

3.2 MCCFR：

MCCFR（Monte Carlo Counterfactual Regret Minimization)是蒙特卡洛算法和 CFR 算法的结合，其核心在于：在避免每轮迭代整棵博弈树的同时，依然能够保证 $immediatecounterfactualregret$ 的期望值保持不变。将叶子节点分割为不同的$block：Q=Q_1,Q_2,...,Q_n$，且保证覆盖所有的叶子结点。

定义$Q_j$是在当前迭代中选择$Q_i$的概率：${\Sigma }_{j=1}^r{Q}_j=1$。

定义$Q(z)$表示在当前迭代中采样到叶子节点的概率：$Q(z)={\Sigma }_{j:z\in Q_j}{Q}_j$

那么在选择$Q_j$迭代时，得到的采样虚拟值为：$v_i(\sigma ,I/j)={\Sigma }_{z\in Q_j}\cap Z_i\frac{1}{Q(z)}{u}_i(z){\pi }_{-i}^{\sigma }(z[I],z)$

通过一定的概率选择不同的 block,得到一个基于采样的 CFR 算法。

3.3 结语

除了上述介绍的两个算法外，CFR 算法的优化数不胜数，有提高计算速度的 Discount-CFR、Warm Start、Total RBP，也有压缩存储空间的 CFR-D、Continue-Resolving、Safe and Nested Subgame Solving 等。

机器博弈是人工智能领域的重要研究方向。非完备信息博弈是机器博弈的子领域。非完备信息博弈中存在隐藏信息和信息不对称的特点,和完备信息博弈相比,非完备信息博弈更加贴近现实生活中。例如,竞标、拍卖、股票交易等现实问题中都存在隐藏信息和信息不对称。因此,研究非完备信息博弈问题更有现实意义。德州扑克博弈包含了隐藏信息、信息不对称和随机事件等重要特性,它是典型的非完备信息博弈。对其的研究具有非常重大的意义，感兴趣的读者可深入了解。

4.参考文献

[1] Brown, N., Kroer, C. and Sandholm, T.: Dynamic Thresholding and Pruning for Regret Minimization, AAAI Conference on Artificial Intelligence (2017).

[2] Lanctot, M., Waugh, K., Zinkevich, M. and Bowling, M.: Monte Carlo Sampling for Regret Minimization in Extensive Games, Advances in Neural Information Processing Systems 22 (Bengio, Y., Schuurmans, D., Lafferty, J. D., Williams, C. K. I. and Culotta, A., eds.), Curran Associates, Inc., pp. 1078–1086 (2009).

[3] Gibson, R. 2014. Regret Minimization in Games and the Development of Champion Multiplayer Computer PokerPlaying Agents. Ph.D. Dissertation, University of Alberta. Gilpin, A., and Sandholm, T. 2007. Lossless abstraction of imperfect information games. Journal of the ACM 54(5).

我们是行者 AI，我们在“AI＋游戏”中不断前行。

618 期间产品套餐推出活动，前往公众号 【行者 AI】，和我们一起探讨技术问题吧！