CFR(Counterfactual Regret Minimization) 演算法簡介

發表於 分類於 文章字數： 5.8k

參考作者在Quora上的解釋

Introduction

self-learning algorithm

  • learns strategy by repeatedly playing against itself
  • initialized with uniformly random
    • playing every action at every decision point with equal probability
  • play actions with probability proportional to their positive regret(regret matching)
  • it will converge to optimal strategy that can do no worse than tie against any opponent

Implementation

  • Summing total regret for each action at each decision point

    • regret: how much better if just always played this one action at this decision, instead of previous choices?
      • Positive regret means that we would have done better if we had taken that action more often
      • Negative regret means that we would have done better by not taking that action at all
      • 愈多regret，代表此選項要多選
    • do actions with probabilities proportional to their positive regret
    • after each game, update regret values

  • Counter-intuitively, sequence of strategies does not necessarily converge to anything useful

    • But it now does so in practice
    • in a two-player zero-sum game, if you compute the average strategy over those billions of strategies in the sequence, then that average strategy will converge towards Nash equilibrium of the game

Nash equilibrium(納許均衡)

  • Do no worse than tie against any other strategy
  • Plays perfect defence
    • Just wins when the opponent makes mistakes
      • since attempting to find and exploit an opponent's mistakes usually makes it possible for an even smarter opponent to exploit your new strategy
  • exploitability(利用度)
    • maximum expectation that a perfect counter-strategy could win
    • exploitability = 0 when Nash equilibrium
    • CFR can make average strategy's exploitability converges towards zero

Result

  • best poker programs started beating the world's best human players in heads-up limit hold'em in 2008, even though there were still massively exploitable by this worst-case measure
  • In January 2015, we've essentially weakly solved the game
    • a strategy with such a low exploitability (0.000986 big blinds per game)
      • have 95% statistical confidence that they were actually winning against everyone

Algorithm Implementation

Regret Matching

單一決策點的核心只有兩行：把負 regret 砍成 0，剩下的正 regret 正規化成機率。

$$\sigma^{T+1}(I, a) = \begin{cases}
\dfrac{R^{T,+}(I,a)}{\sum_{a'} R^{T,+}(I,a')} & \text{if } \sum_{a'} R^{T,+}(I,a') > 0 \[6pt]
\dfrac{1}{|A(I)|} & \text{otherwise (退回均勻分布)}
\end{cases}$$

其中 $R^{T,+} = \max(R^T, 0)$，$I$ 是 information set(玩家看得到的資訊，含自己的牌和公開動作)。

Counterfactual Value

「Counterfactual」的意思是：假設我一定會走到這個決策點，那這裡的期望收益是多少？
所以要把「我自己為了走到這裡所付出的機率」除掉，只留對手和機運的機率：

$$v_i(\sigma, I) = \sum_{z \in Z_I} \pi^{\sigma}_{-i}(z[I]) \cdot \pi^{\sigma}(z[I] \to z) \cdot u_i(z)$$

  • $Z_I$：經過 $I$ 的所有終局
  • $\pi_{-i}$：除了 i 以外所有人(含機運)走到這裡的機率 — 這就是 counterfactual 的來源
  • 除掉自己的機率是關鍵：否則自己很少走的分支永遠得不到有意義的更新

Regret 累積與平均策略

$$R^T(I,a) = \sum_{t=1}^{T} \Big( v_i(\sigma^t_{I \to a}, I) - v_i(\sigma^t, I) \Big)$$

$$\bar{\sigma}^T(I,a) = \frac{\sum_{t=1}^{T} \pi^{\sigma^t}i(I), \sigma^t(I,a)}{\sum{t=1}^{T} \pi^{\sigma^t}_i(I)}$$

⚠ 收斂到 Nash 的是平均策略 $\bar{\sigma}$，不是最後一輪的 $\sigma^T$。
單輪策略序列本身可能一直震盪不收斂，這正是前面 Implementation 那節說的 counter-intuitive。

走訪流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cfr(history h, player i, reach_prob π_1, π_2):
    if h is terminal:  return u_i(h)
    if h is chance:    return Σ_a P(a) · cfr(h·a, i, π_1, π_2)

    I = information_set(h)
    σ = regret_matching(R[I])

    for a in A(I):                       # 先遞迴取得每個動作的 counterfactual value
        v[a] = cfr(h·a, i, π_1 · (σ[a] if player(h)==1 else 1),
                            π_2 · (σ[a] if player(h)==2 else 1))
    v_node = Σ_a σ[a] · v[a]

    if player(h) == i:                   # 只更新輪到自己的節點
        π_self, π_opp = (π_1, π_2) if i == 1 else (π_2, π_1)
        for a in A(I):
            R[I][a] += π_opp  · (v[a] - v_node)     # 用對手的到達機率當權重
            S[I][a] += π_self · σ[a]                # 累積平均策略
    return v_node
  • 每次 iteration 對每個玩家各跑一次(i = 1, i = 2)
  • 每輪走完整棵樹是 $O(|H|)$，這也是為什麼大型遊戲需要 abstraction 或 MCCFR

Example Code

用剪刀石頭布當最小可執行範例。RPS 只有一個 information set(沒有資訊可分)，
所以不需要遞迴，剛好能把 regret matching 單獨看清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import random

ACTIONS = 3                      # 0=rock 1=paper 2=scissors
regret_sum   = [0.0] * ACTIONS   # 累積 regret
strategy_sum = [0.0] * ACTIONS   # 累積策略，最後要平均

def get_strategy():
    """regret matching: 機率和正 regret 成正比"""
    pos = [max(r, 0.0) for r in regret_sum]
    total = sum(pos)
    if total > 0:
        return [p / total for p in pos]
    return [1.0 / ACTIONS] * ACTIONS      # 全非正時退回均勻分布

def payoff(a, b):
    """a 對 b 的收益：贏 1、平 0、輸 -1"""
    if a == b:
        return 0
    return 1 if (a - b) % ACTIONS == 1 else -1

def step(opp_strategy):
    strategy = get_strategy()
    for i in range(ACTIONS):
        strategy_sum[i] += strategy[i]

    my_action  = random.choices(range(ACTIONS), weights=strategy)[0]
    opp_action = random.choices(range(ACTIONS), weights=opp_strategy)[0]

    # counterfactual: 「如果當初每次都選 i」對上這個對手動作，會比實際好多少
    actual = payoff(my_action, opp_action)
    for i in range(ACTIONS):
        regret_sum[i] += payoff(i, opp_action) - actual

def average_strategy():
    total = sum(strategy_sum)
    if total <= 0:
        return [1.0 / ACTIONS] * ACTIONS
    return [s / total for s in strategy_sum]

兩種收斂結果

對手固定時，CFR 收斂到剝削對手的 best response：

1
2
3
4
5
random.seed(0)
for _ in range(100000):
    step([0.4, 0.3, 0.3])            # 對手偏好出石頭
print([round(x, 3) for x in average_strategy()])
# [0.0, 0.999, 0.0]  → 幾乎全出紙

兩邊都在學(self-play)才會收斂到 Nash：

1
2
3
4
5
6
7
8
9
10
11
for _ in range(200000):
    s = get_strategy()
    for i in range(ACTIONS):
        strategy_sum[i] += s[i]
    a = random.choices(range(ACTIONS), weights=s)[0]
    b = random.choices(range(ACTIONS), weights=s)[0]
    actual = payoff(a, b)
    for i in range(ACTIONS):
        regret_sum[i] += payoff(i, b) - actual
print([round(x, 3) for x in average_strategy()])
# [0.335, 0.334, 0.332]  → 收斂到 (1/3, 1/3, 1/3)

這兩個結果的對比就是 Nash 那節在講的事：Nash 是「不會被剝削」，不是「最大化獲利」。
想贏得多就要偏離 Nash 去剝削對手，代價是自己也變得可被剝削。

Summary

變形

演算法 差異 效果
CFR 原版，每輪走完整棵樹 $O(1/\sqrt{T})$ 收斂，樹大就跑不動
CFR+ regret 每輪截斷為非負，並改用加權平均策略 實測快一個數量級，2015 解出 limit hold'em 靠它
MCCFR 抽樣部份分支(outcome/external sampling)而非走完整棵樹 單輪成本大降，換取較高變異
Deep CFR 用神經網路取代 regret 表 不必先做 abstraction，可處理更大的遊戲

之後的發展

本文寫於 2015 年，停在 heads-up limit hold'em 被 weakly solved。後續：

  • 2017 Libratus(CMU)：擊敗 no-limit 一對一的頂尖人類職業選手
    • 關鍵是 nested subgame solving — 對局中即時重解子賽局，而非只查預先算好的策略表
  • 2019 Pluribus(CMU/Meta)：六人桌 no-limit 擊敗職業選手
    • 多人局理論上不保證 Nash(納許均衡在超過兩人的情況下沒有「不會輸」的保證)，但實務上仍有效
    • 訓練成本反而遠低於 Libratus，靠的是 depth-limited search

心得

  • CFR 的價值不在「打敗人類」，而在它把不完全資訊下的均衡求解變成可計算的問題
    • 對比 alpha-beta / MCTS 這些完全資訊的方法，最大的差別是要處理「對手不知道我知道什麼」
  • 兩個最容易搞錯的點
    1. 收斂的是平均策略，不是最終策略
    2. counterfactual 要除掉自己的到達機率，留對手的
  • Nash 是防守解。想贏更多必須偏離它去剝削對手，而這同時讓自己變得可被剝削 — 這個 trade-off 是整個 CFR 系列的哲學核心

參考資料

  • (CFR)Regret Minimization in Games with Incomplete Information
  • (CFR+)Solving Large Imperfect Information Games Using CFR+
  • (CFR)Explanation of CFR by inventor himself
  • poker AI news
  • poker AI news2
  • (Implementation)openCFR