← 返回洞察文章
Solver 算法12 分鐘閱讀

為什麼 solver 把 6♣️ 和 6♦️ 當同一張牌?拆解 board isomorphism

打開一個 solve 準備要選 turn 的牌,理論上要對 49 張可能 turn 卡分別跑一棵子遊戲樹。但現代 solver 真正做的事情是:先把這 49 張卡分組,每組只算一張代表,剩下的直接共用結果。完成這件事的工程主角,叫做 isomorphism (同構)。

iso 是 solver 裡少數同時兼具「嚴格數學等價」與「巨大計算節省」的優化。它不是近似,不是 bucketing 那種 lossy 抽象,而是真正的對稱性壓縮。看懂 iso 的運作,會讓你對「solver 怎麼把無限的撲克空間變成可計算的維度」有更具體的畫面。

撲克的花色為什麼可以等價交換?

花色本身沒有絕對意義。如果你把整副牌的所有 ♠️ 改寫成 ♥️、所有 ♦️ 改寫成 ♣️,沒有任何遊戲屬性會改變。同花機率不變、equity 不變、blocker 結構不變,連發牌機率都對稱。這個性質的數學名字叫 suit symmetry:撲克遊戲在花色 permutation 下不變。

但這個對稱不是「永遠成立」,而是「在當前狀態下成立」。當 board 還是空的,4 個花色完全對稱;當你固定研究一個已經有 Q♠️ 的 parent state,♠️ 就被「指紋化」了,在這個局面裡不能任意跟 ♣️、♦️ 互換。換句話說,每張新發出來的牌都會打破一部分對稱性。以 Q♠️T♠️7♥️ 為例,6♣️ 和 6♦️ 彼此等價;但一旦代表局面選成 6♣️,接下來 river 階段的 ♣️ / ♦️ 對稱性又會改變,必須用四張 board 重新分組。iso 要做的,就是在每個 chance node 重新計算「當前局面下,剩下哪些花色 permutation 還是等價的」。

iso 不是近似,是嚴格等價。把 ♣️ 全部換成 ♦️、♦️ 全部換成 ♣️,撲克的同花機率、equity、blocker 結構完全沒變。solver 利用的就是這個對稱性。

iso 解的是什麼問題?

turn solve 在每張 turn 卡之後都要跑一棵子遊戲樹。如果只看公共牌,flop 後還有 49 張可能 turn;turn 發出後還有 48 張可能 river,也就是 49 × 48 = 2,352 個有序 (turn, river) runout。如果這些子遊戲樹真的都要從頭算,現代 solver 在合理時間內根本跑不完一個 spot。

iso 的觀察是:很多 turn 卡之間,「對遊戲樹來說」根本是同一回事。例如在 Q♠️T♠️7♥️ 上,只要沒有已知手牌、dead cards 或花色不對稱的 range 權重打破 ♣️ / ♦️ 對稱,發 6♣️ 還是發 6♦️,剩下的遊戲在花色重命名後完全等價,因為 ♣️ 和 ♦️ 在 board 上都是空集合。solver 算完 6♣️ 的代表子遊戲樹後,把策略與 EV 透過 ♣️↔♦️ 的映射還原給 6♦️,不需要重算。

  • iso 不會略過「真正不同」的牌面:Q♠️T♠️7♥️ 加 6♣️ 跟加 6♠️ 仍然要分別算,因為 ♠️ 已被指紋化,無法跟 ♣️ 互換。
  • iso 只折掉「真的等價」的局面:♣️ 跟 ♦️ 在這個 board 是對稱的,加 6♣️ 跟 6♦️ 是同一棵樹。
  • iso 是 lossless 的:壓縮後的解原封不動可以還原回每一張具體 turn card 的策略。

算法核心:board canonical signature

iso 的計算核心是 board canonical signature。把 (board + 新卡) 這 n+1n+1 張卡轉成「花色 permutation 不變」的 hash,相同 signature 的兩張新卡屬於同一個 iso class。整個流程是三步:

  1. 列出 4 個花色在這組卡裡的 rank multiset,例如 ♠️ = {Q, T}、♥️ = {7}、♣️ = {}、♦️ = {}。
  2. 在 4 個花色的 24 種 permutation π\pi 中,找出讓 (rank-multiset, ...) 字典序最小的那個。
  3. 套用 π\pi 重新命名花色,把結果 hash 成一個 64-bit 整數,這就是 canonical signature。
sig(B)=h ⁣(minπS4π(B))\mathrm{sig}(B) = h\!\left( \min_{\pi \in S_4} \pi(B) \right)

其中 S4S_4 是 4 個花色的對稱群,π(B)\pi(B) 表示對 board BB 套用 permutation π\pihh 是 hash 函數。同一個 iso class 的所有 board,最小化後得到同一個代表,所以 hash 結果一樣。

用 C++ 看一遍 iso 分組

PokerAlpha 把上面三步落到實作,核心 loop 大概就是這個樣子:

C++ · iso_group_candidates
std::unordered_map<uint64_t, std::vector<int>> groups;
for (int c : candidates) {
    extended[n_board] = c;
    uint64_t sig = board_canonical_signature(extended.data(), n_board + 1);
    groups[sig].push_back(c);
}

邏輯非常乾淨:對每個候選 turn card cc,把它放進 board 後算出 (board + c) 的 canonical signature,sig 相同的歸同一類。每類取最小 card int 當代表,solver 只算這個代表的子遊戲樹;其他卡在輸出時透過對應的花色 permutation 映射回去。

來看 GTO Wizard 的策略

理論講完,看一個直接的證據。在 GTO Wizard 的 100bb HU cEV game 上,同一個 Q♠️T♠️7♥️ flop check-check 後,把 turn 換成 6♣️ 或 6♦️,聚合策略矩陣除了 turn 牌面圖示外一致;在 combo level,6♣️ 的策略透過 ♣️↔♦️ 映射後會對齊 6♦️。

TURN 6♣️
GTO Wizard 100bb HU cEV,Q♠️T♠️7♥️ flop x-x、turn 6♣️ 的策略矩陣
TURN 6♦️
GTO Wizard 100bb HU cEV,Q♠️T♠️7♥️ flop x-x、turn 6♦️ 的策略矩陣
兩張圖的策略矩陣區塊一致,差別只在右上角 turn 牌圖示。這不是巧合,是 iso 把 6♣️ 和 6♦️ 視為同一個 class、透過花色映射共用一棵子遊戲樹的直接結果。

iso 什麼時候不能用?

iso 的前提是「對稱性還在」。一旦你的研究目標需要區分原本對稱的東西,iso 就要重新計算對稱群,否則會算錯導致策略會被剝削。

  • 考慮持有的手牌:如果你算的是「玩家 A 持有 A♠️K♠️」的策略,♠️ 已經被手牌指紋化,board 上的 ♠️ 跟其他花色不再對稱。iso 要把手牌的花色一起放進 signature。
  • Multi-flush board:當 board 已經是 monotone 或 two-tone 時,iso 對「未發出的花色」可以更激進地壓縮;但對「已在牌面上開出的花色」就完全不能 collapse。

正確使用 iso 的關鍵,是把 signature 的輸入定義對。signature 不只看 board,還要看「決策當下,對局面有實質影響的所有資訊」:已知手牌、dead cards、range 裡同一 rank 不同花色的權重、bunching / card-removal 資訊,以及任何會讓某個花色資訊被揭露的情況。

對玩家的真正意義是什麼?

對拿著 solver 學打牌的玩家來說,iso 解釋了一件你大概早就觀察到的現象:在 Q♠️T♠️7♥️ 上,只要沒有額外 blocker 或 range 權重打破 ♣️ / ♦️ 對稱,solver 給你的 6♣️ 策略跟 6♦️ 策略會在花色映射後完全一致。這不是「solver 偷懶」也不是「策略類別簡化」,而是這兩個局面在數學上嚴格等價,沒有任何 EV 差異。

這個觀察可以反過來幫助你的記憶與決策。學完一個 board 的 turn 策略時,你不需要記 49 張卡的反應,記 (board, iso class) 對應的策略就好。實戰上看到 turn 落 6♣️ 還是 6♦️,反應一致。看到 turn 落 6♠️ 跟 6♥️ 時要分別處理,因為它們會和 flop 上已有花色互動,數學上不是同一個 iso class。

參考文獻

  1. [1]Libratus: The Superhuman AI for No-Limit Poker - Brown & Sandholm, IJCAI 2017介紹 Libratus 在 NL poker 中的 abstraction、nested subgame solving 與 self-improvement 工程框架,涵蓋 lossless 與 lossy 抽象的區隔
  2. [2]postflop-solver (b-inary) - Open-source Rust postflop solver使用 Discounted CFR 的開源 postflop solver,README 明確記錄了 isomorphic chances 的實作 (例如 monotone flop 上未發出的三個花色互為 isomorphic)
  3. [3]TexasSolver (bupticybee) - Open-source Texas Holdem solver另一個受歡迎的開源德州撲克 solver 專案,提供 flop / turn solving 與多平台支援,可作為理解 solver 工程實作的對照
  4. [4]Cepheus (poker bot) - WikipediaCepheus 弱解 heads-up limit Texas hold'em 的歷史背景,由 University of Alberta CPRG 在 2015 年發表
  5. [5]What is a Solver in Poker? - Upswing Poker從玩家視角解釋 solver 是什麼、它在解什麼、為什麼解的是「片段」而不是完整的 NLHE

想實際體驗 AI 撲克分析?

Download on the App StoreGet it on Google Play