在上一篇文章中，我们讲了经典的 CFR 算法的原理及实现。但是，它也有两个致命的缺陷，导致无法应用到实际的复杂博弈中：

• 它需要遍历整个游戏树

• 它需要知道对手的策略，这在实际情况下很难满足

本文将介绍基于 Monte Carlo 的改进算法。全部代码可以参考我的 github 项目：cfr-kuhn.

1 Monte Carlo CFR

核心思想是，在避免遍历整个游戏树的前提下，每个 information set 的每个 action 的 counterfactual regret 期望值保持不变。

令 是所有 terminal node 的子集，其中的每一个元素 我们称为 block，每个 block 可能包含多个 terminal node 。令 是选择 的概率，满足 。每次迭代，我们都会从这些 blocks 中采样一个并且只考虑在该 block 中的 terminal node 。

回忆 CFR 经典版的 counterfactual value 计算公式：

在 MCCFR 中，对于 block 的 sampled counterfactual value 可以表示为：

其中：

• 是 terminal node
• 表示 information set 可以到达的 的全集
• 表示某个可以到达 的 information set
• 表示玩家 id
• 表示 block id
• 表示 所在 block 被选中的概率之和（一个 terminal node 可以被分到多个 block 中）

我们可以证明 counterfactual value 和 sampled counterfactual value 期望是相等的。

这就是 MCCFR 的基本思想了。事实上，CFR 可以看作 MCCFR 在 且 的特例。

此外，我们可以将每一个 block 选为 chance node 的一个分支。以 Kuhn Poker 为例，我们对于手牌 1，2，3 可以建立 3 个 block： ，分别包含手牌为 1，2，3 的所有 terminal nodes。从而，每个 block 的概率也自然为 。这就是 chance-sampled CFR。

1.1 Outcome-Sampling MCCFR

在 outcome-sampling MCCFR 中，我们把每个 terminal node 作为一个 block。每次迭代，我们抽取一个 terminal node 并更新它的前缀 information set。一个 terminal node 出现概率越高，我们采样概率也越高。因此我们必须得到每个 terminal node j 出现的概率作为 。如何得到呢？

在 CFR 中，我们在计算 regret 的时候，会计算到达每个 history 的概率。对于 terminal node j，这个概率其实就是采样概率 。

CFR 算法包含了两个方向的遍历：

• 前向遍历。用于计算每个玩家从原点到达当前 history 的概率
• 后向遍历。用于计算每个玩家从当前 history 进行到 terminal node 的概率 ，在此过程中，还会计算 sampled counterfactual regrets。

后向遍历中计算 sampled counterfactual regrets 会分为两种情况。

其一是选择了能通向当前 terminal node 的 action。即，在information set 采取了行动 ，此时计算方式为：

上式比较难以理解的是：

结合定义， 是从 到达 的概率，相比 多前进了一步（选择行动 ），在 选择 的概率是 ，因此，如果从 到 的概率为 ，由于 将选择 的概率由原本的 变成了 1.0，它到 的概率就变成了 。

另一种情况是选择了其他行动，此时 不是 的前缀。此时的 sampled counterfactual value 是：

选取 0 是因为该动作的后悔值更新不归 管。必然有别的 terminal node 的前缀是 ，当采样到这些 terminal node 的时候自然会更新。

我们令：

由于在 outcome sampling 中，每个 terminal node 都对应一个 block ，因此 就是选中 的概率。理论上，为了保证采样的真实性，这个概率应该与所有玩家遵循策略 进行游戏到达 的概率相同，即

根据定义， 是对手到达 的概率，在计算时，假设玩家 以 1.0 的概率选择动作，而 相反。两者的乘积就是从局外旁观者看来到达 的概率。因此有：

带入得到：

注意在这个表达式中，我们不再需要对手的信息 （只有带下标 的部分了）。我们在化简中刻意消去了对手 相关的信息。

每次迭代累计后悔值会增加：

这样计算可以保证累计后悔值的期望是与传统 cfr 相同的。

每次迭代，每个动作的累计 strategy 增加：

注：论文中还增加了 权重，即本次 iteration 和上次访问 的 iteration 之差，但是我加上权重后无法得到正确结果，尚需进一步研究。

1.2 实现细节

相比 cfr，mccfr 的不同主要有：

1. 无需对手（-i）的信息
2. 无需遍历所有行动
3. 计算后悔值的方法不同，需要增加一个基于采样概率的权重。
4. 需要引入 epsilon 保证探索所有 action

    fn mccfr(
        &mut self,
        history: kuhn::ActionHistory,
        cards: &Vec<i32>,
        reach_probs: HashMap<i32, f64>,
    ) -> f64 {
        // current active player
        let player_id = (history.0.len() % 2) as i32;
        let opponent_id = 1 - player_id;

        let maybe_payoff = kuhn::get_payoff(&history, cards);
        if maybe_payoff.is_some() {
            let payoff = match player_id {
                0 => maybe_payoff.unwrap(),
                1 => -maybe_payoff.unwrap(),
                _ => panic!("unexpected player id {}", player_id),
            };
            return payoff as f64;
        }

        // not the terminal node
        let info_set = InformationSet {
            action_history: history.clone(),
            hand_card: cards[player_id as usize],
        };

        if self.cfr_info.contains_key(&info_set) == false {
            self.cfr_info.insert(info_set.clone(), CfrNode::new(0.06));
        }

        let action_probs = self
            .cfr_info
            .get(&info_set)
            .unwrap()
            .get_action_probability();

        let chosen_action_id = sample(&action_probs);
        let chosen_action = kuhn::Action::from_int(chosen_action_id);
        let chosen_action_prob = action_probs[chosen_action_id as usize];
        let mut next_history = history.clone();
        next_history.0.push(chosen_action);
        // modify reach prob for SELF (not opponent)
        // update history probability
        let mut next_reach_probs = reach_probs.clone();
        *next_reach_probs.get_mut(&player_id).unwrap() *= chosen_action_prob;
        // recursive call
        // final payoff of the terminal node
        let final_payoff = -self.mccfr(next_history, cards, next_reach_probs);

        // update regret value
        let node = self.cfr_info.get_mut(&info_set).unwrap();
        for (action_id, action_prob) in action_probs.iter().enumerate() {
            let action = kuhn::Action::from_int(action_id);
            // reach probability of SELF (not opponent)
            let weight = final_payoff / reach_probs[&player_id] / action_prob;
            if action == chosen_action {
                node.cum_regrets[action_id] += weight * (1.0 - action_prob);
            } else {
                node.cum_regrets[action_id] += -weight * action_prob;
            }
        }

        // update strategy
        for (action_id, action_prob) in action_probs.iter().enumerate() {
            node.cum_strategy[action_id] += action_prob * reach_probs[&player_id];
        }

        return final_payoff;
    }

1.3 结果

Explore with epsilon=0.06. Average payoff = -0.05138

We get 0.03 here because we choose epsilon = 0.06 and we have 2 actions to choose from.

Reference

1. Monte Carlo Counterfactual Regret Minimization
2. MCCFR technical report