描述：

尼姆博奕(Nimm Game)，有n堆石子，每堆石子有若干石子，兩個人輪流從某一堆取任意多的物品，規定每次至少取一個，多者不限。取走最后石子的人獲勝。

標準解法：

判斷：

先計算先手是必勝還是必敗：

將每堆石子的數量做二進制異或（即用二進制表示，每個數字的第一位做異或；第二位做異或...），結果如果是0，則必敗；否則必勝。

（其實每個二進制位如果有偶數位1，則異或結果是0，否則為1；異或符合結合律，交換律）

做法：

如果是必勝局如何操作：

必勝局則異或結果不是0，操作某一堆，使得異或結果是0。

證明：

這其實是ICG游戲的標準解法。找到P態和N態（也稱奇異非奇異局勢，平衡態、終態等）：

P態：必敗態，P態的任一操作都將使局面轉為N態；

N態：必勝態，N態可以一步轉為P態；

?

其實不用管上面的理論也行，只有證明以下結論即可：

1.對于一個異或和為0的局面，任一操作都將使其不為0；

2.對于一個異或和不為0的局面，存在一個操作使其為0；

對于1：由于只能操作一個數，至少減一，則有：

　　　　　　如果改變后的數的二進制表示中，1對應的位完全和原來一樣，則必定有0改為了1，導致改變后的數大于原數，矛盾。

　　　　　　所以，改變后的數二進制中，至少有1個1變成了0，則改位的異或和改為了1，證畢。

對于2：可以通過改變1的奇偶來改變異或和（可以通過刪除1或增加1）：

　　　　　　設從高到低，含有奇數列的序號位w1, w2 ,w3...

　　　　　　任意選取最高列中，1所在的數。刪除這個1，實際是分配w1 - 1個1給這個數后面的任一列。

　　　　　　則這行中，多出的1刪去，少了的補上即可。

　　　　　　如：　　　　　

　　　　　　　　5：? 0 1 0 1
　　　　　　　　10：1 0 1 0
　　　　　　　　1：? 0 0 0 1
　　　　　　　　4：??0 1 0 0

　　　　　　其中奇數號列位4，2，而第四列中，10的最高位的1可刪除，刪去1（實際是刪去8），

　　　　　　后面可任意改變數量，而第二列中也多出1，刪去。得0。即10全部取走。

由于0，0，0是異或和為0的狀態，只要一直將異或為0的狀態交給對方，由于數量一直減少，則自己總能到達0，0，0態，取得勝利。

轉載于:https://www.cnblogs.com/willaty/p/8151666.html

總結

以上是生活随笔為你收集整理的ICG游戏：尼姆游戏异或解法的证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。