博弈论总结（20260201）

小米同学

博弈论

ICG 游戏

若满足以下条件：

1. 游戏由两个人参与，两人轮流做出决策且必定对自己最有利；

2. 当有一人无法做出决策时游戏结束，无法做出决策的人输，且无论两人如何决策，游戏都一定会结束（不会出现平局）

3. 游戏中的同一个状态不可多次抵达，任意游戏者在某一确定状态下做出的决策只与当前状态有关，而与游戏者无关

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
• 寻找必胜策略然后从简单情况开始手玩
• 博弈思想：若当前状态对自己有利，必定会尽量维持当前局面，否则尽力改变

来源：https://www.cnblogs.com/ZFR-Blog/p/19560996