公平組合遊戲
經典的公平組合遊戲有很多，包括取數遊戲，31 點，以及 Nim 遊戲等。
Nim 遊戲
\(n\) 堆物品，每堆有 \(a_i\) 個，兩個玩家輪流取走任意一堆的任意個物品，但不能不取。
取走最後一個物品的人獲勝。
例如，如果現在有 \(n=3\) 堆物品，而每堆分別有 \(2, 5, 4\) 個，那麼可以取走第 \(1\) 堆中的 \(2\) 個物品，局面就變成了 \(0, 5, 4\)；或者也可以取走第 \(2\) 堆的 \(4\) 個物品，局面就變成了 \(2, 1, 4\)。
如果現在的局面為 \(0, 0, 5\)，甲取走了第 \(3\) 堆的 \(5\) 個物品，也就是取走了最後一個物品，此時甲獲勝。
博弈圖和狀態
如果將每個狀態視為一個節點，再從每個狀態向它的後繼狀態連邊，我們就可以得到一個博弈狀態圖。
例如，如果節點 \((i, j, k)\) 表示局面為 \(i, j, k\) 時的狀態，則我們可以畫出下面的博弈圖（由於篇幅有限，故僅顯示部分狀態節點和部分邊）：
定義 必勝狀態 為 先手必勝的狀態，必敗狀態 為 先手必敗的狀態。
通過推理，我們可以得出下面三條定理：
- 定理 1：沒有後繼狀態的狀態是必敗狀態。
- 定理 2：一個狀態是必勝狀態當且僅當存在至少一個必敗狀態為它的後繼狀態。
- 定理 3：一個狀態是必敗狀態當且僅當它的所有後繼狀態均為必勝狀態。
對於定理 1，如果遊戲進行不下去了，那麼這個玩家就輸掉了遊戲。
對於定理 2，如果該狀態至少有一個後繼狀態為必敗狀態，那麼玩家可以通過操作到該必敗狀態；此時對手的狀態為必敗狀態——對手必定是失敗的，而相反地，自己就獲得了勝利。
對於定理 3，如果不存在一個後繼狀態為必敗狀態，那麼無論如何，玩家只能操作到必勝狀態；此時對手的狀態為必勝狀態——對手必定是勝利的，自己就輸掉了遊戲。
如果博弈圖是一個有向無環圖，則通過這三個定理，我們可以在繪出博弈圖的情況下用 \(O(N+M)\) 的時間（其中 \(N\) 為狀態種數，\(M\) 為邊數）得出每個狀態是必勝狀態還是必敗狀態。
Nim 和
讓我們再次回顧 Nim 遊戲。
通過繪畫博弈圖，我們可以在 \(O(\prod_{i=1}^n a_i)\) 的時間裏求出該局面是否先手必贏。
但是，這樣的時間複雜度實在太高。有沒有什麼巧妙而快速的方法呢？
定義 Nim 和 \(=a_1 \oplus a_2 \oplus \ldots \oplus a_n\)。
當且僅當 Nim 和為 \(0\) 時，該狀態為必敗狀態；否則該狀態為必勝狀態。
證明
為什麼異或值會和狀態的勝負有關？下面給出了這個定理的證明過程。
為了證明該定理，只需要證明下面三個定理：
- 定理 1：沒有後繼狀態的狀態是必敗狀態。
- 定理 2：對於 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0\) 的局面，一定存在某種移動使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
- 定理 3：對於 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\) 的局面，一定不存在某種移動使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
對於定理 1，沒有後繼狀態的狀態只有一個，即全 \(0\) 局面。此時 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
對於定理 2，不妨假設 \(a_1 \oplus a_2 \oplus \ldots a_n = k \neq 0\)。如果我們要將 \(a_i\) 改為 \(a_i'\)，則 \(a_i'=a_i \oplus k\)。
假設 \(k\) 的二進制最高位 \(1\) 為 \(d\)，即 \(2^d \le k < 2^{d + 1}\)。根據異或定義，一定有奇數個 \(a_i\) 的二進制第 \(d\) 位為 1。滿足這個條件的 \(a_i\) 一定也滿足 \(a_i > a_i \oplus k\)，因而這也是個合法的移動。
對於定理 3，如果我們要將 \(a_i\) 改為 \(a_i'\)，則根據異或運算律可以得出 \(a_i=a_i'\)，因而這不是個合法的移動。
有向圖遊戲與 SG 函數
有向圖遊戲是一個經典的博弈遊戲——實際上，大部分的公平組合遊戲都可以轉換為有向圖遊戲。
在一個有向無環圖中，只有一個起點，上面有一個棋子，兩個玩家輪流沿着有向邊推動棋子，不能走的玩家判負。
定義 \(\operatorname{mex}\) 函數的值為不屬於集合 \(S\) 中的最小非負整數，即：
例如 \(\operatorname{mex}(\{0, 2, 4\})=1\)，\(\operatorname{mex}(\{1, 2\})=0\)。
對於狀態 \(x\) 和它的所有 \(k\) 個後繼狀態 \(y_1, y_2, \ldots, y_k\)，定義 \(\operatorname{SG}\) 函數：
而對於由 \(n\) 個有向圖遊戲組成的組合遊戲，設它們的起點分別為 \(s_1, s_2, \ldots, s_n\)，則有定理：當且僅當 \(\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n) \neq 0\) 時，這個遊戲是先手必勝的。同時，這是這一個組合遊戲的遊戲狀態 \(x\) 的 SG 值。
這一定理被稱作 Sprague–Grundy 定理(Sprague–Grundy Theorem), 簡稱 SG 定理。
SG 定理的證明
可以使用數學歸納法來證明。
我們假設對於遊戲狀態 \(x'\)，其當前節點 \(s_1', s_2', \ldots, s_n'\)（對於任意 \(i\) 有 \(s_i' < s_i\)），皆滿足 SG 定理。
顯然當 \(\operatorname{SG}(s_1)'=\operatorname{SG}(s_2)'=\ldots \operatorname{SG}(s_n)'=0\) 時，該狀態能滿足 SG 定理。
那麼只需要證明對於遊戲狀態 \(x\)，其當前節點 \(s_1', s_2', \ldots, s_n'\) 符合 SG 定理，SG 定理便成立。
事實上這一個狀態可以看作一個 Nim 遊戲，對於某個節點 \(s_i\)，它可以移動到任意一個 \(\operatorname{SG}\) 值比它小或比它大的節點。
在有向圖遊戲中，當一方將某一節點 \(s_i\) 移動到 \(\operatorname{SG}\) 值比它大的節點時，另一方可以移動回和 \(\operatorname{SG}\) 值和 \(\operatorname{SG}(s_i)\) 一樣的節點，所以向 SG 值較大節點移動是無效操作。
當移動到 SG 值較小的節點時，情況則會和 Nim 遊戲一樣，能夠到達任何一個遊戲狀態 \(x'\) 使得 \(\operatorname{SG}(x')= \operatorname{SG}(s_1') \oplus \operatorname{SG}(s_2') \oplus \ldots \oplus \operatorname{SG}(s_n') < \operatorname{SG}(X)\)（注意到前文已經假設 \(x'\) 滿足 SG 定理），但到達不了 SG 值為 \(\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n)\) 的節點。
所以狀態 \(x\) 符合 SG 定理。
SG 定理的應用
SG 定理適用於 任何公平的兩人遊戲, 它常被用於決定遊戲的輸贏結果。
計算給定狀態的 Grundy 值的步驟一般包括：
-
獲取從此狀態所有可能的轉換；
-
每個轉換都可以導致 一系列獨立的博弈（退化情況下只有一個）。計算每個獨立博弈的 Grundy 值並對它們進行 異或求和。
-
在為每個轉換計算了 Grundy 值之後，狀態的值是這些數字的 \(\operatorname{mex}\)。
-
如果該值為零，則當前狀態為輸，否則為贏。
將 Nim 遊戲轉換為有向圖遊戲
我們可以將一個有 \(x\) 個物品的堆視為節點 \(x\)，則當且僅當 \(y<x\) 時，節點 \(x\) 可以到達 \(y\)。
那麼，由 \(n\) 個堆組成的 Nim 遊戲，就可以視為 \(n\) 個有向圖遊戲了。
根據上面的推論，可以得出 \(\operatorname{SG}(x)=x\)。再根據 SG 定理，就可以得出 Nim 和的結論了。
參考文獻
（轉載）Nim 遊戲博弈（收集完全版）- exponent - 博客園
[組合遊戲與博弈論]【學習筆記】- Candy? - 博客園
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：cutekibry, woruo27, tinjyu
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用