<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Game --- * 博奕論定義和簡介 * 巴什遊戲 (bash game) * bash game + bash game --> 賽局和 * 尼姆遊戲 (NIM game) * 博弈論的第一步 --> 轉化為game graph --> 轉化為DAG * 圖轉SG -- SG函數 * SG外的博奕論 數感 * 例題示範 --- ## 組合賽局定義 滿足至少以下條件： 1. 遊戲有剛好兩人參與，兩人輪流做出行動，並且兩人做出的行動都跟隨題目的原則(大局最佳或當回合最佳或題目特殊規則) 2. 遊戲會有結果，也就是最終會歸類到 "輸" "贏" "平手" 三種其中一種情況。 3. 遊戲是公開透明的，沒有不確定或不可控 不可知 機率 的因素。 4. 盤面資訊完全公開 ---- ## 博奕論簡介 * 標準 : 輪到該回合，無法操作的玩家為輸 * 匱乏 : 輪到該回合，無法操作的玩家為贏 * 或其他 ---- * 無偏 : 在同一個局面下，雙方玩家可以做的操作相同 * 有偏 : 在同一個局面下，雙方玩家可以做的操作可以不同 ---- ## 前提 今天只會討論在 "有限時間" 內結束，也就是不會陷入無限的狀況，遊戲一定會結束。 策梅洛定理: 對於一個賽局 不論他有多複雜，只要符合page 3-1 的博奕論定義，就一定會有 1. 先手有必勝策略 2. 後手有必勝策略 3. 雙方皆有平手策略 以上三者必然有其一成立。 --- ## bash game 兩人玩遊戲，總共有 $N$ 顆石頭，兩個人輪流拿， 每次只能拿 1~3 顆，拿走最後一顆石頭的人獲勝 問先手贏還是後手贏? ---- 首先分析題目，可以知道他是一個 無偏 標準 賽局。 做為一個最基礎也是最廣為人知的博奕論模型(減法博奕)，我們針對此遊戲去進行分析，我們若把當下石頭的數量 $x$ 當成一種狀態，當 $x == 0$ 時代表沒石頭可以拿，也就是輸了。 那由於 $0$ 會是最後一步，他的前一步會是多少呢? 分別是 $1,2,3$ 三種剩餘的狀態。 於是就可以得出結論 : 若可以讓對手操作後剩餘 $1,2,3$ 則我必贏 (因為我可以拿走剩餘全部的石頭) ---- 於是就可以畫圖，然後導出 $SG-value$ 不過我們先看一下對於每種狀態的分析。 |x|win/lose| |-|-| |0|1| |1|0| |2|0| |3|0| |4|1| |5|0| |6|0| |7|0| |8|1| ---- 那擅長dp的人會發現他每次可以轉移從 $x$ 轉移到 $x+1 , x+2 , x+3$ ```cpp bool dp[N]={}; memset(dp,-1,sizeof(dp)); for(int i=0;i<=n-3;i++){ for(int j=1;j<=3;j++){ if(dp[i]==1){ dp[i+j]=!dp[i]; } } } ``` ---- 而擅長數學，數感的人，會發現它其實就是 ```cpp int now=n%4==0?1:0; cout<<now<<"\n"; ``` ---- ## bash game的結論以及其衍生 bash game最後的結論 ```cpp cout<<(n%(m+1)==0)<<"\n"; ``` 原理就是 兩個人加起來拿滿4顆 (先手拿1顆 你就拿3顆)(先手拿2顆 你就拿2顆)(先手拿3顆 你就拿1顆) 以及其衍生， 必須對上面兩種解法都有一定的了解，才可衍生出套用在所有模型的結論。 對於畫出的每一層圖形，可以沿生出 **必勝組態** 以及 **必敗組態** ---- ## 必勝組態 必敗組態 必敗組態 : $x==0 x==4 x==8$ 必勝組態 : 必敗組態外的 那麼這兩個之間的關係 玩家對於當下**所有任何操作**都能把對手轉移到**必勝態**，則當下為**必輸態** 玩家對於當下**存在一種操作**都能把對手轉移到**必輸態**，則當下為**必勝態** 也就是說 如果玩家當下做任何操作結果都會輸，則當下為必輸態 如果玩家當下存在一種操作會讓自己必贏，則當下為必勝態 --- ## bash game + bash game --> 賽局和 有兩堆石頭,其中一堆有 $N$ 顆,另一堆有 $M$ 顆,兩人輪流拿,每次可以拿走任意其中一堆的 $1,2,3$ 顆,沒辦法拿的人輸。請問先手還後手必勝? ---- 他其實只需要直接把兩局遊戲的結果乘起來就好，你會發現它可以轉移的是 $dp(n-1,m) , dp(n-2,m) , dp(n-3,m) , dp(n,m-1) , dp(n,m-2) , dp(n,m-3)$ 於是就會變成  那你就會發現，只要他的差值是4的倍數，則先手必敗。 他分別可以看成是 一場 $N$ 顆的bash game + 一場 $M$ 顆的bash game , 而把這兩場賽局的結果加起來，就是指賽局和。 ---- 那現在的問題就是，如果今天有一堆賽局的話 怎解? 我要做那麼多維度的dp轉移嗎? 那其根本上 每局賽局可以分成兩種型別 * N (Next player win) : 下一輪輪到的玩家(先手)獲勝。 * P (Previous player win) : 上一輪輪到的玩家(後手)獲勝。 先手勝的賽局 -> N型別 後手勝的賽局 -> P型別 ---- 然後就會有以下定理 定理一 : 如果 $G_1 == G_2$ 則兩個類別相同。 -- 廢話定理 定理二 : 如果 $G_2 == P$ 則 $G_1 + G_2 == G_1$ -- P完全沒用 定理三 : 如果 $G_1$ 跟 $G_2$ 都是 $P$ 則 $G_1 == G_2$ 所以根據以上定理，會發現 型別為 $P$ 的賽局不論加多少個進來 都不會對原本的賽局造成影響，只要思考型別為 $N$ 的結果就好 --- ## 尼姆遊戲 (NIM game) ---- 有 $N$ 堆石頭，每一堆石頭有 $a_i$ 個，每次可以選其中的一堆非空的石頭堆拿至少一顆，問先手獲勝或者後手獲勝 ---- 也就是它是一個賽局和，分別有 $N$ 個賽局合起來的遊戲。 而我們可以用非負整數代表每個賽局的狀態 定義 $0$ 為必輸態， 所有正整數為必勝態 而我們可以用 xor 去滿足以上性質 必輸態**所有任何操作**都能把對手轉移到必勝態 必勝態**存在一種操作**都能把對手轉移到必輸態 當 $0$ (必輸態) xor 任何非 $0$ 整數都會變成非 $0$ 整數(必勝態) 任何非 $0$ 數字(必勝態)都可以 xor 得到 $0$ (必輸態) ---- 而我們分析 $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\}$ --- ## 博弈論的第一步 --> 轉化為game graph --> 轉化為DAG ---- 接下來要進入高度理論化的博奕論，把我們前面的遊戲轉化為可以套用在所有博奕的萬用模型，接下來的內容會比前面簡單的遊戲難非常多，且會重複利用到前面的理論(必勝組態,賽局和,MEX...) 做出SG ---- # 圈圈叉叉 ---- ## 簡易圈圈叉叉 這個賽局在一個連續的三個空白格子上遊玩。先手僅能放置叉叉,後手僅能放置圈圈,每次輪到的玩家要將符號填入一個空白的格子,盤面上出現連續兩個格子中含有自己的符號時獲勝,空白格子皆被填滿時若是沒有人獲勝,則平局。 ---- 小抄(畫圖在黑板上 ----  ---- 那由於有一個最基本的條件，是賽局需要在有限時間內結束，因此一定會有起點跟終點，然後不會有無限跟迴圈的狀況，所以一定可以畫出一個DAG出來，並且建邊的條件是可以從點 $v$ 轉移到點 $u$ 即可建立一條邊。 這樣就可以更明確的知道是如何轉移的。 --- ## 圖轉SG -- SG函數 ---- 任何標準無偏賽局，皆可以轉換成一堆 $Nim$ 遊戲 我們將這個 $Nim$ 遊戲的堆的大小，定義為 $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 級勝態 我們現在來枚舉看看 NIM game 的 勝態，即可更簡潔的知道他的做法。 (小抄畫黑板 因此一堆石頭有 $a_i$ 堆時，則他為 $a_i$ 級勝態，我們就可以回到尼姆數的結論，直接把所有石頭數xor起來即可。 ---- 所以我們遇到博奕論的第一步就是 想辦法轉換為NIM 然後求出SG --- ## SG外的博奕論 數感 ---- 找規律或者是找結論而已，通常會遇到非常明顯的規律，或者是他可以有一個結論，(奇偶性質,質數性質 之類的) --- ## 例題示範 ---- 本次題單的最後一題 移除壓克力板 題敘 : 桌面上有 $N$ 堆壓克力板,每堆分別有 $a_1, a_2......$a_N$ 片。Kevin 和 Nicky 打算用這些壓克力板玩一個遊戲,兩人輪流移動,每次可以從以下兩種 操作選一種: * 選擇一堆壓克力板,並把最上面的一片拿掉。 * 選擇一堆 $2x$ 片 ($x$ 為正整數) 的壓克力板,將它整堆拿掉,並另外補上 $k$ 堆每堆 $x$ 片的壓克力板。 $N \leq 10^5 , a_i \leq 10^9 , k \leq 10^9$ ---- 那麼發現到每堆之間是獨立的，根據賽局和，尼姆遊戲，以及尼姆數的結論，我們只需要把每堆的SG xor 起來即為答案。 那麼SG應該要怎麼求呢?可以畫圖推出他的轉移，那我們這邊直接寫出他可以怎麼轉移。 $\left\{ \begin{array}{**lr**} mex\{SG(x-1)\} \ \ , x \mod \ 2 = 1 \ and \ x > 0 \\ mex\{SG(x−1),SG(x/2)·(k \mod \ 2)\} \ \ , x \mod \ 2 = 0 \ and \ x > 0 \\ 0 \ \ , \ x = 0 \end{array} \right.$ ---- 然後畫圖找規律，分別可以找到當 $k$ 分別等於偶數和奇數的時候會有兩種結果 然後就可以求出 $\left\{ \begin{array}{**lr**} 2 \ \ , SG(x/2) = 1 \\ 1 \ \ , otherwise \end{array} \right.$ 然後就結束了。 --- ## 提問以及練習時間 ## [題單](https://vjudge.net/contest/593941) 我的AC-code都不長。 覺得有趣的話可以再來跟我探討:) 我有很多書可以借你:) 黑黑