博弈論之Nim游戲

? ? ? ?OI里，博弈論就是兩個聰明絕頂的人玩不公平的游戲。

? ? ? ? Nim游戲是組合游戲(Combinatorial Games)的一種，屬于“Impartial Combinatorial Games”（以下簡稱ICG）。

? ? ? ? 通常的Nim游戲的定義是這樣的：有若干堆石子，每堆石子的數量都是有限的，合法的移動是“選擇一堆石子并拿走若干顆（不能不拿）”，如果輪到某個人時所有的石子堆都已經被拿空了，則判負（因為他此刻沒有任何合法的移動）。

? ? ? ? 我們都知道，對于N堆石子，判斷第一個人是否贏是將每個石子進行異或運算，如果結果為0則第一個人取得必輸，否則必贏。

? ? ? ? 但主要是為什么用異或？為什么等于零則是先者必輸？

? ? ? ??首先先說一下大家都知道的定義吧：P-position和N-position。

? ? ? ??P-position：P即Previous，該局面為P-position，則代表著這個局面先行者必輸，后行者必贏。

? ? ? ? N-position：N即Next，該局面為N-position，則代表著這個局面的后行者必輸，先行者必贏。

? ? ? ? 很顯然，對于無法移動的局面（Terminal position）為P-position；可以移動到P-position局面的必為N-position局面（就是這個局面是先行者必輸的話，它的上一個局面一定是后行者必輸）；所有移動都導致N-position局面的是P-position。

? ? ? ? 也就是說，對于一個局面A是?P-position還是N-position，如果它的子局面（所謂子局面就是這個局面的能夠發展成的后續局面，比如兩個石子堆個數為（3,3），那么它的子局面為(0,3)(1,3)(2,3)）存在先者必輸P-position的局面，那么局面A就是后者必輸N-position的局面，如果它的子局面全部是后者必輸N-position的局面，那么局面A就是先者必輸P-position的局面（子局面的后者就是局面A的操作者）。

? ? ? ? 為此我們要判斷的就是一開始是屬于什么局面，根據上述定義可知這個局面的判定取決于它的子局面，而它的子局面又取決于它的子子局面……直到這個局面能夠獨立判斷是P-position還是N-position，然后再回溯判斷，對于這個遞歸的算法你可能已經敏銳地看到有大量重復的子問題了，需要記憶化搜索或DP，這實際上也就是博弈論的本質而已，只是我們存在一種比搜索更優的方法——異或。

? ? ? ? 為什么用異或呢？因為異或有一種我們需要的神奇的性質——消去律。

? ? ? ?1.對于Terminal?position只有一個，也就是全為0，結果也為0，故先行者必輸。

? ? ? ?2.某個局面(a1,a2,...,an)，若a1^a2^......^an=k(k不等于0)，則必有一種局面ai能夠通過合法的步驟轉換為ai'，使結果變為0（k二進制中的某一位中的1必定是某個ai貢獻過來的），其中ai^k=ai'<ai（ai在k的二進制下最高位是1），所以是后行者必輸。

? ? ? 3.某個局面(a1,a2,...,an)，若a1^a2^......^an=0，若ai能夠通過合法的步驟轉換成另一個局面ai'使結果也為0，那么a1^a2^..^ai^...^an=a1^a2^..^ai'^...^an，根據消去律，得到ai=ai'，這是不合法的移動（因為還是它本身），所以是先行者必輸。

? ? ? 而這樣，我們就可以在O（n）內知道應該是先行還是后行了。

? ? ? 關于SG函數，我們先定義一種作用在集合的運算mex，定義結果為該集合中未出現的最小非負整數，如mex{0,1,2,4}=3、 mex{2,3,5}=0、mex{}=0。

? ? ??對于一個給定的有向無環圖，定義關于圖的每個頂點的Sprague-Garundy函數g如下：g(x)=mex{ g(y) | y是x的后繼（就是子局面） }。

? ? ? 實際上，所以Nim游戲都可以抽象成一個模型：一個有向圖中，一個棋子代表著當前局面，每個頂點代表著每個局面，而每位選手則負責移動棋子，直到某個選手無法移動棋子則為負。

? ? ?所以對于SG函數的性質，跟上面所講的1,2,3是一樣的：

? ? ? 1.對于Terminal?position對應的頂點，就是沒有出邊，其g（x）=0;

? ? ? 2.若該點ai的g（ai）不為0，則它的后繼里存在一個頂點ai'它的g（ai'）=0；

? ? ? 3.若該點ai的g（ai）=0；則它的后繼里沒有一個頂點ai'它的g（ai'）=0。

? ? ? 事實上，如果有多堆石子，我們可以把每堆石子都抽象成一個棋子在圖中移動，那么我們所要做的就是講每個棋子所在頂點的SG值算出來，異或一下即可。

? ? ? 稍微變一下，有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數顆，可以從第3堆及以后石子里取任意顆， 我們可以把它看作3個子游戲，第1個子游戲只有一堆x顆石子，每次可以取1、2、3顆，很容易看出x顆石子的局面的SG值是x%4（數學歸納法可以證明）。第2個子游戲也是只有一堆 石子，每次可以取奇數顆，經過簡單的畫圖可以知道這個游戲有x顆石子時的SG值是x%2。第3個游戲有n-2堆石子，就是一個Nim游戲。對于原游戲的每 個局面，把三個子游戲的SG值異或一下就得到了整個游戲的SG值，然后就可以根據這個SG值判斷是否有必勝策略以及做出決策了。

? ? ?g（x）=b，說明當前局面可以移動到g（a）=b-1，b-2，b-3.......1,0上。

? ? ? 所以，對于我們來說，我們是將一個復雜的游戲分成許許多多若干個簡單的小游戲，再分別求出SG值，再全部異或起來就是原游戲的SG值了。

? ? ? 關于題目所說的完美操作，雙方足夠聰明，指的就是當前這個局面如果能夠贏得這場游戲的話，這個人就會順著這個能夠贏的這條路徑進行下去，就是N-position。