算法 - 博弈问题

基本思想

游戏可以等效为一个有向图，每一个状态相当于图中的一个节点，而可能的状态转移是图中的边。如果必胜态的后继中存在必败态，而必败态的后继全是必胜态。

SG函数

\[ SG(u) = mex\{ SG(v)|u \to v \} \] 函数值为 0 代表必败态，不为 0 代表必胜态。（也就是说，0 只能转移到非 0，而非 0 一定能转移到 0。） 一个组合游戏的 SG 和等于所有子游戏的异或和。 ## Anti-SG 和 SJ 定理 Anti-SG 游戏： 走完最后一步的一方输，也就是说，SG 为 0 的局面不一定为终止局面。

SJ 定理： 对于 Anti-SG 游戏，如果游戏结束的条件是所有子游戏的 SG 值均为 0 时，那么先手必胜的条件是： SG 值不为零 xor 没有子游戏 SG 值大于1

Every-SG

每一个非终止状态的子游戏必须进行操作。 \[ step(v) = \begin{cases} 0, & \text{$v$ 为终止状态} \\ max\{step(u)|SG(u)=0\}+1, & \text{$SG(v)>0$} \\ min\{step(u)\}, & \text{$SG(v)=0$} \\ \end{cases} \] 先手必胜的充要条件：所有子游戏中最大的 step 值为奇数

Green Hackenbush

图上的删边游戏，过于复杂，自行搜索。

题目

解题思路

• 试图将问题转换成 Nim 游戏计算 SG 和，确定边界状态的 SG 值（不存在时为 -1）。

• SG 计算过于复杂时打表找规律，或者和自己玩一玩找到一种必胜策略并进行推广。

zero-move

在 Nim 游戏的基础上增加一个规则，每一堆石子可以进行一次空操作（与玩家无关）。这道题看似同一次状态可以多次抵达，实则不然。同样多的石子，根据经历过空操作与否可以看做两个状态。
新的 SG 值：

n	1	2	3	4	5	6	...
SG	2	1	4	3	6	5	...