# Road Map

博弈型 dp跟其他类型动态规划不同：博弈型往往从第一步开始分析

策梅洛定理，SG 定理，minimax

# NIM 游戏

先手：第一个行动的称为先手

后手：第二个行动的称为后手

必败状态：无论采取何种行动，都会输掉游戏

必胜状态：某一局面下存在某种行动，使行动后对手面临必败局面

NIM 博弈不存在平局，只有先手必胜和先手必败两种情况。

# 定理

NIM 游戏先手必胜，当且仅当 $A_1\ xor\ A_2\ xor\ ...\ xor\ A_n \neq 0$

举例：（异或和为 0 的情况）

证明：

如上图所示，所有物品被取光是一个必败局面，当异或和为 0 时，先手必败（后手每一轮都取跟先手一样的石子数）

对于任意一个局面，如果 $A_1\ xor\ A_2\ xor\ ...\ xor\ A_n = x \neq 0$ ，设 x 的最高位 1 在第 k 位，则一定存在 $A_i$ 的第 k 位为 1， $A_i\ xor x < A_i$ ，拿走若干石子，使其成为 $A_i\ xor x$ ，就得到了一个所有石子异或和为 0 的局面。

# AcWing 891. Nim 游戏 (opens new window)

# SG 函数

# 补充

# Mex 运算:

设 S 表示一个非负整数集合.定义 mex(S)为求出不属于集合 S 的最小非负整数运算,即: mes(S)=min{x}; 例如:S={0,1,2,4},那么 mes(S)=3;

# SG 函数

在有向图游戏中,对于每个节点 x,设从 x 出发共有 k 条有向边,分别到达节点 y1,y2,····yk,定义 SG(x)的后记节点 y1,y2,···· yk 的 SG 函数值构成的集合在执行 mex 运算的结果,即: SG(x)=mex({SG(y1),SG(y2)····SG(yk)}) 特别地,整个有向图游戏 G 的 SG 函数值被定义为有向图游戏起点 s 的 SG 函数值,即 SG(G)=SG(s).

# 有向图游戏的和

设 G1，G2,····,Gm 是 m 个有向图游戏.定义有向图游戏 G,他的行动规则是任选某个有向图游戏 Gi,并在 Gi 上行动一步.G 被称为有向图游戏 G1,G2,·····,Gm 的和. 有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数的异或和,即: SG(G)=SG(G_1)\ xor\ SG(G_2)\ xor\ ···\ xor\ SG(G_m)

# 翻转游戏

# Nim 游戏

LeetCode 292. Nim Game (easy) (opens new window)

# 石子游戏

一个数字序列，两名玩家，两人依次从左右两个端点取，两人都会做出最佳选择

← 0x53_区间dp 0x54_状态压缩dp →