為什麼會想到用異或來算SG函數？它的本質是什麼？

01-08

下面是之前回高中講課的時候的講法梗概，個人覺得還湊合吧。

記法和一些其他的說明：

組合遊戲（下稱「遊戲」）全部用DAG來表示（應當是單源單匯的，即恰有一個入度為0的點和一個出度為0的點）。遊戲的全體記為 $GAME$ （是一個可數的集合），空的遊戲（只有一個頂點的DAG）用 $phi$ 表示。 $nim(k)$ 表示只有一堆 $k$ 個石子的nim遊戲。

$GAME$ 上有一個二元的 $+$ 運算，就是somehow把兩個遊戲的頂點集合的笛卡爾積作為新的頂點集合的通常的「遊戲的和」運算，你們懂的。由於DAG的表示可能牽涉頂點編號之類的問題，我們就不談論 $+$ 是否交換之類的事情了，這不太重要。

謂詞 $win(g)$ 表示遊戲 $g$ 是先手必勝的。定義關係 $T(x,y)$ 成立如果對任意的 $zin GAME$ 都有 $win(x+z)=win(y+z)$ 。容易驗證 $T$ 是 $GAME$ 上的一個等價關係，以下也記為 $x sim y$ 或者「 $x$ 和 $y$ 等價」。 $T$ 在 $GAME$ 上誘導出的等價類集合記為 $ar{GAME}$ ，根據 $T$ 的定義， $+$ 也能自然地誘導到 $ar{GAME}$ 上。你應驗證裝備了 $+$ 的 $ar{GAME}$ 為一abel群，其中：

$ar{phi}$ 是單位元

$ar{phi}$ 以外的元素都為2階

$i e j$ 則 $ar{nim(i)} e ar{nim(j)}$ （因此 $ar{GAME}$ 也是可數的）

容易證明 $ar{GAME}$ 同構於一列2階群的直和（每次取一個還不能被生成的元素加進生成元集即可），因此同構於裝備了xor運算的自然數。

之前的活看上去從一片黑暗中得到了xor運算。接下來我們還需要找一個具體並且好用的表示，終於需要干一些不能避免的臟活（僵硬的「驗證」而非「推倒」）了。你需要：證明 $ar{nim}$ 們能生成整個 $ar{GAME}$ 而不是它的一個真子群（對頂點數歸納，證明任意遊戲都等價於某個 $nim(k)$ ，驗證mex結論的正確性），並且證明把 $ar{nim(k)}$ 映到 $k$ 確實是同構。

最後一步驗證 $ar{nim(x)} + ar{nim(y)} = ar{nim(x oplus y)}$ 直接驗證 $mex(left{ a oplus x : a<y ight}cup left{ aoplus y : a<x ight} ) = x oplus y$ 有點無趣。一個好一點的方法是，可以不費力地驗證 $ar{nim(1)} + ar{nim(x)} = ar{nim(x oplus 1)}$ ，進而可以看到 $left{ ar{nim(2k)} ight}$ 同構於 $ar{GAME}$ ，然後容易證明 $left{ ar{nim(2^k)} ight}$ 是 $ar{GAME}$ 的一個極小生成元集。

以下內容全是個人的空想臆測，一時民科性子發作，僅供娛樂消遣。

考慮在一個單源拓撲圖 $G$ 上的博弈遊戲，初始狀態為源點 $S$ ，玩家輪流選擇當前狀態的一條出邊 $(u,v)$ 並將當前狀態變為 $v$ ，不能如此做的玩家輸。

這個遊戲的勝負判定是很簡單的，但是如果多個這樣的遊戲組合起來呢？

形式化的說，對於有向圖 $X,Y$ ，記 $Xcdot Y$ 為 $X$ 與 $Y$ 的笛卡爾積。

我們從這個遊戲的性質出發，我們用一個迷之函數f: DirectedGraph o ???來表示有向圖G上的遊戲的勝負狀態。

對於這個函數值定義一種複合運算 $f(X)oplus f(Y)=f(Xcdot Y)$ 。

規定，若 $G$ 上的遊戲先手必輸，則 $f(G)=0$ 。

於是顯然有 $f(G)oplus 0=f(G),f(G)oplus f(G)=0,f(X)oplus f(Y)=f(Y)oplus f(X),(f(X)oplus f(Y))oplus f(Z)=f(X)oplus (f(Y)oplus f(Z))$ 。

不難驗證這個函數值構成了一組線性空間，現在的首要任務是找到一組基。

我們希望找到一組儘可能簡單的有向圖 $G$ 的函數值 $f(G)$ 來作為基，為了考察 $f(X)$ 是否等於 $f(Y)$ ，我們考慮 $Xcdot Y$ 上的遊戲是否先手必敗。

不難發現，記刪除 $S$ 後，以 $S$ 的直接後繼們分別為源點形成的拓撲圖集合為 $T$ ， $forall tin T,f(G) eq f(t)$ ，這是由於在 $Gcdot t$ 的遊戲中先手只需從S走一步即可使遊戲變成 $f(tcdot t)=0$ 。

於是我們考慮一種無向圖 $B_n=(V,E)$ ，其中 $V={1,2,3,ldots n},E={(u,v)|(u>v)}$ ，希望 $0,f(B_1),f(B_2),ldots$ 能表示出所有的組合遊戲。

記 $sg(G)$ 為滿足 $f(G)=f(B_{sg(G)})$ 的整數。

這是可以的，考慮歸納法，記刪除 $S$ 後，以 $S$ 的直接後繼們分別為源點形成的拓撲圖集合為 $T$ ，假設 $sg(G)=n$ ，首先需要滿足， $forall tin T,sg(t) eq n$ ，其次需要滿足 $forall m<n,exists tin T, sg(t)=m$ ，也就意味著 $sg(G)=mex{{sg(t)|tin T}}$ ，

否則先手將 $B_n$ 走到 $B_{sg(G)}$ 的狀態時，我們就會無計可施。

很容易驗證 $sg(G)=mex{{sg(t)|tin T}}$ 時， $f(Gcdot B_{sg(G)})=0$ ，這裡不再贅述。

下面說的話有點精神錯亂。

我們現在已經找到了線性基的超集，現在試圖去尋找我們所要的線性基。

顯然 $k$ 個基可以組合出 $2^k$ 種可能的遊戲，如果這 $2^k$ 種可能的遊戲的sg值是 $[0,2^k)$ 就好了。那麼如果如此，我們就可以取 ${0}cup {f(B_{2^k})}$ 來做基了，那麼根據一個數的二進位表示，就可以得出所需要用的基。

於是令 $D_k=B_{2^k}$ ，我們的目的是證明這是一組線性基。

註：以下的二進位第k位均指二進位表示中從右向左數第k+1位。

先來考慮證明的目的，我們回到之前的線性空間，我們用一個二進位數來表示 $f(G)$ ，若 $f(G)=f(D_{i_1})oplus f(D_{i_2})oplus ldots oplus f(D_{i_k})$ （ $i_1,i_2,ldots ,i_k$ 互不相同），那麼 $f(G)=2^{i_1}+2^{i_2}+ldots 2^{i_k}$ ，不難驗證 $oplus$ 就是按位異或運算。同時在證明了之前的結論後，用歸納可以證明，若x的二進位表示中第i位為1，則B_x分解為基的表示中必有D_i，由此顯然有 $sg(G)=f(G)$ ，於是&之所以是異或就是在mod 2下的線性基的加法啦&。

回到證明，仍然考慮歸納。

假設 $0,f(D_0),ldots f(D_{k-1})$ 可以線性表出任意 $f(B_x),0leqslant x<2^k$ ，證明 $D_kcup{D_i|i<d}$ 可以線性表出任意 $2^kleqslant x<2^k+2^d$ 。