Safe and Nested Subgame Solving for Imperfect-Information Games 深度解析

不完美資訊遊戲（Imperfect-Information Games）如撲克、談判、策略競賽等，因為玩家無法完整觀察對手的行動與持有資訊，導致策略求解難度遠大於完美資訊遊戲（如西洋棋、圍棋）。此論文《Safe and Nested Subgame Solving for Imperfect-Information Games》由 Michael Bowling 與 Noam Brown 於 NeurIPS 2017 發表，榮獲最佳論文獎，其核心在於提出一套「安全且可巢狀執行的子遊戲求解（subgame solving）方法」，成功克服不完美資訊遊戲中子遊戲求解的固有限制，並在理論及實務上都展現出大幅領先前人之效果，成為關鍵技術並推動了 AI 在德州撲克等領域達成人類頂尖水平的突破。

研究背景與動機

不完美資訊遊戲的挑戰在於各子遊戲（subgame）並非獨立，玩家的最優策略不僅取決於該子遊戲內的狀態，更與整個遊戲中未被觸及的其他子遊戲策略息息相關。這與完美資訊遊戲的子遊戲特性大不相同，後者子遊戲可獨立求解且構成整體策略的基石。傳統方法通常先對整體遊戲進行策略近似，之後再嘗試針對某些子遊戲局部優化，而這樣的「子遊戲求解」過程，若不考慮全局策略聯結，往往會導致不安全（可能被對手剝削）或無法改進的結果。

此外，不完美資訊遊戲中對手可能會執行訓練階段未涵蓋的行動（out-of-abstraction actions），若無適當因應機制，AI 會嚴重受挫。傳統對策「行動轉換（action translation）」雖有益處，但性能仍有限，難以有效應對真實遊戲時的多變環境。

因此，Brown 與 Sandholm 希望設計一套理論上保證安全（不會比原先策略更容易被剝削）、同時具備高度靈活性與擴展性的子遊戲求解方法，並且允許多次在遊戲樹向下推進過程中重複執行，從而逐步降低策略可被利用的弱點，達到實務可用且效能卓越的解決方案。

核心方法與創新

本論文提出的核心即為「安全子遊戲求解（Safe Subgame Solving）」技術，採取以下幾項關鍵策略：

• 回溯調整（Resolving with a Safety Margin）：在子遊戲求解過程中，不直接在子遊戲中利用近似全局策略，反而先計算該子遊戲的「保障價值（gadget value）」與對手可行反制的上限，確保新策略不會比先前整體策略更容易被剝削。
• 線性規劃保證策略安全：透過在子遊戲引入一種特殊的輔助策略與約束，確保子遊戲的策略改變不會降低整體遊戲中玩家的勝率下限，相當於保護了全局 Nash 均衡的穩定性。
• 巢狀子遊戲求解（Nested Subgame Solving）：允許在遊戲進行過程中，根據對手實際行動，動態且多階段地重複執行子遊戲求解。這種機制彌補了單次求解的策略缺陷，使AI能持續改進策略反應，顯著降低策略可被利用程度（exploitability）。
• 擴展至行動抽象外反應：改進之前的行動轉換方法，提出一套利用子遊戲求解同時處理遊戲抽象外行動的技術，能靈活應對對手未見過的新策略或行動，大幅提升了在真實遊戲環境下的適應性與性能。

整體方法體系從策略理論出發，引入嚴謹數學保證並兼顧實務架構，使本技術得以穩健地應用於複雜且信息不對稱的戰略遊戲求解中。

主要實驗結果

Brown 與 Sandholm 在德州撲克（heads-up no-limit Texas hold’em）等經典不完美資訊遊戲環境中完成系列實驗，驗證其方法的優勢。

• 實驗顯示，該安全子遊戲求解方法在理論上可以顯著降低策略剝削率（exploitability），遠勝過傳統子遊戲局部求解或直接行動轉換方法。
• 透過巢狀反覆求解，可以持續改善策略應對對手的不同胁迫策略，策略表現勝過一次性靜態求解，不僅降低了被剝削風險，也提升了贏率。
• 在面對超出既有策略抽象的行動（即未知策略），本方法因能動態求解子遊戲並安全更新策略，遠較過去行動轉換工具性能優異，表現更具韌性與適應性。
• 該論文提出的方法是成功驅動 Libratus 系統擊敗世界頂尖人類德州撲克玩家的核心算法部分，證明其在實際競技場上的強大實力與革命性貢獻。

對 AI 領域的深遠影響

此篇作品在多個層面推動了不完美資訊遊戲 AI 技術的革新：

• 理論突破：系統性解決了子遊戲求解中「策略非獨立性」的理論難題，提出安全且可重複執行的框架，從根基強化了不完美資訊遊戲策略求解的理論基礎。
• 實務指導：演算法的設計兼顧效率與安全，使其可用於真實世界龐大遊戲樹中，即使局面複雜依然能動態更新策略，提供後續研究與實務系統良好範本。
• 競技革命：作為 Libratus 系統的關鍵組成，成功打破長久以來 AI 在現金注德州撲克對戰中不能穩定擊敗人類專家的瓶頸，創造了 AI 在不完美資訊領域攻頂的新里程碑。
• 啟發後續研究：後續不完美資訊博弈研究中，子遊戲求解、反覆決策更新、以及策略擴展技術皆基於此篇核心框架進一步深化，使 AI 不僅能應對靜態抽象，更能面對動態複雜環境下的挑戰。

總結來說，Brown 與 Sandholm 的這項工作不僅在遊戲 AI 領域建立了新標竿，更拓展了 AI 在不完美資訊決策領域的理論與應用疆界，為智能代理（agent）設計、安全策略更新與動態適應性奠定了重要基礎，影響深遠且持續發酵。

---

論文資訊
📄 Safe and Nested Subgame Solving for Imperfect-Information Games
👥 Brown, Sandholm
🏆 NeurIPS 2017 · Best Paper
🔗 arxiv.org/abs/1705.02955