必胜必败分析
概念
更明确的定义概念：
必胜点（N）
先手必胜点。
必败点（P）
先手必败点。
性质
所有终结点都是必败点；
从必胜点出发，存在一种方法能够进入必败点；
从必败点出发，无论如何都只能进入必败点。
算法
设计一种算法来分析，一个局面是先手必胜还是先手必败。
- 将终结点标为必败点；
- 将所有一步操作进入必败点的位置标为必胜点；
- 如果从某一个点开始，一步操作后只能进入必胜点，那么标记为必败点；
- 重复步骤2， 3.
记忆化搜索的过程，可以画出博弈树。
例子
描述
一个 $4$ 行 $3$ 列的矩阵，有一个小球放在左上角。两个人依次移动小球，每次只能：
- 向右移动一格；
- 向下移动一格；
- 向右下移动一格。
最后无路可走的人输。两人按最优策略，问谁必胜。
解析
直接用 $4$ 行 $3$ 列的矩阵表示必胜必败情况。用*表示情况不确定，P表示必败，N表示必胜。
首先标记最终的点是必败点：
***
***
***
**P
之后推第四行。第四行的所有点，只能往右走，所以：
***
***
***
PNP
再看第三行。$(3, 3)$ 可以往下走到必败，所以是必胜点。$(3, 2)$ 可以往右下走到必败，所以是必胜点，$(3, 1)$ 同理，所以：
***
***
NNN
PNP
同样的，可以算出最后两行：
NNN
PNP
NNN
PNP
所以，先手必胜。
代码实现
两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。分析必胜必败。
bool win[1001], vis[1001];//win[i]表示剩余i个物品时的必胜必败情况
void init() {
win[0]=false;
vis[0]=true;
}
void dfs(int x){
if(vis[x]){
return;
}
if(x>=1){
dfs(x-1);
}
if(x>=3){
dfs(x-3);
}
if(x>=4){
dfs(x-4);
}
win[x]=false;
if(x>=1&&!win[x-1]){
win[x]=true;
}
if(x>=3&&!win[x-3]){
win[x]=true;
}
if(x>=4&&!win[x-4]){
win[x]=true;
}
vis[x]=true;
return;
}
SG函数
组合博弈游戏
组合博弈游戏是这样一种博弈游戏：
- 有两个游戏者
- 有一个有限的游戏状态集
- 游戏规则规定了在每一个状态可以到达的后继状态集。如果在任意状态，双方的走步集合是相同的，那么这个游戏是公平的，否则是不公平的。比如象棋是不公平的，因为每个玩家只能移动自己的棋子。
- 两个人轮流操作
- 一般情况下，当一方无法操作时，无法操作者输，游戏结束。
我是真找不到别的定义了……
对于任意一个公平的组合博弈游戏（ICG），我们将每个可能的局面当成图论当中的一个点。
在这个图中的连边规则是：把局面向这个局面经过操作后可能得到的所有局面连边，构成一个有向图。如果这个游戏对于任意的局面 $A$，都不能通过一些操作，回到这个局面 $A$，那么构成的图是一个有向无环图（DAG）。
SG函数
定义一个 $mex$ 函数，表示对于一个集合，不属于该集合的最小非负整数。比如 $mex\{0, 1, 2, 4\}=3$.
还是在这个博弈游戏中：两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。
我们对每个状态进行分级，终结态的级别是 $0$. 如果一个状态能够变为 $0$ ~ $n-1$ 级的状态，那么这个状态是 $n$ 级状态。
状态 $1$ 能够变成 $0$ 级状态，称它为 $1$ 级状态；
状态 $2$ 只能变成 $1$ 级，不能变成 $0$ 级，所以它的级别为 $0$；
状态 $3$ 可以变为 $0$ 级，级别为 $1$；
状态 $4$ 可以变为 $0,1$ 级，级别为 $2$；
状态 $5$ 可以变为 $0,1,2$ 级，级别为 $3$.
在博弈游戏当中，SG函数定义为：$\operatorname{sg}(x)=mex\{\operatorname{sg}(y)\mid y$ 是 $x$ 的后继$\}$，也就是上面所说的状态等级。
对于一个ICG来说，状态 $x$ 是必败态，当且仅当 $\operatorname{sg}(x)=0$.
例子
两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。
$\operatorname{sg}(0)=mex(\emptyset)$，
$\operatorname{sg}(1)=mex\{\operatorname{sg}(0)\}=mex\{0\}=1$，
$\operatorname{sg}(5)=mex\{\operatorname{sg}(4), \operatorname{sg}(2), \operatorname{sg}(1)\}=3$.