OI-wiki 零和博弈全解從序貫 Minimax 到同時博弈的混合策略與線性規(guī)劃求解【免費下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki零和博弈zero-sum game是博弈論與算法競賽的交叉核心兩名玩家的收益之和恒為零一方的收益必然是另一方的損失。本文以 OI-wiki 的 零和博弈文檔 為骨架系統(tǒng)講解序貫零和游戲的 Minimax 遞推與實戰(zhàn)優(yōu)化、同時零和游戲的收益矩陣與混合策略并完整推導 von Neumann 極小化極大定理及其向線性規(guī)劃的轉化。讀完本文你將掌握用動態(tài)規(guī)劃、記憶化搜索、Alpha–Beta 剪枝解決序貫博弈題以及用線性規(guī)劃求解一般同時零和博弈最優(yōu)混合策略的完整方法論。前置知識零和博弈在博弈論中的定位在 OI-wiki 的博弈論體系中博弈論簡介 定義了基礎概念框架零和博弈zero-sum game指無論各方采取何種行為所有參與者的收益總和始終為零的博弈通常討論的二人零和博弈中一方的收益必然是另一方的損失。與之相對的是非零和博弈含正和、負和博弈。零和游戲可以視為常和游戲的特殊情形——任何常和游戲都可以通過對某一方的收益整體加上或減去一個常數(shù)等價地轉化為零和游戲因此僅需要討論零和游戲即可覆蓋更廣的問題。同時博弈按行動方式可分為同時博弈simultaneous game如剪刀石頭布與序貫博弈sequential game玩家依次行動、后行動者能觀察到部分先行動者的行為。本文討論的二人零和游戲在算法競賽中大致對應這兩類序貫零和游戲與同時零和游戲。前者用博弈樹刻畫、以 Minimax 思想求解后者用收益矩陣刻畫、以混合策略和線性規(guī)劃求解。序貫零和游戲Minimax 遞推收益函數(shù)的遞歸結構序貫零和游戲中兩名玩家輪流行動直到游戲終止收益函數(shù)呈現(xiàn)遞歸結構。游戲局面 $S$ 可分為三類終止局面 $S_0$、玩家 $1$ 行動的局面 $S_1$、玩家 $2$ 行動的局面 $S_2$。假設終止局面 $s\in S_0$ 處玩家 $1$ 的收益為 $v(s)$則玩家 $2$ 的收益為 $-v(s)$——輪到玩家 $2$ 行動時最大化自身收益等價于最小化玩家 $1$ 的收益。由此假設雙方都采取最優(yōu)策略玩家 $1$ 在局面 $s\in S$ 處能獲得的最大收益 $V(s)$ 滿足如下遞推$$ V(s) \begin{cases} v(s), s \in S_0,\ \max_{t\in s} V(t), s\in S_1,\ \min_{t\in s} V(t), s\in S_2. \end{cases} $$其中 $t\in s$ 表示 $t$ 是 $s$ 的后繼局面。這正是 Minimax 算法極小化極大思想 的核心——在搜索樹中我方MAX節(jié)點取子節(jié)點分數(shù)最大值對方MIN節(jié)點取子節(jié)點分數(shù)最小值回溯得到根節(jié)點在雙方最優(yōu)策略下的分數(shù)。四個實戰(zhàn)方法論將這一算法應用于實際問題根據(jù)局面規(guī)模與結構有四種典型方法局面數(shù)量較少直接暴力實現(xiàn)該遞推即可。局面數(shù)量龐大且無特殊結構考慮 Alpha–Beta 剪枝 并結合其他搜索剪枝算法。Alpha–Beta 剪枝維護 $\alpha$我方分數(shù)下界與 $\beta$對方分數(shù)上界兩個變量當 $\alpha\ge\beta$ 時剪掉當前節(jié)點剩余分支從而在不改變搜索結果的前提下大幅減少搜索量。單個局面頻繁作為多個局面的后繼為避免重復搜索采用記憶化搜索或其他動態(tài)規(guī)劃算法將每個局面的 $V(s)$ 只計算一次。收益是全程行動的收益和可以優(yōu)化建模方式。設到達終局 $s\in S_0$ 時玩家 $i1,2$ 的行動序列分別為 ${a^{(i)}j}{j1}^{k_i}$行動 $a$ 對應收益 $w(a)$玩家 $1$ 的收益函數(shù)為$$ v(s) \sum_{j1}^{k_1}w(a_j^{(1)}) - \sum_{j1}^{k_2}w(a_j^{(2)}). $$此時可以設 $\tilde V(s)$ 為當前玩家在局面 $s\in S$ 之后的游戲中能取得的最大分數(shù)不再固定以玩家 $1$ 為收益主體而是站在輪到誰行動的視角。對于初始狀態(tài) $s_0$ 有 $V(s_0)\tilde V(s_0)$因此求 $\tilde V(\cdot)$ 足以求解原問題。$\tilde V(\cdot)$ 滿足更簡潔的遞推$$ \tilde V(s) \begin{cases} 0, s \in S_0, \ \max_{t\in s} w(a_{s\to t}) - \tilde V(t), s\in S_1\cup S_2. \end{cases} $$其中 $a_{s\to t}$ 表示能使狀態(tài)從 $s$ 轉移到 $t$ 的行動若有多個這樣的行動取收益 $w(a)$ 最高的那個。這一當前玩家視角的建模在取石子、棋盤博弈類題目中極為常用。與公平組合游戲的聯(lián)系公平組合游戲都是序貫零和游戲只需設勝利方收益 $1$、失敗方收益 $-1$。此時 $V(\cdot)$ 的遞推關系正是 公平組合博弈 中判定必勝狀態(tài)$\mathcal N$ 態(tài)和必敗狀態(tài)$\mathcal P$ 態(tài)的引理——沒有后繼狀態(tài)的狀態(tài)是必敗狀態(tài)一個狀態(tài)必勝當且僅當存在至少一個必敗后繼一個狀態(tài)必敗當且僅當所有后繼均為必勝。這從零和博弈的角度統(tǒng)一了 Sprague–Grundy 理論 所依賴的必勝/必敗判定基礎。這類問題還有一個常見變形求勝利方最少需要的回合數(shù)、失敗方最多能堅持的回合數(shù)。技巧在于從終止狀態(tài)開始做 BFS 并按引理判定必勝/必敗狀態(tài)時記錄判定各狀態(tài)勝負時 BFS 進行的輪次數(shù)即為所求回合數(shù)。原因在于判定為必勝狀態(tài)只需要一個必敗后繼它總是由后繼狀態(tài)中輪次數(shù)最小的必敗狀態(tài)轉移而來判定為必敗狀態(tài)需要所有后繼均為必勝它總是由后繼狀態(tài)中輪次數(shù)最大的必勝狀態(tài)轉移而來。這一方法同樣可以推廣到一般的有向圖游戲。例題精講Codeforces 794 E. Choosing Carrot設有一個長度為 $n$ 的數(shù)列 ${a_i}$。兩名玩家輪流從數(shù)列兩端取走一個數(shù)直到數(shù)列僅剩最后一個數(shù)字。玩家 $1$ 的目標是最大化這個最后剩下的數(shù)字玩家 $2$ 的目標是最小化它。游戲開始前玩家 $1$ 還可先進行 $k$ 次行動。對每個 $k0,1,\dots,n-1$求雙方最優(yōu)策略下最后剩下的數(shù)字。數(shù)據(jù)范圍 $1\le n\le 3\times10^5$。分析無論雙方如何取數(shù)剩余部分總是一段完整區(qū)間 $[l,r]$局面可由區(qū)間和當前行動玩家 $i1,2$ 描述。設 $f(l,r,i)$ 為局面 $(l,r,i)$ 下游戲最后剩下的數(shù)字當 $lr$ 時滿足$$ \begin{aligned} f(l,r,1) \max{f(l1,r,2),f(l,r-1,2)},\ f(l,r,2) \min{f(l1,r,1),f(l,r-1,1)}. \end{aligned} $$終值條件 $f(l,l,1)f(l,l,2)a_l$。樸素區(qū)間 DP 為 $\Theta(n^2)$無法通過原題數(shù)據(jù)范圍需要優(yōu)化。優(yōu)化思路將轉移看作對數(shù)列整體操作兩個轉移方程分別對應將相鄰數(shù)字取最大值/最小值得到新數(shù)列稱為「最大化操作」和「最小化操作」每次操作使數(shù)列長度減一。長度為 $d$ 的區(qū)間對應結果共 $(n-d1)$ 個等價于對序列做 $(d-1)$ 次操作得到的序列且 $f(l,r,1)$ 要求最后一次操作是最大化操作?？疾爝B續(xù)兩次操作的效果先做最小化再做最大化數(shù)列 $a_1,a_2,a_3$ 變?yōu)?$ \max{\min{a_1,a_2},\min{a_2,a_3}}. $$枚舉三者大小關系可知除 $a_2$ 為嚴格極大值的情形外該式恒等于 $a_2$。也就是說若數(shù)列不存在嚴格極大值點連續(xù)兩次操作的效果就是刪去數(shù)列首尾各一個數(shù)字。而只要對序列做一次最大化操作就能保證不存在嚴格極大值點。因此所有偶數(shù)次操作的結果可通過對初始數(shù)列做兩次操作得到的序列逐對刪去首尾數(shù)字得到所有奇數(shù)次操作的結果可通過做一次操作得到的序列逐對刪去首尾數(shù)字得到。完整操作至多只需 $3$ 次統(tǒng)計答案只需 $2$ 次遍歷總復雜度降為 $\Theta(n)$。倉庫中的參考代碼位于 docs/math/code/zero-sum-game/zero-sum-game-1.cpp核心實現(xiàn)如下#include algorithm #include iostream #include vector int main() { int n; std::cin n; std::vectorint a(n); for (int x : a) std::cin x; std::vectorint ans(n), tmp; tmp a; for (int i 0; i n - 1; i) { tmp[i] std::max(tmp[i], tmp[i 1]); } for (int l n / 2 - 1, r (n - 1) / 2, ma 0; l 0; --l, r) { ma std::max({ma, tmp[l], tmp[r]}); ans[r - l] ma; } tmp a; for (int i 0; i n - 1; i) { tmp[i] std::min(tmp[i], tmp[i 1]); } for (int i 0; i n - 2; i) { tmp[i] std::max(tmp[i], tmp[i 1]); } for (int l (n - 3) / 2, r n / 2 - 1, ma 0; l 0; --l, r) { ma std::max({ma, tmp[l], tmp[r]}); ans[r - l] ma; } ans[n - 1] *std::max_element(a.begin(), a.end()); for (auto x : ans) std::cout x ; std::cout std::endl; return 0; }代碼結構印證了上文優(yōu)化第一段用一次最大化操作后的序列逐對刪去首尾處理偶數(shù)長度區(qū)間第二段用最小化最大化兩次操作后的序列處理奇數(shù)長度區(qū)間ans[n-1]對應整段數(shù)列的最終值。倉庫中還提供了對應測試數(shù)據(jù) zero-sum-game-1.in輸入4與數(shù)列1 2 3 5及期望輸出 zero-sum-game-1.ans3 3 5 5可直接運行驗證。序貫零和游戲習題Luogu P2734 USACO3.3 游戲 A GameLuogu P4576 CQOI2013 棋盤游戲Luogu P7097 yLOI2020 牽絲戲Codeforces 388 C. Fox and Card GameCodeforces 794 E. Choosing CarrotCodeforces 1628 D2. Game on Sum (Hard Version)Luogu P3210 HNOI2010 取石頭游戲同時零和游戲收益矩陣表示同時零和博弈中兩名玩家同時行動通常用收益矩陣表示。設玩家 $i1,2$ 的行動集合為 $A_i$當雙方分別采取行動 $a_i\in A_i$ 時收益分別為 $v(a_1,a_2)$ 和 $-v(a_1,a_2)$。以石頭剪刀布為例勝利得 $1$ 分、失敗得 $-1$ 分、平局得 $0$ 分收益表為$$ \begin{pmatrix} 0,0 1,-1 -1,1 \ -1,1 0,0 1,-1 \ 1,-1 -1,1 0,0 \end{pmatrix}. $$一般的二人同時游戲都可表示為類似形式故也稱雙矩陣游戲bimatrix game。對零和博弈玩家 $1$ 與玩家 $2$ 的收益矩陣互為相反數(shù)因此只需考慮玩家 $1$ 的收益矩陣$$ V (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2} \begin{pmatrix} 0 1 -1 \ -1 0 1 \ 1 -1 0 \end{pmatrix}. $$要解決的問題是給定收益矩陣 $V$如何求出兩名玩家的最優(yōu)策略和最大收益為什么純策略分析不夠序貫視角的局限既然已經(jīng)解決了序貫零和游戲一個自然的想法是把同時游戲看成它的序貫版本。若假定玩家 $1$ 先行動、玩家 $2$ 后行動那么游戲結束時玩家 $1$ 的收益由$$ w_-\max_{a_1\in A_1}\min_{a_2\in A_2} v(a_1,a_2) $$給出——玩家 $1$ 的行動對玩家 $2$ 單向透明這是玩家 $1$ 能獲得的最差結果。對稱地若玩家 $2$ 先行動玩家 $1$ 的收益為$$ w_ \min_{a_2\in A_2}\max_{a_1\in A_1} v(a_1,a_2) $$——這是玩家 $1$ 能獲得的最好結果。玩家 $1$ 應期待實際收益 $w\in[w_-,w_]$。盡管不等式 $w_-\le w_$ 總是成立證明參見 線性規(guī)劃的對偶原理但等號未必成立因此僅采用序貫分析無法唯一確定同時游戲的結果。石頭剪刀布中如果出手有先后先手必輸、后手必贏對應 $w_--1\le1w_$恰為等號不成立的例子。上述分析遺漏了同時游戲的關鍵因素玩家無法準確預測對手的行動這意味著雙方可以采取隨機策略。這一想法在序貫博弈中不成立——無論先手如何隨機后手總能觀測到具體行動并有針對性地回應但在同時游戲中隨機策略引入的戰(zhàn)略模糊使對手無法有效針對。仍以石頭剪刀布為例若玩家 $1$ 均勻隨機地選擇剪刀、石頭、布則按玩家 $2$ 的不同行動玩家 $1$ 的期望收益為$$ \dfrac{1}{3}(0,1,-1)^T \dfrac{1}{3}(-1,0,1)^T \dfrac{1}{3}(1,-1,0)^T (0,0,0)^T, $$無論玩家 $2$ 如何行動期望收益恒為 $0$顯然優(yōu)于確定性選擇單個行動?；旌喜呗杂纱艘牖旌喜呗詍ixed strategy概念同時游戲中玩家 $i$ 的混合策略是指函數(shù) $s_i:A_i\to[0,1]$且滿足 $\sum_{a_i\in A_i}s_i(a_i)1$——即行動集合 $A_i$ 上的一個概率分布。玩家 $i$ 全體混合策略的集合記作 $S_i\Delta(A_i)$。若 $s_i$ 是退化的概率分布存在 $a\in A_i$ 使 $s_i(a)1$則稱其為純策略pure strategy。混合策略的收益就是各行動收益的期望$$ v(s_1,s_2) \sum_{a_1\in A_1}\sum_{a_2\in A_2}s_1(a_1)s_2(a_2)v(a_1,a_2). $$將單個行動看作對應的純策略行動集合 $A_i$ 就嵌入到策略集合 $S_i$ 中上式將 $v(a_1,a_2)$ 從 $A_1\times A_2$ 延拓到 $S_1\times S_2$ 上。von Neumann 定理極小化極大與極大化極小的統(tǒng)一引入混合策略后極大化極小思想與極小化極大思想得到的結果一致同時零和游戲的結果被唯一確定。這就是經(jīng)典的 von Neumann 定理定理von Neumann允許混合策略的同時零和游戲中若雙方都采取最優(yōu)策略玩家 $1$ 的最大收益為$$ w \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2) \min_{s_2\in S_2}\max_{s_1\in S_1} v(s_1,s_2), $$玩家 $2$ 的最大收益為 $-w$。證明要點原文給出了完整推導設 $w \max_{s_1}\min_{s_2}v(s_1,s_2)$。由 $v(s_1,s_2)\sum_{a_2}s_2(a_2)v(s_1,a_2)$ 可知內層最小化問題的最優(yōu)解可由純策略達到即 $w\max_{s_1\in S_1}\min_{a_2\in A_2}v(s_1,a_2)$。引入輔助變量 $u$ 后改寫為約束優(yōu)化問題并結合混合策略的定義與收益函數(shù)表達式等價于線性規(guī)劃問題 (P)$$ (P) \qquad \begin{aligned} w \max_{u,s_1}; u\ \text{subject to } \sum_{a_1\in A_1}s_1(a_1)v(a_1,a_2) \ge u,~\forall a_2\in A_2,\ \sum_{a_1\in A_1}s_1(a_1) 1,\ s_1(a_1) \ge 0,~\forall a_1\in A_1. \end{aligned} $$該問題可行且有最優(yōu)解。根據(jù) 對偶原理其最優(yōu)解等于對偶問題 (D) 的最優(yōu)解$$ (D) \qquad \begin{aligned} w \min_{t,s_2}; t\ \text{subject to }\sum_{a_2\in A_2}s_2(a_2)v(a_1,a_2) \le t,~\forall a_1\in A_1,\ \sum_{a_2\in A_2}s_2(a_2) 1,\ s_2(a_2)\ge 0,~\forall a_2\in A_2. \end{aligned} $$重復前述步驟(D) 等價于 $\min_{s_2}\max_{s_1}v(s_1,s_2)$定理得證。這一結果正是該游戲的Nash 均衡假定雙方都選擇均衡中的最優(yōu)策略沒有任何玩家能從偏離均衡策略中嚴格獲益。轉化為線性規(guī)劃具體求解方法von Neumann 定理的證明同時指出了求解方法。設 $n$、$m$ 分別為玩家 $1$、$2$ 的可行動作數(shù)目給定玩家 $1$ 的收益矩陣 $V\in\mathbf R^{n\times m}$求解如下線性規(guī)劃$$ \begin{aligned} w \max_{(u,s)\in\mathbf R\times\mathbf R^n}; u\ \text{subject to } V^Ts \ge u\mathbf 1,\ \mathbf 1^Ts 1,\ s \ge 0. \end{aligned} $$這是一個規(guī)模為 $\Theta(nm)$ 的線性規(guī)劃問題可用 單純形法 高效求解。算法得到的最優(yōu)解 $s$ 就是玩家 $1$ 的最優(yōu)混合策略玩家 $2$ 的最優(yōu)策略只需從單純形表中獲得該問題最優(yōu)解的**對偶變量影子價格**即可。實操要點收益矩陣 $V$ 的每一行對應玩家 $1$ 的一個行動、每一列對應玩家 $2$ 的一個行動約束 $V^Ts\ge u\mathbf 1$ 保證無論玩家 $2$ 怎么選玩家 $1$ 的期望收益都不低于 $u$$\mathbf 1^Ts1$ 與 $s\ge 0$ 保證 $s$ 是概率分布。若 $V$ 中存在負數(shù)元素需按線性規(guī)劃慣例平移矩陣保證變量非負約束的可行性配合對偶問題的影子價格讀取玩家 $2$ 的策略。同時零和游戲習題Luogu P4232 無意識之外的捉迷藏參考資料與注釋原文依據(jù)均為倉庫內文檔博弈論簡介零和/非零和博弈、同時/序貫博弈、完美/完全信息等基礎概念公平組合博弈必勝/必敗狀態(tài)引理、有向圖游戲與 BFS 輪次判定Minimax 算法與 Alpha–Beta 剪枝序貫零和博弈的搜索理論基礎線性規(guī)劃對偶原理與線性規(guī)劃問題的形式化單純形法線性規(guī)劃的高效求解算法零和博弈參考代碼 及 測試數(shù)據(jù)、期望輸出外部學術背景原文引用的文獻主題Zero-sum game 與 Minimax theorem 的數(shù)學定義可參見維基百科對應條目雙矩陣游戲bimatrix game與 Nash 均衡的概念可參見博弈論標準教材?！久赓M下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內含炫酷算術魔法項目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考