標準無偏賽局與

# 標準無偏賽局與 # SG value ---- ## 先來看一下名詞定義 ---- ### 組合賽局 1. 兩位玩家對戰，輪流操作 2. 資訊是完整公開的 3. 沒有任何機率因素 4. 結果可由一贏一輸或平手來表示栗子(? ：圈圈叉叉、西洋棋、大部分的棋不是栗子：大富翁（機率)，撲克牌（不透明） ---- ### 各種組合賽局 - 標準：輪到該回合時，無法操作者輸 - 匱乏：輪到該回合時，無法操作者贏 - 無偏：同個盤面下，雙方可做的操作相同 - 有偏：同個盤面下，雙方可做的操作可能不同不難想像，標準及匱乏必然是一勝一負 ---- ### 簡單的小遊戲一條數線上有 $10$ 個正整數點一開始有一個棋子放在 $1$ 號點上雙方輪流移動同個棋子每次可往前 $1$ 或 $2$ 步先走到 $10$ 就贏了，不能超出範圍 #### 這是哪種賽局？（標準 or 匱乏，無偏 or 有偏） ---- ### 簡單的小遊戲 2.0 一條數線上有 $10$ 個正整數點一開始有一個棋子放在 $1$ 號點上雙方輪流移動同個棋子先手每次可往前 $1$ 或 $2$ 步後手每次可往前 $3$ 或 $4$ 步先走到 $10$ 就輸了，不能超出範圍 #### 這是哪種賽局？（標準 or 匱乏，無偏 or 有偏） ---- ### 標準無偏賽局由以上我們可以整理出幾個性質 1. 由於是無偏賽局，決勝因素即是先後手 2. 由於是標準賽局，勝者不是先手就是後手（好像是廢話於是我們可以將標準無偏賽局分為 1. $N$：先手獲勝 2. $P$：後手獲勝 ### 這兩個代號很重要喔！！！ --- ## 一些理論基礎以下內容中，我們討論的都是標準賽局 ---- ### 賽局和兩個賽局 $G1$ , $G2$ 的和，表示為 $G1+G2$ 其實就是，把兩個遊戲擺在一起玩，一次選一個遊戲並做一個操作 ---- ### 等價賽局定義兩個賽局 $G1$ , $G2$ , 若對於所有賽局 $H$，皆滿足： $G1+H$ 和 $G2+H$ 的型別相同( $N$ 或 $P$ ) 則稱 $G1$ 與 $G2$ 等價，表示為 $G1=G2$ --- ## 一些定理 ---- ### 定理 1 #### 如果 $G1=G2$ ， $G1$ 與 $G2$ 型別相同這是不是很像廢話 XD ---- ### 定理 2 #### 如果 $G2$ 的型別是 $P$ ， $G1+G2=G1$ 這個定理的意思是，任一賽局加 $P$ 賽局等於沒有加想像一下，在 $G1$ 原本會贏的玩家，可以一直維持 1. 對手一玩 $G2$ 就跟著玩，讓自己變成後手 2. 否則就專心玩 $G1$ ### 於是勝負不變 ---- ### 精美的圖圖 ![](https://i.imgur.com/KxNteOU.png) ---- ![](https://i.imgur.com/Z2Q5Qgx.png) ---- ![](https://i.imgur.com/35Vs9is.png) ---- ### 所以在左邊會贏的傢伙就還是會贏!!! ---- ### 定理 3 #### 如果 $G1$ , $G2$ 的型別都是 $P$ , $G1=G2$ 這個定理告訴我們，所有的 $P$ 賽局都是同一種 ### 證明：對於任一賽局 $H$ 都滿足 $H+G1=H=H+G2$ 根據等價賽局的定義， $G1=G2$ --- ## 進入正題對沒錯，剛剛都只是先備知識而已 --- ### 經典遊戲 Nim 有 $N$ 堆石頭，每堆有 $a_1$ , $a_2$ , $a_3$ , $...$ , $a_N$ 顆兩人輪流執行以下操作：每次從其中一堆拿走任意多但至少一顆的石頭，無法拿的人就輸了，請問先手必勝還是後手必勝？ ---- ### 直接講結論啦！ ---- ### 哈哈騙你的 ---- ### [Bitwise Operation](https://hackmd.io/@Paul-Liao/rJve8AY7t#/) ### [位元運算](https://hackmd.io/@Paul-Liao/rJve8AY7t#/) ---- ### 現在才要講結論啦 ! 定義一個特徵值 $X$ $X=a_1\oplus a_2\oplus a_3\oplus ... \oplus a_N$ 那個像龜殼的符號是 Bitwise-XOR （還有人不知道這是什麼嗎？ > $1\oplus0=0\oplus1=1$ > $1\oplus1=0\oplus0=0$ ---- ### 定理 4 #### 此遊戲先手必勝若且唯若 $X\neq0$ #### 後手必勝若且唯若 $X=0$ ---- ### 證明 1. 首先，結束盤面 $X=0$（每一項都是 $0$ ） 2. $X=0$ 的盤面無法走到其他 $X=0$ 的盤面假設將原本有 $a_i$ 顆的第 $i$ 堆拿成 $a_i'$ 顆特徵值變成 $X'$ , $X'=X\oplus a_i \oplus a_i'$ 因為 $a_i\neq a_i'$，所以 $X'\neq X=0$ ---- ### 為什麼 $X'=X\oplus a_i\oplus a_i'$ 假設原本的 $X=a_j\oplus a_k\oplus a_l\oplus a_i$ 因為 $a_i\oplus a_i=0$ （每一位都會相同）所以 $X\oplus a_i=a_j\oplus a_k\oplus a_l$（去掉 $a_i$ 了） $a_j\oplus a_k\oplus a_l\oplus a_i'=X\oplus a_i\oplus a_i'=X'$ ---- 3. $X\neq 0$ 的盤面必可以走到一個 $X=0$ 的盤面將 $X$ 寫成二進制，設其最高位為 $2^k$ 的那一位在 $N$ 堆中必有一堆 $a_i$ 在二進制下的第 $k$ 位為 $1$ 將那堆的數量拿成 $a_i'=a_i \oplus X$ 由於 $k$ 是 $X$ 的最高位，因此 $a_i'<a_i$ 特徵值變為 $X'=X\oplus a_i\oplus a_i'=0$ ---- ### 哈哈我知道沒人聽得懂 ### 看個栗子 ~ 假設現在有 $5$ 堆，數量分別為 $2$ , $5$ , $7$ , $9$ , $6$ -> $X=15$ 換成二進制後 $X=1111$ , 最高位 $2^k,k=3$ 也就是最左邊的那一位 ---- 在五個數中我們發現 $9$ 的二進位 $1001$ 在第 $k$ 位為 $1$ 於是將 $9$ 拿成 $9\oplus 15=6$ 寫成二進位就是 ``` 1 0 0 1 = 9 1 1 1 1 = 15 --------------> XOR 0 1 1 0 = 6 ``` ---- ### 新的 $X$ 值就是 ### $2\oplus 5 \oplus 7\oplus 6 \oplus 6=0$ ---- ## 上面那些可以幹嘛假設現在 $X\neq 0$ ，每一輪中： 1. 先手把 $X$ 變成 $0$ 2. 後手把 $X$ 變成不是 $0$ ---- ### 最後必是後手面臨結束盤面 ### 因此先手必勝 --- ## 另一個遊戲 Choose Nim 同樣有 $N$ 堆石頭，每堆有 $a_1$ , $a_2$ , $a_3$ , $...$ , $a_N$ 顆先手選擇一堆石頭，設有 $a_i$ 顆，接著就變成只有一堆且數量為 $a_i$ 顆的 Nim 遊戲 ---- ### 定理 5 #### 一個集合為 { $a_1$ , $a_2$ , $...$ , $a_N$ } 的 Choose Nim 遊戲 #### 等價於一個僅有一堆數量為 #### MEX( { $a_1$ , $a_2$ , $...$ , $a_N$ } ) 的 Nim 遊戲 MEX 就是，在一個非負整數集合中，沒有出現的最小非負整數栗子：MEX( { $0$ , $1$ , $2$ , $4$ } ) $=3$ MEX( { $1$ , $2$ , $4$ } ) $=0$ ---- ### 聽起來是玄學可以醬想，一個僅有一堆 $i$ 顆的 Nim 遊戲在先手操作了一次後不就變成了 $0$ ~ $(i-1)$ 顆的 Nim遊戲嗎剛好符合了 Choose Nim 遊戲的規則 ---- ### 先手不會選數量大於 MEX 的嗎？一堆的 Nim 遊戲，只要不是 0 顆都是先手必勝換句話說， Choose Nim 遊戲中，先手應會選盡量小的堆，因此不用考慮大於 MEX 的 --- ## SG value 哈哈終於要講 SG value 了 ---- ### Sprague-Grundy Theorem #### 任何標準無偏賽局，皆可以轉換成一堆 Nim 遊戲 #### 我們將這個 Nim 遊戲的堆的大小，定義為 SG value ---- ### 為什麼可以醬！！！簡單來說，我們把結束狀態的 SG value 設為 0 再通過定理 5 （ MEX 那個），求出整個遊戲的 SG value 每個狀態的 SG value 即是 ### 所有可以轉移到的狀態的 MEX --- ### 又双叒叕是栗子一條數線上有 $10$ 個正整數點一開始有一個棋子放在 $1$ 號點上雙方輪流移動同個棋子每次可往前 $1$ 或 $2$ 步先走到 $10$ 就贏了，不能超出範圍沒錯就是一開始的那個簡單的小遊戲 ---- 因為每次只能往前 $1$ 或 $2$ 格所以這個遊戲中 $SG(i)=$ MEX( { $SG(i+1)$ , $SG(i+2)$ } ) ---- ### step 1 設 $SG(10)=0$ ，也就是說，從 $10$ 開始，後手必勝 ( P 型別 ) ### step 2 $SG(9)=$ MEX( { $0$ } ) $=1$ 也就是說，從 $9$ 開始，先手必勝 ( N 型別 ) ---- ### step 3 $SG(8)=$ MEX( { $0$ , $1$ } ) $=2$ 也就是說，從 $8$ 開始，先手必勝 ( N 型別 ) ### step 4 $SG(7)=$ MEX( { $1$ , $2$ } ) $=0$ 也就是說，從 $7$ 開始，後手必勝 ( P 型別 ) ---- ### 快轉... 快轉... 現在我們已經知道 $SG(4)=0$ , $SG(3)=1$ ---- ### step 8 $SG(2)=$ MEX( { $0$ , $1$ } ) $=2$ 也就是說，從 $2$ 開始，先手必勝 ( N 型別 ) ### step 9 $SG(1)=$ MEX( { $1$ , $2$ } ) $=0$ 也就是說，從 $1$ 開始，後手必勝 ( P 型別 ) ---- ### 於是乎 ### 我們知道這是一個後手必勝的遊戲