最优策略？最优策略！——浅谈 SG 函数

前言

本文内容来自于我之前的一个 PPT 和以前写的一个学习笔记，我将内容做了一个整合然后放了上来，部分内容网上可能出现过，作者是我。

如果你读完一遍后感觉对文章的内容还不太了解，可以先读一读参考资料 [1] 中提到的这篇文章（张一飞《由感性认识到理性认识——透析一类搏弈游戏的解答过程》），再选择阅读本文。

一道小学奥数题

现在有 1 堆 20 个石子，先后手轮流操作，每人能选择一个非空的石子堆，取 1 颗或 2 颗石子，谁无法操作谁就输了，问先手是否有必胜策略？

这是一道简单的小学奥数题，让我们把题目改改：现在有 2 堆石子，第一堆有 20 个石子，第二堆有 21 个石子，先后手轮流操作，每人能选择一个非空的石子堆，取 1 颗或 2 颗石子，谁无法操作谁就输了，问先手是否有必胜策略？

更进一步地：现在有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个，游戏规则同上，问先手是否有必胜策略？

你还会做吗？

定义！

在刚刚这个游戏中，若只有 1 堆石子，并且现在还有 5 个石子没有被取，那么我们称这个局面为 $G = (5)$。

我们称这个局面 $G$ 的前继状态为 $G’=(6)$ 和 $G’’=(7)$，因为局面 $G’$ 和局面 $G’’$ 可以通过一次操作得到局面 $G$。

类似的，我们称局面 $G$ 的后继状态为 $g’=(3)$ 和 $g’’=(4)$，因为局面 $G$ 可以通过一次操作得到局面 $g’$ 和局面 $g’’$。

如果你理解了的话，我们再来看看局面的拆分和组合。

如果有 3 堆石子，并且它们在一开始的个数分别为 11、15、19，那么我们称这个局面 $G = (11, 15, 19)$，它可以被拆分成两个子局面 $g_1=(11, 19)$、$g_2=(15)$。

当然，你也可以把它拆成 $g_1=(11)$、$g_2=(15)$、$g_3=(19)$，拆法还有很多，在这里就不一一列举出来了。

对于上面的这种拆法，我们称 $g_1+g_2+g_3 = G$。

那么，我们能否通过子局面的胜负情况来判断出原局面的胜负情况呢？

不行。

但我们有另一种方法！

变！问题的转换！

在了解了定义后，我们再来看两个显而易见的结论：

1. 如果一个局面 $G$ 是必败的，那么对于它所有的前继 / 后继局面 $G’$，$G’$ 都是必胜的（对手怎么样都赢，找不到破绽）

2. 如果一个局面 $G$ 是必胜的，那么对于它所有的前继 / 后继局面 $G’$，至少有一个局面 $G’$ 是必败的（我可以抓住对手的至少一个破绽取胜）

是不是感觉有点意思？

进入正题吧！

对于一个局面 $G$，我们称它的 SG 函数值为：

$$SG(G) = \text{mex}\{SG(G')\}$$

其中局面 $G’$ 为局面 $G$ 的后继状态。

是不是简短而有趣？

你可能要问了，$\text{mex}$ 是个啥？

$\text{mex}$ 运算是一个施加于集合的运算，其值为 最小的不在集合中的非负整数。

例如 $\text{mex}\{0, 1, 3\} = 2$、$\text{mex}\{1, 3, 4, 5, 6\} = 0$。

一般来说（有特例），若一个局面 $G$ 的 $SG$ 函数值 $SG(G)$ 不为 0，那么它必胜，否则它必败。可以根据上面所讲到的两个结论来理解。

一个更有趣的性质

对于一个局面 $G$，它的 SG 函数值 $SG(G)$ 满足：

$$SG(G) = SG(g_1) ⊕ SG(g_2) ⊕ ... ⊕ SG(g_n)$$

其中局面 $g_1 + g_2 + … + g_n = G$。

其中 $⊕$ 为异或符号，在 C++ 语言中用“^”来表示。

伪代码

例题：给你 $n$ 堆石子，第 $i$ 堆石子的个数为 $a_i$，并给出你一个大小为 $m$ 的集合 $\{g_1, g_2, …, g_n\}$。

先后手轮流操作，每次可以取的石子个数要在集合 $\{g_1, g_2, …, g_n\}$ 中，谁无法操作谁就输了，问你先手是否有必胜策略。

对于这个例题的伪代码如下：

int SG ()
	memset(f, 0) // 清空储存 SG 函数值的数组， 
	//其中 f[i] 表示若只有一堆石子，并且这一堆石子的个数为 i， 
	//那么先手是否有必胜策略 
	for i : 1 ~ n
		memset(book, 0);//book 数组的作用是算出 mex 值 
		for j : 0 ~ m - 1
			if g[j] > i//因为 i 小于 g[j]， 
					   //所以显然不能取 g[j] 个， 
					   //因此要 continue 掉， 
				continue 
			book[i - g[j]] = true
		for j : 0 ~ maxN - 1//这个循环是用来求 mex 的，
							//其中 maxN 表示的是单堆石子个数的最大值 
			if !book[j]
				f[i] = j
				break
int main ()
	SG()
	read(n)
	read(a[1] ~ a[n])
	read(m)
	read(g[1] ~ g[m])
	if (f[a[1]] xor f[a[2]] xor ... f[a[n]])
		printf "1"//先手必胜
	else
		printf "0"//先手必败 

例题 & 题解

E.g.1 Luogu P2197 【模板】nim游戏

可以直接暴力求出 SG 函数值，然后判断一下给定的每堆石子的 SG 函数值的异或和是否为 0 即可。

也可以打个表，发现石子个数为 $i$ 的一堆石子的 SG 函数值为 $i$，于是就直接判断一下每堆石子的个数的异或和是否为 0 即可。

对于打表找 SG 函数的规律，是一个博弈论中常用的套路。

E.g.2 HDU P1848 Fibonacci again and again

做法类似于 E.g.1 中的第一种做法。

E.g.3 HDU P2897 邂逅明下

做法类似于 E.g.1 中的第二种做法。

练习题

• HDU 1847 Good Luck in CET-4 Everybody!

• POJ P2425 A Chess Game

• Luogu P6639 「JYLOI Round 1」让

参考资料

[1] 由感性认识到理性认识——透析一类搏弈游戏的解答过程。

[2] 组合游戏略述——浅谈SG游戏的若干拓展及变形。

[3] 博弈论。

[4] SG函数。

[5] hdu 1848Fibonacci again and again。

[6] 专题训练之博弈。

[7] 博弈by高嘉煊。

[8] sg函数入门题。

[9] 【转】博弈-翻硬币游戏。

[10] 博弈:关于SG函数的一些心得（知识总结+叙述证明+例题）。

[11] POJ2425（树形，无向无环图博弈）。

后记

前言 中提到的 PPT 我放在腾讯微云共享组中了，有需要的请自取。

邀请链接：https://share.weiyun.com/0BgMrcWf-g ，因为是给班级同学讲的，所以内容可能比较基础。

SG 函数与“游戏的和”的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的 SG 函数，然后全部异或起来就得到了原游戏的 SG 函数，就可以解决原游戏了。——百度百科