Game

我们现在讨论的Game具有以下特征：
Double（双人）：游戏由两个人进行。
Symmetric（对称）：在同一种局面下两个人的决策集合是相同的。
Sequential（轮流）：两个人轮流执行决策。
Finite（有限）：游戏在有限步之后一定会终止。
Exact（确定）：决策不带有随机性。
Open（公开）：游戏的信息是完全公开的。
Intelligent（聪明）：两个人都是绝顶聪明的。

如果没有说明我们认为无法决策的人输。

游戏图

我们将一个局面看做是一个点，将某个局面的一种决策看做是这个点的出边，那么一个满足上述条件的游戏就可以和一张DAG对应起来。

N&P

定义先手必胜为N态，先手必败为P态。
一个状态为P态的充要条件是该状态的出边到N态。
在此基础上，一个状态为N态的充要条件是该状态至少存在一条出边可以走到P态。

SG函数

全名叫做Sprague-Grundy Function。
定义\(\operatorname{mex}(S)\)为集合\(S\)中未出现的最小自然数。
定义一个局面\(u\)的SG函数为：
\(SG(u)=\begin{cases}0&E_u=\varnothing\\\operatorname{mex}(SG(E_u))&E_u\ne\varnothing\end{cases}\)

定理1：

\(SG(x)=0\Leftrightarrow x\in P\)

不难发现这就是SG函数与NP态定义的相似性。

游戏的和

给定若干个游戏，每轮玩家可以任选一个游戏进行一次决策，最后无法进行决策的人输。

定理2（Sprague-Grundy定理）：

\(SG(u+v)=SG(u)\operatorname{xor}SG(v)\)

考虑根据拓扑序归纳。
当\(u,v\)中某个局面的出边为空集时显然成立。
那么我们设\(u,v\)的出边分别到达\(a_1,\cdots,a_n\)、\(b_1,\cdots,b_m\)。
那么我们轻松地得到如下两个结论：
\(SG(u)\operatorname{xor}SG(v)\notin\{SG(u+b_i)\}\cup\{SG(a_i+v)\}\)
\([0,SG(u)\operatorname{xor}SG(v))\cup\mathbb Z\subseteq\{SG(u+b_i)\}\cup\{SG(a_i+v)\}\)
命题得证。

定理3：

若\(SG(u)=SG(v)\)，则\(u,v\)等价。

Game

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12296410.html