<style> .reveal .slides { text-align: left; font-size:30px; } </style> # combinatorial games ## 組合賽局 ---- ## 定義 需要滿足以下條件： 1. 遊戲有剛好兩人參與，兩人輪流做出決策，並且兩人做出的決策都是對自己最優的 2. 當有一人無法決策的時候，該人失敗。 3. 遊戲沒有平手，必然會在有限時間內結束。 4. 遊戲是公開透明的，沒有不確定或隨機的因素。 ---- # 常見賽局種類 - 標準賽局：輪到該回合，無法操作的玩家為輸 - 匱乏賽局：輪到該回合，無法操作的玩家為贏 - 無偏賽局：在同一個局面下，雙方玩家可以做的操作皆相同 - ~~有偏賽局：在同一個局面下，雙方玩家可以做的操作可能不同~~ 今天會介紹上面三種 --- ## 標準賽局 輪到該回合，無法操作的玩家為輸 ---- ## bash game 兩人玩遊戲，總共有 $N$ 顆石頭，兩個人輪流拿， 每次只能拿 1~3 顆，拿走最後一顆石頭的人獲勝 問先手贏還是後手贏? ---- ## 分析題目 1. 遊戲有剛好兩人參與，兩人輪流做出決策，並且兩人做出的決策都是對自己最優的 $\to$ 兩人玩遊戲且輪流拿，誰能拿走最後一顆石頭 2. 當有一人無法決策的時候，該人失敗。 $\to$ 拿走最後一顆之後就不能再拿了 3. 遊戲沒有平手，必然會在有限時間內結束。 $\to$ 每次都一定會少石頭，最後一定會被拿完 4. 遊戲是公開透明的，沒有不確定或隨機的因素。 $\to$ 能知道對方拿多少石頭，且沒有不確定因素 因此此題為無偏賽局 ---- ## 必勝態與必輸態 拿走最後一顆石頭的人贏，換句話說沒石頭拿的人輸 我們可以把當下剩下的石頭數量 $x$ 當成一種狀態 當 $x$ = 0 代表必輸態 而 x=0 可以由 x = 1,2,3 轉移過來 x = 1,2,3 為必勝態，因為他們可以轉移給必輸態 | 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | ---------- | - | - | - | - | - | - | - | - | | 狀態 | -1 | 1 | 1 | 1 | ? | ? | ? | ? | ---- ## 必勝態與必輸態 狀態為必勝態與必輸態其中一種，且兩種互相相反的 玩家對於當下**所有任何操作**都能把對手轉移到**必勝態**，則當下為**必輸態** 玩家對於當下**存在一種操作**都能把對手轉移到**必輸態**，則當下為**必勝態** 白話一點， 如果玩家當下做任何操作結果都會輸，則當下為必輸態 如果玩家當下存在一種操作會讓自己贏，則當下為必勝態 ---- 回到剛剛的石頭遊戲 當剩下的石頭數量剩下 $x$ 顆時，則玩家可以把局面 變成 $x$-1, $x$-2, $x$-3 其中一種狀態 且 玩家對於當下所有任何操作都能把對手轉移到必勝態，則當下為必輸態 玩家對於當下存在一種操作都能把對手轉移到必輸態，則當下為必勝態 因此可以推出下面的表格 | 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | ---------- | - | - | - | - | - | - | - | - | - | - | | 狀態 | -1 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 | ---- 結果用數學歸納法可以得到 $$ S(n) = \begin{cases} -1, & \text{$n\mod 4 = 0$} \\ 1, & \text{otherwise} \end{cases} $$ | 剩下石頭數量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | ---------- | - | - | - | - | - | - | - | - | - | - | | 狀態 | -1 | 1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 | 由於勝負只跟當下狀態有關，因此勝負決定的因素**只跟先後手**有關 ---- ## game graph 由於遊戲一定會在有限時間結束，因此狀態最後都會到 0 (結束) 因此會是一張有向無環圖(DAG)，狀態轉移則用一條有向邊連接  --- ## Nim game 有 $N$ 堆石頭，每一堆石頭有 $a_i$ 個，每次可以選其中的一堆非空的石頭堆拿至少一顆，問先手獲勝或者後手獲勝 ---- 在此遊戲中，每堆石頭都分別為獨立的子遊戲 ( sub game ) 如果把每個子遊戲的狀態都只設成先後手獲勝，則對於整個賽局沒有意義 因此要重新定義每堆石頭的狀態對於整場賽局的意義 但也必須符合前面的定義 必輸態**所有任何操作**都能把對手轉移到必勝態 必勝態**存在一種操作**都能把對手轉移到必輸態 ---- 我們可以用非負整數代表每個子遊戲的狀態 定義 0 為必輸態， 所有正整數為必勝態 而我們可以用 xor 去滿足以上性質 必輸態**所有任何操作**都能把對手轉移到必勝態 必勝態**存在一種操作**都能把對手轉移到必輸態 當 0(必輸態) xor 任何非0整數都會變成非0整數(必勝態) 任何非0數字(必勝態)都可以 xor 得到 0(必輸態) ---- ## Nim sum 回到 Nim game 假設有三堆 $5 (101_2), 8(1000_2), 22(10110_2)$ Nim sum 為每個狀態 xor 起來的結果 ($a_1$ ^ $a_2$ ^ ... ^ $a_n$) 變成 $27(11011_2)$ 而當下狀態為必勝態(非0整數)，我們可以藉由 xor 之後變成必輸態$(0_2)$ 把 $22(10110_2)$ 變成 $13(1101_2)$ 如此一來整個賽局變成必輸態 (xor 後為 0) 再經由任一個操作(拿取任意顆數石頭)又可以把當前狀態變成必勝態 ---- ## Nim Game - 多個獨立的子賽局組成 - 最後結果為必輸態(Nim sum = 0) - 必勝態與必輸態是能互相轉換的 - 能由當前局面計算出先手勝/後手勝 ---- ## game graph  --- ## Sprague-Grundy Theorem 把無偏賽局歸納成一個 SG value 以得到結果 ---- ## n 級勝態 來看 Nim game 每個子遊戲的狀態，當某堆石頭有 $a_i$ 時， 則他可以藉由操作得到 $0$ ~ $a_i-1$ 的狀態 先定義 0 級勝態為必敗態 而如果一個狀態是 n 級勝態，則他能達到所有 i (for all i=0~n-1) 級勝態 example: 當前狀態可以達到 0,1,4,5 級勝態，則他是 2 級勝態 當前狀態可以達到 1,2,3 級勝態，則他是 0 級勝態 當前狀態可以達到 0,1,2,3 級勝態，則他是 4 級勝態 ---- 會發現要求出當前狀態的 n 級勝態， 即為求出 mex (所有可達到的狀態的集合) mex($s$) 為對於一個集合 $s$，最小未出現過的非負整數 以剛剛的例子 mex({0,1,4,5}) = 2 mex({1,2,3}) = 0 mex({0,1,2,3}) = 4 ---- 再回到 Nim game 算各自的 N 級勝態 會發現當石頭堆有 0 顆石頭，則為必敗態 而有一顆石頭，可以拿走 1 顆，而一顆石頭可以達到 0 級勝態 因此為 1 級勝態 當有 N 顆石頭時，可以達到 0 ~ N-1 的石頭數量，也就是 0 ~ N-1 級勝態 因此一堆石頭有 $a_i$ 堆時，則他為 $a_i$ 級勝態 ---- 再一個例子 ## [luogu P4860](https://www.luogu.com.cn/problem/P4860) 總共有 $n(n \le 5 \cdot 10^7)$ 個石子，兩人分別可以取 $P^k$ 顆石子 (P為任意質數 $\land k=0或1)$，沒石子拿了就輸了 問先手勝或後手勝? 轉換題目即為 $N$堆石子，每次可以能 1 顆或質數顆，問誰拿走最後一顆? ---- ## game graph  ---- ## 表格 N = 0 為 0 級勝態 N = 1 為 1 級勝態( 轉成 0 級勝態(N = 0) N = 2 為 2 級勝態( 轉成 0 級勝態(N = 0)、轉成 1 級勝態(N = 1) N = 3 為 3 級勝態( 轉成 0 級勝態(N = 0)、1 級勝態(N = 1)、2 級勝態(N = 2) N = 4 為 0 級勝態( 轉成 1 級勝態(N = 1)、2 級勝態(N = 2)、3 級勝態(N = 3) 以此類推 | N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | ------ | - | - | - | - | - | - | - | - | - | - | | N級勝態 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 觀察即為當 N 整除 4 時，為必敗態 ---- 而我們把所有子遊戲的勝態 xor 起來就會是整個遊戲的 SG value 也就是我們想求出的結果 $\to$ 先手勝 or 後手勝 題目通常難度在於如何計算各個子遊戲的 SG value 通常可以透過好好觀察、通靈 ? 或者 DP 列出來 --- ## 匱乏賽局 輪到該回合，無法操作的玩家為贏 接下來一樣用 nim game 舉例 ---- 只有 $1$ 堆一顆石頭的情況 $\to$ 先手必敗 只有 $2$ 堆一顆石頭的情況 $\to$ 先手必勝 有 $k$ 堆一顆石頭的情況 $\to$ 由 $k$ 的奇偶性決定，$k$ 為奇數則先手必敗，偶數則先手必勝 ---- 而如果以下情況 1 1 1 2，可以把 2 顆石頭的那堆拿走 1 顆或 2 顆，因此可以控制輸贏 1 1 1 2 3 5 7 ... 有很多堆 > 1 顆石頭 根據數學歸納法則也最後也可以變成只有一堆 > 1 顆石頭 因此如果每堆石頭都是 1 顆，則直接判斷奇偶性 否則直接用原本標準賽局的方法(xor 每個子賽局)判斷輸贏 --- ## Practice 建議上面題目也做過一遍 [Homework Link](https://vjudge.net/contest/506062)