博弈論
ICG 遊戲
若滿足以下條件：
-
遊戲由兩個人蔘與，兩人輪流做出決策且必定對自己最有利；
-
當有一人無法做出決策時遊戲結束，無法做出決策的人輸，且無論兩人如何決策，遊戲都一定會結束（不會出現平局）
-
遊戲中的同一個狀態不可多次抵達，任意遊戲者在某一確定狀態下做出的決策只與當前狀態有關，而與遊戲者無關
DAG 中的博弈
根節點有一個棋子，兩個遊戲者輪流移動這顆棋子；
-
若當前點沒有後繼點，則當前點為必敗點；
-
若當前點的後繼點存在必敗點，則當前點為必勝點，否則為必敗點；
SG 函數（Sprague-Grundy）
定義 $ mex(S) $ 為 最小的不屬於集合 $ S $ 的非負整數
定義SG函數： $ SG(u) = mex ({ SG(v) }) $
性質：
- 若SG函數值為0，則當前點必敗，否則必勝；
滿足DAG上博弈的性質；
SG 定理
遊戲的和的SG函數值 等於 遊戲的SG函數值的異或和
Nim遊戲各類變形
Nim
$ n $ 堆物品，每堆 $ a_i $ 個，兩個玩家輪流取走任意一堆的任意個物品，不能不取，取到最後一個物品的人獲勝
若 $ (\bigoplus_{i=1}^{n} a_i) = 0 $ ，則先手必敗，否則先手必勝
k-Nim
$ n $ 堆物品，每堆 $ a_i $ 個，兩個玩家輪流取走最多 $ k $ 堆中的任意個物品，不能不取，取到最後一個物品的人獲勝
令 $ x $ 在二進制下第 $ i $ 位的值為 $ s(x)_i $
若 $ \forall i , (\sum_{j=1}^{n} s(a_j)_i ) \mod ( k + 1 ) = 0 $ ，則先手必敗，否則先手必勝
階梯 Nim
$ n $ 堆物品，每堆 $ a_i $ 個，兩個玩家輪流將任意一堆 $ k $ 中的任意個物品放入 $ k - 1 $ 中 ，不能不操作，無法操作的人輸
若 $ (\bigoplus_{i=1且i為奇數 }^{n} a_i) = 0 $ ，則先手必敗
Anti-Nim
$ n $ 堆物品，每堆 $ a_i $ 個，兩個玩家輪流取走任意一堆的任意個物品，不能不取，取到最後一個物品的人失敗
-
若 $ \forall i \in [1,n], a_i=1 且 (\bigoplus_{i=1}^{n} a_i) = 0 $ , 則先手必勝
-
若 $ \exists i \in [1,n], a_i > 1 且 (\bigoplus_{i=1}^{n} a_i) \neq 0 $ , 則先手必勝
-
否則先手必敗
博弈論題目常用做題技巧
- 規約為經典模型（如 Nim 遊戲），或經典模型變形
- 分類討論
- SG函數（勝敗態）DP
- 尋找必勝策略然後從簡單情況開始手玩
- 博弈思想：若當前狀態對自己有利，必定會盡量維持當前局面，否則盡力改變
