# 組合賽局 ---- ## 簡介 組合賽局是賽局理論 (Game theory) 的一個分支，定義如下 - 兩位玩家輪流進行操作 - 盤面資訊完全公開 - 任何盤面下的操作皆不含機率成分 - 賽局結果只有三個可能，A勝B敗、B勝A敗、AB平手 ---- ## 分類 組合賽局中有許多分類，以下是較為常見的四個： - 標準：輪到該回合，無法操作者輸。 - 匱乏：輪到該回合，無法操作者勝利。 - 無偏：在同一個盤面下，兩方能做的操作相同。 - 有偏：在同一個盤面下，兩方能做的操作可能不同。 ---- ## 定義 > 對於一個組合賽局，以下三者必有一成立。 > 1.先手擁有必勝策略 > 2.後手擁有必勝策略 > 3.兩人都有平手策略 --- ## 無偏賽局 由於組合賽局的內容較多，後面主要只會提到標準/匱乏的無偏賽局。 ---- ### 撿石頭 小時候常見的遊戲，有 N 顆石頭，兩人輪流拿，每次可以拿走 1 ～ 3 顆，拿到最後一顆的一方贏。請問先手還後手必勝? ---- 拿到最後一顆的贏，代表的是這是一個標準賽局，而對於同一個盤面（四顆），兩方能做的操作是相同的（一、二、三顆），因此這是一個無偏賽局。 ---- 當剩下 x 顆石頭，通過操作可以讓他變成 x - 1、x - 2、x - 3 顆，於是我們可以畫出以下表格 | x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | s(x) | -1 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 通過數學歸納法可以知道當 - x 是 4 的倍數時後手必勝 - 反之則先手必勝 ---- 策略就是當 x % 4 != 0 時，先手將石頭數目變成 4 的倍數，接著後手回合結束後，再將石頭數目變成 4 的倍數，最後就會拿到最後一塊石頭了。 --- ### 賽局和 兩個賽局的和，表示為 $G_1+G_2$，其實就是把兩個賽局一起擺出來，每個回合可以對其中一堆進行操作 ---- ### 撿石頭 ex 有兩堆石頭，分別有 n、m 顆，每次拿走其中一堆的 1 ~ 3 顆，拿到最後一顆的一方贏。請問先手還後手必勝? ---- 根據觀察可以發現，只有在石頭堆相差在 4 的時候為先手必勝，其他情況都是後手必勝。 <!-- 兩堆的情況還比較容易分析，但如果是 3、4 或更多堆呢？ --> note: 等同於是將兩堆石頭在 2、0 步變為 4 的倍數 <!-- ### 型別 由於無偏標準遊戲不是先手勝就是後手勝，因此我們會分成兩個型別來分析 N：先手必勝 P：後手必勝 可以發現一場遊戲就是一直在 N 跟 P 之中做轉移 ---- --> ### --- ### nim number ---- #### 尼姆遊戲 是一種兩個人玩的回合制數學戰略遊戲。也就是前文提到的撿石頭，遊戲者輪流從幾排棋子中選擇一排，再由這一排中取走一個或者多個。 可以是撿到最後一個的為贏家，或者是撿到最後一個的為輸家，前者稱為標準後者稱為匱乏 ---- 給定一個標準的example跟流程 $A \ \ \ B \ \ \ C$ $1 \ \ \ 2 \ \ \ 3$ $玩家2從C拿走2$ $1 \ \ \ 2 \ \ \ 1$ $玩家1從B拿走1$ $1 \ \ \ 1 \ \ \ 1$ $玩家2從C拿走1$ $1 \ \ \ 1 \ \ \ 0$ $玩家1從B拿走1$ $1 \ \ \ 0 \ \ \ 0$ $玩家2從A拿走1$ $0 \ \ \ 0 \ \ \ 0$ $玩家2勝利$ ---- 從以上可以發現兩件事情 1. 不論哪一種玩法，只要剛好剩下一排的棋子是二個或二個以上（其他排可能沒有棋子，或是只有一個），下一個遊戲者可以輕易的獲勝。 2. 在剩下各排都只有一個子的情況下，若是 $misère$ 版本(撿到最後一個的為輸家)，下一個遊戲者下完之後，只要留下奇數排就會勝利，若是 $normal$ 版本(撿到最後一個的為贏家)，下一個遊戲者下完之後，只要留下偶數排就會勝利。 ---- 而我們分析 $1 \ 2 \ 3$ 這個case，會發現他的遞迴樹應該長這樣  (normal的情況) ---- #### 尼姆數 尼姆數是由每一堆石子做亦或運算 $(xor)$ 的結果，以剛剛那張圖舉例，每個殘局的尼姆數都是 $0$ ，然後就可以大膽猜測尼姆數對於勝負的關西，只要輪到自己時尼姆數 $>0$ 代表必勝局，而 $=0$ 即為必敗局 以這局遊戲為例子 $\{5,6,7,8\}$ 這局的尼姆數為 $5 \ xor \ 6 \ xor \ 7 \ xor \ 8 = 12$ $nim(5,6,7,8)=5 \ xor \ 6 \ xor \ 7 \ xor \ 8 = nim(12) = 12$ 也就是說先手只需要讓尼姆數變成 $0$ ，那又因為亦或運算滿足結合率，又因 $a \ xor \ a = 0$ 因此$5 \ xor \ 6 \ xor \ 7 \ xor \ 8 \ xor \ 12 = 0$ ---- 然後會發現 $\{5,6,7,8\}$ 中， $12 \ xor \ 8$ 的結果是 $4$ , 於是我們先手要做的操作就是從 ${5,6,7,8}$ 中的 $8$ 那堆拿走 $4$ 即可。 這樣局勢會變成 $\{5,6,7,4\}$ $5 \ xor \ 6 \ xor \ 7 \ xor \ 4 = 0$ 對手因為不論拿甚麼都會破壞尼姆數為0的平衡，因此對手必敗。 ---- 另外，由於亦或的性質，因此可以把 $\{5,6,7,8\}$ 拆成 $\{5,6\} + \{7,8\} = nim(3) + nim(15) = \{3,15\} = nim(12) = 12$ 再次證明為必勝局，只要xor出來的結果是一樣的就都是相同的局面。 <!-- 也就是說，一個集合為 $\{ a_1,a_2...a_N \}$ 的 Nim 遊戲 --> <!-- 等價於一個僅有一堆數量為 $MEX( \{ a_1,a_2 ...,a_N \} )$ 的 Nim 遊戲 --> $\{5,6,7,8\} = \{12\}$ --- ### SG value 任何標準無偏賽局，皆可以轉換成一堆 $Nim$ 遊戲 我們將這個 $Nim$ 遊戲的堆的大小，定義為 $SG value$ ---- ### 另一個遊戲 同樣有 $N$ 堆石頭 ，每堆有 $a_1,a_2,a_3,...a_N$ 顆 先手選擇一堆石頭，設有 $a_i$ 顆，接著就變成只有一堆且數量為 $a_i$ 顆的 $Nim$ 遊戲 一個集合為 ${ a1 , a2 , ..., aN}$ 的 $Choose Nim$ 遊戲等價於一個僅有一堆數量為 $MEX( { a1 , a2 , ... , aN} )$ 的 $Nim$ 遊戲 $MEX$ 就是，在一個非負整數集合中，沒有出現的最小非負整數 $example :$ $MEX( { 0,1,2,4 } ) =3$ $MEX( { 1,2,4} ) =0$ ---- 簡單來說，我們把結束狀態的 $SG value$ 設為 $0$ 假設今天有一個遊戲，一條數線上有 $10$ 個正整數點一開始有一個棋子放在 $1$ 號點上雙方輪流移動同個棋子每次可往前 $1$ 或 $2$ 步先走到 $10$ 就贏了 因為每次只能往前 $1$ 步或者是 $2$ 步，因此 $SG(i) = MEX(SG(i+1),SG(i+2))$ ---- 初始化就是讓 $SG(10)=0$ ， 而第一步就是 $SG(9)=MEX(SG(10))=MEX(0)=1$ $SG(8)=MEX(SG(10),SG(9))=MEX(0,1)=2$ $SG(7)=MEX(SG(9),SG(8))=MEX(2,1)=0$ $SG(6)=MEX(SG(8),SG(7))=MEX(2,0)=1$ . . . $SG(1)=MEX(SG(3),SG(2))=MEX(2,1)=0$ 而 $SG_value$ 是 $0/1$ 則代表了先手必勝或是後手必勝。 也就是說這是一個後手必勝的遊戲 --- ## 謝謝大家 :eye-in-speech-bubble: