一、Fibonacci 博弈#
描述#
基本的斐波那契博弈（Fibonacci Game）描述如下：
有一堆石子，兩個頂尖聰明的人玩遊戲，先取者可以取走任意多個，但不能全取完，之後每次可以取的石子數至少為 1，至多為對手剛取的石子數的 2 倍。約定取走最後一個石子的人為贏家，求必敗態。
結論#
當且僅當總石子數為斐波那契數時，先手必敗。
证明#
证明如下，轉自大佬证明
用到了 Zeckendorf 定理（齊肯多夫定理）：任何正整數可以表示為若干個不連續的 Fibonacci 數之和。
二、Bash 博弈#
描述#
基本的巴什博弈（Bash Game）描述如下：
有一堆 n 個物品，兩人輪流取走物品，每次至少取一個，最多取 m 個，最後取光者獲勝。
結論#
若 n % (m+1) == 0，則先手必敗
bool FirstWin(int n, int m) { //先手必勝返回true
return n % (m+1) != 0;
}
证明#
博弈過程如下：证明
這裡簡單說說
同餘定理：若 n%(m+1) = r, 若先取者拿走 r 個，後者無論拿走 1~m 任意個，先手都可以再拿走若干個湊夠（m+1）個，則先手必赢。反之先手必敗。當 n<m 時，先手可以一次取完，也是必勝
巴什博弈變形#
有一堆 n 個物品，兩人輪流取走物品，每次至少取 p 個，最多取 q 個，剩餘不足 p 個時一次取完，最後取光者勝利。
若 n%(p+q) = r, 則當 r != 0 && r < p 時先手必勝，反之先手必敗
三、Wythoff 博弈#
描述#
基本的威佐夫博弈（Wythoff Game）描述如下：
有兩堆各若干個物品，兩個人輪流從某一堆或同時從兩堆中取同樣多的物品，每次至少取一個，多者不限，最後取光者得勝。
結論#
設兩堆物品各有 a、b 個，求出 ab 的差值後乘以黃金分割比，看結果是否等於 ab 中的最小值，若等於則先手必敗
bool FirstWin(int a, int b) { //先手必勝返回true
double G = (sqrt(5.0)+1) / 2; //黃金分割比
int t = abs(a-b) * G;
return d != min(a,b);
}
证明#
证明較複雜… 暫存一下板子，這裡看证明
四、Nim 博弈#
描述#
基本的尼姆博弈（Nim Game）描述如下：
有若干堆各若干個物品，兩個人輪流從某一堆取任意多的物品，每次至少取一個，多者不限，最後取光者得勝。
結論#
將 N 堆物品數量全部異或後，若結果為 0 則先手必敗，否則先手必勝
bool FirstWin(int a, int b) { //先手必勝返回true
int ans = 0;
for(int i = 0; i < N; ++i) ans ^= a[i];//a[i]為物品數量
return ans != 0;
}
证明#
证明也很複雜… 這裡看证明
後面會介紹 SG 函數，一般將最終局面的 SG 值設為 0
SG 定理：遊戲的和的 SG 值是各個子遊戲的 SG 值的異或。
知道了以上結論，想到 Nim 遊戲實際上可以分為 n 個 Bash 遊戲，而 Bash 遊戲若可以無限取子，則以當前局面剩餘石子數為狀態，SG (x)=x。所以這個題目的答案即為各個堆石子數的異或值，若值為 0，先手必敗，否則先手總有方案使得下一局面異或值為 0，後手必敗。
變形#
參考博客Nim 博弈及其變形
反 Nim 博弈#
反尼姆博弈顧名思義，
有若干堆各若干個物品，兩個人輪流從某一堆取任意多的物品，每次至少取一個，多者不限，最後取光者失敗。
例題 E - Misere Nim
先手只有兩種情況必勝，1 是所有堆石子數全為 1，且異或和為 0，2 是有石子數不為 1 的堆，且異或和不為 0
五、SG 函數#
參考博客：SG 函數、組合遊戲 - SG 函數和 SG 定理
1. 概念介紹#
ICG 博弈遊戲（公平組合遊戲）#
條件如下： 題目描述一般為 A,B 兩人做遊戲
- A、B 交替進行操作
- 每操作一次，選手可以在合法操作集合中任選一種操作。
- 對於遊戲的任何一種可能的局面，合法的操作集合只取決於這個局面本身，不取決於其它因素（跟選手，以前的所有操作無關）
- 如果當前選手無法進行合法的操作，判負
以上面所提的巴什博弈做背景，有一堆 n 個物品，兩人輪流取走物品，每次至少取一個，最多取 m 個，最後取光者獲勝。
一個公平遊戲可以抽象地用一個有向無環圖來表示，這個圖中每個點都對應一個狀態，每條有向邊代表從一個狀態到另一個狀態的合法操作。
必勝態與必敗態#
- 必敗態（P-position）：上一个選手（即剛操作完的選手）處於必勝局面，此時誰面臨此狀態誰必敗。
- 必勝態（N-position）：下一个選手（即將操作的選手）處於必勝局面，此時誰面臨此狀態誰必勝。
性質：
- 所有的終結點都是必敗態
- 從任何必勝態操作，至少能有一種方式進入必敗態
- 無論如何操作， 從必敗態都只能進入必勝態
2.SG 函數#
定義 mex 運算#
先定義 mex (minimal excludant) 運算，這是施加於一個集合的運算，表示最小的不屬於這個集合的非負整數。
- 如 mex {2,3,5}=0、mex {0,1,2,4}=3、mex {}=0。
對於任意狀態 x，定義 SG (x)=mex (S)，其中S 是 x 後繼狀態的 SG 函數值的集合。如 x 有三個後繼狀態分別為 a、b、c，那麼 SG (x)=mex {SG (a), SG (b), SG (c)}。 這樣，集合 S 的終態必然是空集，所以當且僅當 x 為必敗點 P 時，SG 函數的終態為 SG (x)=0。
通過 SG 函數，每個 ICG 都可以轉換成 Nim 博弈。SG 函數的定義域為 ICG 的決策樹上的所有節點，此時具體定義為：SG (x)=mex {SG (y)|y 是 x 的節點}。對於 ICG 的決策樹上的節點 u，我們可以把它想象成一個只有一堆石子，個數為 SG (u) 的 Nim 博弈。SG 函數的求解方式我是通過這個博客理解的:組合遊戲 - SG 函數和 SG 定理。
取石子問題
有 1 堆 n 個的石子，每次只能取 {1, 3, 4} 個石子，先取完石子者勝利，那麼各個數的 SG 值為多少？
SG[0]=0，f[]={1,3,4},
- x=1 時，可以取走 1 - f {1} 個石子，剩餘 {0} 個，所以 SG [1] = mex { SG [0] }= mex {0} = 1;
- x=2 時，可以取走 2 - f {1} 個石子，剩餘 {1} 個，所以 SG [2] = mex { SG [1] }= mex {1} = 0;
- x=3 時，可以取走 3 - f {1,3} 個石子，剩餘 {2,0} 個，所以 SG [3] = mex {SG [2],SG [0]} = mex {0,0} =1;
- x=4 時，可以取走 4- f {1,3,4} 個石子，剩餘 {3,1,0} 個，所以 SG [4] = mex {SG [3],SG [1],SG [0]} = mex {1,1,0} = 2;
- x=5 時，可以取走 5 - f {1,3,4} 個石子，剩餘 {4,2,1} 個，所以 SG [5] = mex {SG [4],SG [2],SG [1]} =mex {2,0,1} = 3;
以此類推…
x = 0 1 2 3 4 5 6 7 8…
SG[x] = 0 1 0 1 2 3 2 0 1…
由上述實例我們就可以得到 SG 函數值求解步驟，那麼計算 1~n 的 SG 函數值步驟如下：
- 使用數組 f 將可改變當前狀態的方式記錄下來。
- 用另一個數組將當前狀態 x 的後繼狀態標記。
- 最後模擬 mex 運算，也就是我們在標記值中 搜索 未被標記值 的最小值，將其賦值給 SG (x)。
- 不斷的重複 2 - 3 的步驟，就完成了 計算 1~n 的函數值。
模板如下：
//f[N]:可改變當前狀態的方式，N為方式的種類，f[N]要在getSG之前先預處理
//SG[]:0~n的SG函數值
//S[]:為x後繼狀態的集合
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
int i,j;
memset(SG,0,sizeof(SG));
//因為SG[0]始終等於0，所以i從1開始
for(i = 1; i <= n; i++){
//每一次都要將上一狀態 的 後繼集合 重置
memset(S,0,sizeof(S));
for(j = 0; f[j] <= i && j <= N; j++)
S[SG[i-f[j]]] = 1; //將後繼狀態的SG函數值進行標記
for(j = 0;; j++) if(!S[j]){ //查詢當前後繼狀態SG值中最小的非零值
SG[i] = j;
break;
}
}
}
3.SG 定理#
- 遊戲和的 SG 函數是所有子遊戲的 SG 函數的異或和，其中所有子遊戲互相獨立。
- 所以當且僅當每堆石子的 SG 函數的異或和不為 0 時，先手必勝。
六、Green Hackenbush（樹上刪邊遊戲）#
做題第一題就被卡住了，搜了下題解發現是沒學過的 Green 博弈
參考博客：博弈 - Green Hackenbush，以下內容都是這裡面的
1.Hackenbush 遊戲概述#
Hackenbush 遊戲是通過移除一個有根圖的某些邊，直到沒有與地板的相連的邊。地板用虛線來表示，其中移除某一條邊的時候，那條邊以上所連著的所有邊都會移除，就像砍樹枝那樣，樹枝以上的部分也會被移除。在這裡，我們討論這個遊戲的公平版本，每個玩家在他的回合可以刪除任意的邊。這個版本叫做 Green Hackenbush，每條邊都是綠色的，下面我們簡稱 GH 遊戲。這裡還有一個不公平版本，叫做 Blue-Red Hackenbush，有些邊是藍色，有些邊是紅色，而玩家一只能刪除藍色邊，玩家二只能刪除紅色邊。總的來說，Hackenbush 遊戲，可能會有只供玩家一刪除的藍色邊，只供玩家二刪除的紅色邊，還有兩個玩家都可以進行操作的綠色邊。
2. 克朗原理（Colon Principle）#
對於樹上的某一個點，它的分支可以轉化成以這個點為根的一根竹子，這個竹子的長度就是它各個分支的邊的數量的異或和
所有邊權值為 1，則是裸的 green 博弈，每個點的 sg 函數 = 子節點的 sg 函數 + 1 的異或和。
權值不同时，當 AB 權值 = 1 時，sg [A]=sg [B]+1。
當 AB 權值為偶數時，sg [A]=sg [B]。
當 AB 權值為奇數時，sg [A]=sg [B]^1