前言
在學校被問到賽局理論的東西，想起自己以前有學過sg函數這種東西，那時候覺得挺玄的，也沒認真推導跟思考，直接拿來用在題目上，感覺就像在玩「魔法」一樣。
現在有能力也有時間可以好好推導這個東西了。
一切起源自石頭
某一天，有兩個極度聰明的小孩在玩遊戲，有$n$堆石頭，每堆有$a_n$顆石頭，每回合可以從任意一堆拿走$k$顆石頭，若無法再拿走石頭即輸，問在兩方採最優策略下是先手勝(N)或是先手敗(P)?
sg函數推導
每次遇到這種問題時，都是同樣的模式，先討論$n=1, k=1$的情況:
根據剩餘的石頭數量，可以畫出有向圖，每點代表石頭剩餘數量:
左下數字代表剩餘石頭數量
可以知道當$a_1$是奇數時先手勝，反之。
而當$k=2$:
由上圖可知兩個規則:
- 只要可以轉移到的狀態中有P，此點為N
- 若只能轉移到N，此點為P
由上面的規則就可以從終點回推到起點，就知道起點是先手敗或是先手勝。
現在或許可以思考$n>1$的情形了，為了方便討論先固定$a_i = 1, i \in [1,n]$, $k=1$
$n=2$時，是先手敗(P)
$n=3$時，是先手勝(N)
$n=4$時，是先手敗(P)
…以此類推。
大膽做個猜想，若每堆的狀態N有奇數個，就是先手勝，若是偶數個，就是先手敗。
很可惜，這個想法在$a_i=1$時是對的；但是當$a_i$可以為2時可以找到反例:
上圖代表兩堆石頭($a_1 = 2, a_2 = 1$)各自的狀態圖
仔細觀察剛剛$a_i=1$的圖與$a_i=2$的差別，可以感覺的出來，他們有某種層級結構，不如就將$a_i=1$的圖命為: 一階 (1!)，而$a_i=2$則命為: 二階 (2!)。
特別的，若是P點則稱: 零階 (0!)
既然有一跟二了，那就會有三吧?
觀察二階圖形，他可以轉移到一階與零階，三階應當也有這種特性，可以轉移到零階，也可以轉移到一階、二階。
這種型態應該在$k=3$時才能出現，以此類推， $a$階只能在$k=a$時才會出現 。
並且可以得知「階」的另一個特性， $a$階可以轉移到$0$~$a-1$階 ，其中0階可以升階，只是後手可以把他再降回原階，等同於局面沒有變動。
注意這裡可以將「階」定義到一個點上，可以自行思考為什麼。
而現在又出現一個問題了:
當$k = 2$，
若$a_i=3$，他的階數為多少? 將$a_i=3$畫出來，是P點，應為零階
而$a_i=4$，是N點，但是他轉移的狀態不像剛剛定義的「階」，這代表剛剛的定義需要擴展，不如先停下來；討論剛剛階的性質。
先轉回來研究「階」組合起來的性質，若有兩堆石頭，為$a_1 = a, a_2 = b$，
$a = 0, b = 0$，是先手敗。(0! + 0! = P)
$a = 0, b = 1$，是先手勝。(0! + 1! = N)
$a = 0, b = 2$，是先手勝。(0! + 2! = N)
$a = 1, b = 1$，是先手敗。(1! + 1! = P)
$a = 1, b = 2$，是先手勝。(1! + 2! = N)
$a = 2, b = 2$，是先手敗。(2! + 2! = P)
觀察勝負的規律，當$a = b$是先手敗，其餘都是先手勝。
利用一點邏輯思考，當$a = b$，每當先手將其中一堆降階，後手總是可以將另一堆降為同一階，無論先手怎麼操作，狀態都會收斂到兩方皆為先手敗的狀態，導致先手敗。
而當$a \ne b, a > b$，先手總是可以將第一堆石頭降階，與第二堆同階，造成與剛剛相同的情況，但是是後手敗。
於是就驗證出了這個規則: 兩同階為P，兩異階為N
回過頭來思考$n=1, a_i=4, k=2$究竟該怎麼定義到階上。
記得泰勒展開式嗎? 雖然完全無關，但是其中有個思想似乎可以套用在這邊，若$f(x)=g(x)$，則$f^{(n)}(x)=g^{(n)}(x)$，只要兩者特性完全相同，就可以判定兩者相同。
稱 $a_i=4$ 為 $x$ 階，將其與0階組合看看，是N；與1階，是P；與2階，是N。
寫成數學式子:
$x! + 0! = N$
$x! + 1! = P$
$x! + 2! = N$
他與1階的特性完全相同，所以可以說它是1階。
這時「階」的定義已經被擴展了，我們可以用組合已知階，來判斷其為哪一階。
不過這樣的數學定義不太簡潔，似乎可以簡化? 再深入研究看看$a_i=4$；上面的數學式子其實可以展開:
$x! + 0! = N$
|-> $0! + 0! = P$(雖然看起來是先手敗，但其實是上一局的後手敗)
|-> $2! + 0! = N$
$x! + 1! = P$
|-> $0! + 1! = N$(雖然看起來是先手勝，但其實是上一局的後手勝)
|-> $2! + 1! = N$
$x! + 2! = N$
|-> $0! + 2! = N$
|-> $2! + 2! = P$(雖然看起來是先手勝，但其實是上一局的後手勝)
發現一個規則，只要展開後是全N，即為先手敗，同時此點也是這階，或許還沒有足夠的證據看出來規律，我們來討論$k=3$的$a_i=5$
$x! + 0! = N$
|-> $0! + 0! = P$
|-> $2! + 0! = N$
|-> $3! + 0! = N$
$x! + 1! = P$
|-> $0! + 1! = N$
|-> $2! + 1! = N$
|-> $3! + 1! = N$
…(下略)
若$x$與組合的階$y$為同階，結果為P，而結果為P就代表，$x$可以轉移的所有狀態必跟$y$不同階。
而因為可以轉移的狀態[0, 1, 2, 3]只會有一個缺失，可以確定這個缺失必與$y$同階，故寫出以下式子:
$sg(status) = mex(sg(nextStatus)|status \to nextStatus)$
其中$mex$為最小的未出現的非負整數。
這下我們有一個好用的數學式子，來幫助我們表達一個狀態的「階」。
此時可以輕易判斷當$n=1$、任意$a_1,k$是先手勝或是先手敗。
但$n>1$的情況又要如何判斷?
Nim-sum
剛剛的問題是，石頭可以從任意一堆拿$k$顆，現在改成可以從任意一堆拿任意顆，情況似乎變複雜了，但是實際上變簡單了。
設每堆石頭為$a_i$顆，而每堆其實就代表一局遊戲。
現在有$n$局: $a_1,a_2,a_3…,a_n$，而$a_i \oplus a_j$代表將第$i$局遊戲與第$j$局組合起來一起玩。
同時$a_i$也可以說是一種狀態，$\oplus$即是將兩種狀態組合成一種狀態。
直覺告訴我們，只要在每一局遊戲中都採取最佳策略，那就會贏下整場遊戲，因此$\oplus$滿足交換律，亦即先玩完第一場或先玩完第二場都沒差。
接著我們也知道$(a_i \oplus a_j) \oplus a_k = a_i \oplus (a_j \oplus a_k)$，因為把兩局遊戲組合後，就算是一局大遊戲，先玩完也不影響整體勝負。
以及其他直覺的結論 $a_i \oplus 0 = a_i$、若$a_i = a_j$, $a_i \oplus a_j = P = 0$
利用剛剛推導出來的sg函數，我們可以知道某個狀態的階，進而判斷是先手勝或是先手敗。
特別的，$n=1$時，$sg(a) = a$。
根據sg函數的定義寫出$sg(a_1 \oplus a_2 … \oplus a_n) = mex(sg(a_1 \oplus … \oplus a_i’ … \oplus a_n) | a_i \to a_i’)$，這樣子可以反推回去，決定是究竟是先手勝或是先手敗。
然而每局的狀態難以這樣一一列舉，為了簡化情況，我們先討論$n = 2$:
$sg(0 \oplus 0) = P = 0$
$sg(0 \oplus a) = sg(a) = a$
$sg(a \oplus b) = P = 0$, 如果$a = b$
$sg(a \oplus b) = N$, 如果$a \ne b$
看著這個運算規則，越看越像xor，做個猜想: 在$n$為任意正整數下，$\oplus$與xor是等價的。
為此我們必須證明兩者等價:
當$a_i = 0, i \in [1, n]$，是終盤，兩者定義符合。
當$a_1$ $xor$ $a_2$ $xor$ … $a_n=0$，無法將其中一個數字改變，且維持$xor$和為0；換句話說，當$xor$和為0，下一步只會讓$xor$和為非0。
這其實就是最上面提到的第二點規則: 若只能轉移到N，此點為P 。
證明這點很簡單，若將其中一數改成$a_i’$，而$xor$和變為$X$，
則$a_1$ $xor$ … $a_i’$… $a_n$ $=X=0$ $xor$ $a_i$ $xor$ $a_i’$，但是$a_i’<a_i$，故$X = 0$ $xor$ $a_i’$ $xor$ $a_i \ne 0$
得證。
當$a_1$ $xor$ $a_2$ $xor$ … $a_n = X \ne 0$，可以將其中一數改變，並使$xor$和為0。
這也對應到最上面第一點規則: 只要可以轉移到的狀態中有P，此點為N 。
若將$a_i$改成$a_i$ $xor$ $X$，則$xor$和為0。此時$a_i$ $xor$ $X$就是$a_i’$。
但是還必須證明$a_i’ < a_i$，假設$X$在二進位下最高位1是第$k$位，則必有某$a_i$滿足二進位下第$k$位為1，顯然，$a_i$ $xor$ $X$第$k$位為0，得證$a_i’ < a_i$。
現在我們可以非常迅速的計算一整個大遊戲的狀態了，因為$\oplus$與xor是等價，所以只要將$sg(a_1 \oplus a_2 … a_n)$裡面的值全部做xor運算即可。
必勝策略也顯而易見，先手只需要每次都使下一個狀態為0，即可獲勝。
回到最初的問題
回到一開始的問題，看似可以依剛才的結論，全部xor後判斷，但是實際上因為「無法任意改變數字」而存在錯誤，上面的證明有一步是將$a_i$變為$a_i$ $xor$ $X$，這代表$a_i$可能變成$0$ ~ $a_i-1$中任意一數，但是因為這個問題有拿走數的限制$k$，所以無法對所有狀態成立。
而一開始推導出來的「階」正好滿足此性質。($n$階可以轉移至$0$ ~ $n-1$階)
只要將一開始的每個狀態取sg()，就可以得知階數，最後再將全部xor起來，非0即為先手勝，0則為先手敗。
可能你會注意到0階接下來的轉移似乎有點問題，但是因為可以由後手轉移回0階，最終都會收斂至先手敗，所以對整體局面還是一樣。
結論
只要先依$k$構建一DAG，從終盤逆推回去找到sg值，再將所有局面的sg值xor起來，就可以判斷問題解答。
寫成數學式子: $sg(sg(a_1) \oplus sg(a_2) … \oplus sg(a_n)) = sg(a_1) \oplus sg(a_2) … \oplus sg(a_n)$。
結語
這次研究的題目真硬，雖然學過了但是還是試著從零開始推導，結果真的推導出同樣的結論，這種過程真的挺好玩的，就像是在創造新的結構一樣，可以發現許多以前不曾想過的東西。