分析的是甚麼遊戲?
考慮由局面組成的有限有向無環圖。邊代表合法走法;在同一局面,兩名玩家的合法走法相同,不能走的一方落敗。這些是有限、無偏、正常玩法的假設:它們排除了無限遊戲,不涵蓋走法依玩家而異或終局規則不同的遊戲。
定義 5.1.1
(Mex 與局面的值)
對非負整數有限集合 , 是不在其中的最小非負整數;特別有 。遞歸定義局面 的值為
終局的值為零。無環性讓我們可以向後定義所有值。
零值與致勝走法
定理 5.1.2
(值為零表示輪到走的一方落敗)
在有限的無偏正常玩法遊戲中,值為零的局面對輪到走的一方是必敗的(雙方最佳對弈);值為正的局面是必勝的:該方可走到值為零的局面。
證明
(對遊戲圖向後歸納)
值為零的局面沒有值為零的後繼,因為零不在後繼值中。值為正的局面有值為零的後繼,因為比其 mex 小的每個非負整數都必須出現。然後從終局向後歸納:終局的值為零而且無法走步,所以輪到走的一方落敗。若某局面的值為零,它所有後繼的值都是正的,由歸納假設,每個後繼對下一步的走子者都是必勝的,所以現在走的一方落敗。若它的值為正,走的一方可走到值為零的後繼,由歸納假設,該局面對在那裏走子的一方是必敗的。此結論使用了上述正常玩法規則。
反例模式
Mex 不是走法數目
若一堆中每步可取走一或兩個代幣,三個代幣有兩個合法走法,分別到達兩個及一個代幣。後繼值是 和 ,所以其值為 。單靠合法走法數目不能決定局面值。
為何獨立遊戲以異或合併
定義 5.1.3
(遊戲的和)
對局面 ,其和 指每一步只在其中一個分量走一步。非負整數上的 表示按位異或。
定理 5.1.4
(和的異或規則)
對有限無偏正常玩法遊戲的局面 ,
證明
(對剩餘走法數歸納)
對兩個分量的最長剩餘走法數之和歸納。設 、、。只改變 的後繼由歸納假設有值 ;因 不在 的後繼值中,,所以後繼值不可能是 。只改變 時同理。
現在任取整數 ,令 。在 與 不同的最高位, 是 而 是 。因為 , 至少一個在該位是 。假設是 ,則 。mex 的定義保證 有值為 的後繼,而所得和的值為 。選中 的情況相同。因此沒有後繼的值是 ,但每個小於 的值都出現,故其 mex 是 。
證明透視
Mex 證明的兩部分
這個證明須對同一個數 說明兩件事:和的後繼沒有一個的值是 ,並且每個比它小的值都出現。第一件只用到 不在 的後繼值中、 不在 的後繼值中,即 mex 定義中「不在集合內」的一半。第二件才是不尋常的一步: 與 不同的最高位,指出一個可以藉由與 異或而降低其值的分量,然後 mex 定義中「每個更小的值都出現」的一半提供所需的後繼。異或正是用在找出該位為 的分量這一處;對普通的值相加,這個論證沒有對應的版本。歸納之所以能收尾,是因為每走一步,剩餘的走法就縮短。
證明可重複用於有限多個分量;它確定遊戲值,不只是勝負。異或值非零時可走到零;異或值為零時每個合法後繼都非零。
常見錯誤
(把值相加而不是異或)
兩堆各有一個代幣,值分別為 與 。其和局面的值為 :先手走到 ,後手取走最後一個代幣,先手落敗。若把值相加會得 ,錯誤地暗示先手獲勝。合併的規則是異或。
一個取子遊戲
設一堆有 個代幣,每步可在數量足夠時取走 或 個。
定理 5.1.5
(每步取一個或兩個的遊戲的值)
在這個遊戲中,對每個 都有 。
證明
(對堆的大小歸納)
基礎值為 和 。當 ,由歸納假設,後繼 的值是模 餘數中不等於 的另外兩個;由 mex 定義, 是剩下的餘數。
這也證明了上面反例使用的值。
例題 5.1.6
(用 mex 算出最初幾個值)
局面 是終局,所以 。局面 只有後繼 ,所以 。局面 的後繼為 ,值為 ,所以 。局面 的後繼為 ,值為 ,所以 。局面 的後繼為 ,值為 ,所以 。局面 的後繼為 ,值為 ,所以 。局面 的後繼為 ,值為 ,所以 。數列 就是 。終局 是唯一沒有後繼的情況,所以它的值是空集合的 mex。
例題 5.1.7
(大小為 4 與 8 的兩堆)
若兩堆分別為 和 ,其值為 和 ,異或為 ,故輪到走的一方獲勝。第一堆取走 得 ,其值為 ;第二堆取走 得 ,其值為 。兩步均得到零異或。其他合法首步是 或 ,異或均非零,所以以上就是全部致勝首步。
例題 5.1.8
(三堆,其中一堆的值為零)
在同一個遊戲中取三堆 。其值為 ,異或為 ,所以輪到走的一方獲勝。要使異或為零,必須把某一堆走到「其餘兩堆的異或」那個值:對 的一堆(值 ),目標是 ,取走一個代幣得 即可;對 的一堆(值 ),目標是 ,取走兩個代幣得 即可。結果 與 的值分別為 與 。 的一堆值為 ,沒有致勝的走法:把它走到 或 ,異或分別是 或 ,都不為零。
習題與解答
快速檢查
(空堆的值是多少?)
它沒有後繼。
解答 · 答案
,即空集合的 mex。
快速檢查
(在此取子遊戲中, 個代幣的值是多少?)
使用 的公式。
解答 · 答案
。
快速檢查
(在上述規則下,從 出發誰會贏?)
計算兩堆的值。
解答 · 答案
兩堆值均為零,故異或為零;雙方最佳對弈下輪到走的一方落敗。
快速檢查
(若改成不能走的一方獲勝,可不加證明地沿用零值結論嗎?)
歸納的哪一步用到終局規則?
解答 · 答案
不可。這改變了終局條件,正常玩法的歸納不再按原樣適用。