Nim游戏与Sprague-Grundy 函数

注：本文内容大量借鉴 hihocoder 平台对nim游戏的介绍，包括 1163, 1172 和 1173。

我们先从几个问题引入Nim游戏，介绍其特点，然后循序渐进重复其推导过程，最后介绍Sprague-Grundy函数及其应用。

问题

大家先来看看几个小游戏哈：

地上有两堆石子，两人轮流从一堆中取走任意数量石子，至少1枚，最后没有石子可取则判负。已知石子初始数量为 (x_1, x_2)，问双方采用最佳策略下，先手必胜还是必败？
在问题1的基础上，若有(n)堆石子，数量分别为 (x_1, x_2, ... ,x_n)，同样的规则下，如何判断先手必胜还是必败呢？
与此类似的有，台阶上有(n)枚硬币，每次可以将任意一枚硬币下移，最后所有硬币都在地面时则失败。

这些问题都有一个特点，两名选手的操作只取决于游戏局面，与选手无关。明显与之不同的例子如象棋，红黑双方只能操作己方棋子。如果我们将每个游戏局面想象成一个状态节点，每个节点通过合法操作转换的状态节点用有向边连接，就得到了一个有向图。

Nim游戏

我们将此类游戏的状态空间抽象为有向图之后，可以将节点分为两类：

p-position：先手必败
n-position：先手必胜

判断的标准是：

没有后继节点的是 p-position ；
后继节点存在 p-position 节点的是 n-position；
后继节点均为 n-position 节点的是 p-position.

于是我们可以从终止状态按照上述规则递推出所有状态的类型，得出结论。但是时间复杂度较大！对于上述问题1,2 我们有更简单的结论：

当前状态为 p-position 当且仅当 $ x_1 oplus x_2 oplus ... oplus x_n = 0, oplus$ 为异或操作。

证明过程不再赘述，归纳思路大致为，(forall i, x_i=0) 是p-position ；若当前满足异或为零的条件，无论当前采用何种操作后，局面异或值不会为零，且对方可以采用某种操作是异或值变为零，这样当前选手面对的局面始终是零，则先手必败；若当前局面异或值不为零，存在操作使得异或值为零。

这样我们就得到了一类问题的判断方法，不再需要递推求解。然而这里还有些更复杂的问题。

Sprague-Grundy 函数

更复杂的问题：

地上有 (n) 堆石子，两人轮流从一堆中取走任意数量石子，至少1枚，或者将一堆石子分为两堆，最后没有石子可取则判负。问双方采用最佳策略下，先手必胜还是必败？
地上有 (n) 堆石子，两人轮流从一堆中取走石子数量 (a_1=1, a_2,...,a_k) ，最后没有石子可取则判负。(当 (n=1, {a_n}={1,2,3})时，大家应该见过这个问题哈)

（注：下面大幅摘自hihocoder )

上面两个问题与Nim游戏有同样的性质，依然可以将状态空间分为 p-position 和 n-position，但是没有那么简单的判断方法。这里我们引入Sprague-Grundy 函数，定义如下：

若当前局面x为终结局面，则sg值为0。
若当前局面x非终结局面，其sg值为：sg(x) = mex{sg(y) | y是x的后继局面}。
mex{a[i]}表示a中未出现的最小非负整数。举个例子来说：mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2

可以发现，若一个局面x为P局面，则有sg(x)=0；否则sg(x)>0。同样sg值也满足N、P之间的转换关系：

若一个局面x，其sg(x)>0，则一定存在一个后续局面y，sg(y)=0。
若一个局面x，其sg(x)=0，则x的所有后续局面y，sg(y)>0。

sg函数中还有一个非常好用的定理，叫做sg定理：

对于多个单一游戏，X=x[1..n]，每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。即：sg(X) = sg(x[1]) xor sg(x[2]) xor … xor sg(x[n])

要证明这一点我们只要证明：

假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，对于任意一个0 <= B < A，总存在一个X的后续局面Y，使得sg(Y)=B。
假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A，不存在一个X的后续局面Y，使得sg(Y) = A。

先证明(1)：假设M = A xor B，设M表示为二进制之后最高位的1为第k位。所以A的第k位为1，B的第k位为0。又因为A的第k位为1，至少存在一个i，sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M < sg(x[i])，即一定通过某个操作使x[i]变为x[i’]，且sg(x[i’]) = sg(x[i]) xor M。那么：sg(x[i’]) xor Other = sg(x[i]) xor M xor Other = M xor A = B.下证明(2)：若sg(X) = A，sg(Y) = A。不妨设我们改变的游戏为x[i]，则X=x[1..n], Y=x[1…i’…n]。有sg(x[i]) =sg(x[i’])，产生矛盾，所以sg(Y)不可能等于A。

回到上面的问题1，局面上一共有N堆石子，每一次我们只能改变一堆石子。那么我们可以将每一堆石子看作一个单一游戏。对于一堆石子，若该堆石子数量为0，就达到了终止状态，所以sg(0) = 0。若其石子数量为k，接下来我们从k=1开始枚举递推每一个sg(k)。对于k，其可能的后继状态有：

不分堆：石子数量为k’=0..k-1，则sg(k’)
分堆：石子变为2堆，数量为(1,k-1),(2,k-2),…,(k-1,1)。设第一堆的石子数量为i，则sg值为sg(i) xor sg(k-i)。(这里用到了sg定理)

那么可以推算出sg(k) = mex{sg(0), sg(i), sg(i) xor sg(k - i) | i = 1..k-1}。对于N堆石子，其sg值则为这N堆各自的sg值异或和。