初学博弈论
一、巴什博奕(Bash Game)
基本描述：
只有一堆n個石子，兩個人輪流從這堆石子中取石子，規定每次至少取一個，最多取m個，最后取完的人獲勝。
分析：
結論：
其中上述的情況1和3可以合并，故：
注意：
練習：
二、PN點分析
什么是PN點
PN點的屬性
分析步驟
結論
注意
練習
三、斐波那契博弈
基本描述
有一堆個數為n的石子，游戲雙方輪流取石子，滿足：
取最后石子的人為贏家。
結論
先說結論：
當且僅當n不是Fibonacci數時，先手必勝。換句話說，先手必敗構成Fibonacci數列。
分析
證明需要前置技能，“Zeckendorf定理”（齊肯多夫定理），其表述為：任何正整數可以表示為若干個不連續的Fibonacci數之和。
具體證明在這篇博文中給出，有興趣的讀者可以自行學習。
練習
四、威佐夫博弈
基本描述
有兩堆各若干個石子，兩個人輪流從某一堆或者兩堆中取同樣多的物品，規定每次至少取一個，多著不限，最后取完石子的人獲勝。
分析
設這兩堆石子分別有(A,B)個，并且A<=B。我們先來看一下先手必敗的局勢。
取第一堆的1個，后手取走第二堆的2個獲勝。
從第一堆第二堆各取1個，后手取走第二堆剩下的1個獲勝。
取第二堆的1個，后手從第一堆第二堆各取1個獲勝。
取第二堆的2個，后手取走第一堆的1和獲勝。
綜上所述，先手必敗。
先討論先手從第一堆中取的情況
先手可以從第一堆中取1個，后手從第二堆中取4個，轉化為(1,2),先手必敗。
先手可以從第一堆中取2個，后手從第二堆中取3個，轉化為(1,2),先手必敗。
再討論先手從第二堆中取的情況
先手可以從第二堆中取1個，后手從兩堆中各取2個，轉化為(1,2)，先手必敗。
先手可以從第二堆中取2個，后手從兩堆中各取3個，轉化為(0,0)，先手必敗。
先手可以從第二堆中取3個，后手從兩堆中各取1個，轉化為(1,2)，先手必敗。
先手可以從第二堆中取4個，后手從第一堆中取2個，轉化為(1,2)，先手必敗。
接著討論先手從兩堆中取的情況
先手可以從兩堆中各取1個，轉化為(2,4)，此時情況較多
后手足夠聰明，他從第二堆中取了1個，轉化為(2,3)，先手也足夠聰明，他為了不直接輸掉，從第一堆中取了1個(其他取法直接輸掉了)，轉化為(1,3)，此時后手從第二堆中取1個，轉化為(1,2)，先手必敗。
先手可以從兩堆中各取2個，后手從第二堆中取一個，轉化為(1,2)，先手必敗。
綜上所述，先手必敗。
其他的先手必敗局勢
(4,7),(6,10),(8,13),(9,15),(11,18).
我們將先手必敗局勢的集合，稱為奇異局勢。
奇異局勢的性質
Betty定理
我們可以發現，將所有奇異局勢按照第一堆的石子的數目從小到大排列，每個奇異局勢的差值是自然數列。
進一步觀察發現，對于一個奇異局勢(A,B), A = 下取整[ (B-A) * 1.618 ]，更準確的說，1.618 = (sqrt(5) + 1) / 2.
為什么會是這樣的？ 具體的證明涉及到Betty的定理，有興趣的讀者可以百度，這里不再贅述。
常見的幾類問題
檢查是否是奇異局勢。
由于差值是固定的，根據差值計算。
練習
五、尼姆博弈
基本描述
有三堆石子， 每堆有若干個，兩個人輪流從某一堆中任取石子，每次至少取一個，多者不限，最后取完者獲勝。
分析
用(A,B,C)來表示某一特定局勢，同時規定A<=B<=C。奇異局勢表示先手必敗。
對于一個奇異局勢(A,B,C),我們可以發現，A(XOR)B(XOR)C = 0。
下面一條需要的前置技能
設有數字a,b，a(XOR)b(XOR)(a(XOR)b) = (a(XOR)a)(XOR)(b(XOR)b) = 0
對于一個非奇異局勢(A,B,C),我們只需要將C轉化為(A(XOR)B)即可，而將C轉化為(A(XOR)B)的操作為，C = C-(A(XOR)B)即可。
注：
練習
六、SG函數
基本描述
SG函數為計算博弈狀態的函數，當SG[X] = 0時，說明先手必敗。
為了求解SG函數，首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
對于任意狀態 x ， 定義 SG(x) = mex(S),其中 S 是 x 后繼狀態的SG函數值的集合。如 x 有三個后繼狀態分別為 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。
這樣 集合S 的終態必然是空集，所以SG函數的終態為 SG(x) = 0,當且僅當 x 為必敗點P時。
說起來很抽象，舉一個具體的例子來說明一下。
實例：取石子游戲
游戲規則：
有1堆n個的石子，每次只能取{ 1, 3, 4 }個石子，先取完石子者勝利，那么各個數的SG值為多少？
SG分析
SG[0] = 0(顯然沒有石子可取時必敗)；
f[] = {1,3,4}(表示每次取有3中方案，取1個，取3個，取4個)；
當石子x = 1時，可以取走1-f{1}個石子,SG[1] = mex(SG[1-1]) = mex(0) = 1;
當石子x = 2時，可以取走2-f{1}個石子,SG[2] = mex(SG[2-1]) = mex(1) = 0;
當石子x = 3時，可以取走3-f{1,3}個石子，SG[3] = mex(SG[3-1],SG[3-3]) = mex(0,0) = 1;
當石子x = 4時，可以取走4-f{1,3,4}個石子，SG[4] = mex(SG[4-1],SG[4-3],SG[4-4]) = mex(1,1,0) = 2;
以此類推…
我們可以打出SG函數的表，根據表來判斷是先手必勝還是先手必敗。
練習
七、更多的練習
總結
- 上一篇： hasset java_java Has
- 下一篇： 传播时延、发送时延、处理时延和排队时延各