0%

算法 - 博弈问题

基本思想

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

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