Nim游戏和SG函数
Nim游戏和SG函数
一、 Nim 游戏
重点结论：对于一个 Nim
游戏的局面
(a1,a2,…,an)
，它是
P-position
当且仅当
a1^a2^…^an=0
，其中
^
表示位异或
(xor)
运算 。
Nim 游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论，由这个游戏开始了解博弈论恐怕是最合适不过了。
Nim 游戏是组合游戏
(Combinatorial Games)
的一种，准确来说，属于
“Impartial Combinatorial Games”
（以下简称
ICG
）。满足以下条件的游戏是
ICG
（可能不太严谨）：
1
、有两名选手；
2
、两名选手交替对游戏进行移动
(move)
，每次一 步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；
3
、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮 到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素；
4
、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非
ICG
。例如 象棋就不满足条件
3
，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。
通常的 Nim
游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是
“
选择一堆石子并拿走若干颗（不能不拿）
”
，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
这 游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对 手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多 的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子 ……
好像已经很 难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。
定 义 P-position
和
N-position
，其中
P
代表
Previous
，
N
代表
Next
。直观的说，上一次
move
的人有必胜策略的局面是
P- position
，也就是
“
后手可保证必胜
”
或者
“
先手必败
”
，现在轮到
move
的人有必胜策略的局面是
N-position
，也就是
“
先手可保证必胜
”
。更严谨的定义是：
无法进行任何移动的局面（也就是
terminal position
）是
P-position
；
可以移动到
P-position
的局面是
N-position
；
所有移动都导致
N-position
的局面是
P-position
。
按照这个定义，如果局面不可能重现，或者说 positions
的集合可以进行拓扑排序，那么每个
position
或者是
P-position
或者是
N-position
，而且可以通过定义计算出来。
以 Nim
游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个
P-position
，下面我们依靠定 义证明一下
(3,3)
是一个
P
是一个
P
是一个
P-position
。首先
(3,3)
的子局面（也就是通过合法移动可以导致的局面）有
(0,3)(1,3) (2,3)
（显然交换石子堆的位置不影响其性质，所以把
(x,y)
和
(y,x)
看成同一种局面），只需要计算出这三种局面的性质就可以了。
(0,3)
的子局面有
(0,0)
、
(0,1)
、
(0,2)
，其中
(0,0)
显然是
P-position
，所以
(0,3)
是
N-position
（只要找到 一个是
P-position
的子局面就能说明是
N-position
）。
(1,3)
的后继中
(1,1)
是
P-position
（因为
(1,1)
的唯一子局 面
(0,1)
是
N-position
），所以
(1,3)
也是
N-position
。同样可以证明
(2,3)
是
N-position
。所以
(3,3)
的所有 子局面都是
N-position
，它就是
P-position
。通过一点简单的数学归纳，可以严格的证明
“
有两堆石子时的局面是
P-position
当且 仅当这两堆石子的数目相等
”
。
根据上面这个过程，可以得到一个递归的算法 ——
对于当前的局面，递归计算它的所有子局面的性质，如果存在某 个子局面是
P-position
，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用
DP
或者记忆化搜索的 方法以提高效率（简单的博弈问题想到这一步就可以了）。但问题是，利用这个算法，对于某个
Nim
游戏的局面
(a1,a2,…,an)
来说，要想判断它 的性质以及找出必胜策略，需要计算
O(a1a2…*an)
个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断
Nim
游戏的局面的性质的方法。
直接说结论好了。 (Bouton’s Theorem)
对于一个
Nim
游戏的局面
(a1,a2,…,an)
，它是
P-position
当且仅当
a1^a2^…^an=0
，其中
^
表示异 或
(xor)
运算。怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂，基本上就是按 照两种
position
的证明来的。
根据定义，证明一种判断 position
的性质的方法的正确性，只需证明三个命题：
1
、这个判断将所有
terminal position
判为
P-position
；
2
、根据这个判断被判为
N-position
的局面一定可以移动到某个
P-position
；
3
、根据这个判 断被判为
P-position
的局面无法移动到某个
P-position
。
第一个命题显然， terminal position
只有一个，就是全
0
，异或仍然是
0
。
第 二个命题，对于某个局面 (a1,a2,…,an)
，若
a1^a2^…^an!=0
，一定存在某个合法的移动，将
ai
改变成
ai'
后满足
a1^a2^…^ai’^…^an=0
。不妨设
a1^a2^…^an=k
，则一定存在某个
ai
，它的二进制表示在
k
的最高位上是
1
（否则
k
的 最高位那个
1
是怎么得到的）。这时
ai^k<ai
一定成立。则我们可以将
ai
改变成
ai’=ai^k
，此时
a1^a2^…^ai’^…^an=a1^a2^…^an^k=0
。
第三个命题，对于某个局面 (a1,a2,…,an)
，若
a1^a2^…^an=0
，一定不存在某个合法的移动，将
ai
改变成
ai'
后满足
a1^a2^…^ai’^…^an=0
。因为异或运算满足消去率，由
a1^a2^…^an=a1^a2^…^ai’^…^an
可以得 到
ai=ai'
。所以将
ai
改变成
ai'
不是一个合法的移动。证毕。
根据这个定理，我们可以在 O(n)
的时间内判断一个
Nim
的局面的性质，且如果它是
N-position
，也可以在
O(n)
的时间内找到所有的必胜策略。
Nim
问题就这样基本上完美的解决了。
二、Sprague-Grundy 函数
上一期的文章里我们仔细研究了 Nim
游戏，并且了解了找出必胜策略的方法。但如果把
Nim
的规则略加改变，你还能很快找出必胜策略吗？比如说：有
n
堆石子， 每次可以从第
1
堆石子里取
1
颗、
2
颗或
3
颗，可以从第
2
堆石子里取奇数颗，可以从第
3
堆及以后石子里取任意颗
……
这时看上去问题复杂了很多，但相信你如果 掌握了本节的内容，类似的千变万化的问题都是不成问题的。
现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶 点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有 Impartial Combinatorial Games
的抽象模型。也就是说，任何一个
ICG
都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个
“
有向图游戏
”
。下 面我们就在有向无环图的顶点上定义
Sprague-Garundy
函数。
首先定义 mex(minimal excludant)
运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如
mex{0,1,2,4}=3
、
mex{2,3,5}=0
、
mex{}=0
。
对于一个给定的有向无环图，定义关于图的每个顶点的 Sprague-Garundy
函数
g
如下：
g(x)=mex{ g(y) | y
是
x
的后继
}
。
来 看一下 SG
函数的性质。首先，所有的
terminal position
所对应的顶点，也就是没有出边的顶点，其
SG
值为
0
，因为它的后继集合是空集。然后对于一个
g(x)=0
的顶点
x
，它的所有后继
y
都满足
g(y)!=0
。对于一个
g(x)!=0
的顶点，必定存在一个后继
y
满足
g(y)=0
。
以上这三句话表明，顶点 x
所代表的
postion
是
P-position
当且仅当
g(x)=0
（跟
P-positioin/N-position
的定义的那三句话是完全对应的）。我们通过计算有向无环图 的每个顶点的
SG
值，就可以对每种局面找到必胜策略了。但
SG
函数的用途远没有这样简单。如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋 子，而是有
n
枚棋子，每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？
让我们再来考虑一下顶点的 SG
值的意义。当
g(x)=k
时， 表明对于任意一个
0<=i<k
，都存在
x
的一个后继
y
满足
g(y)=i
。也就是说，当某枚棋子的
SG
值是
k
时，我们可以把它变成
0
、变成
1
、
……
、变成
k-1
，但绝对不能保持
k
不变。不知道你能不能根据这个联想到
Nim
游戏，
Nim
游戏的规则就是：每次选择一堆数量为
k
的石子，可以把它变 成
0
、变成
1
、
……
、变成
k-1
，但绝对不能保持
k
不变。这表明，如果将
n
枚棋子所在的顶点的
SG
值看作
n
堆相应数量的石子，那么这个
Nim
游戏的每个必 胜策略都对应于原来这
n
枚棋子的必胜策略 。
对于 n
个棋子，设它们对应的顶点的
SG
值分别为
(a1,a2,…,an)
，再设局面
(a1,a2,…,an)
时的
Nim
游戏的一种必胜策略是把
ai
变成
k
，那么原游戏的一种必胜策略就是把第
i
枚棋子移动到一个
SG
值为
k
的顶点。这听上去 有点过于神奇
——
怎么绕了一圈又回到
Nim
游戏上了。
其实我们还是只要证明这种多棋子的有向图游戏的局面是 P-position
当且仅当所有棋子所在的位置的
SG
函数的异或为
0
。这个证明与上节的
Bouton’s Theorem
几乎是完全相同的，只需要适当的改几个名词就行了。
刚才，我为了使问题看上去更容易一些，认为 n
枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子在一个有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。
所 以我们可以定义有向图游戏的和 (Sum of Graph Games)
：设
G1
、
G2
、
……
、
Gn
是
n
个有向图游戏，定义游戏
G
是
G1
、
G2
、
……
、
Gn
的和
(Sum)
，游戏
G
的移动规则是：任选一个子游戏
Gi
并移动上面的棋子。
Sprague-Grundy Theorem
就是：
g(G)=g(G1)^g(G2)^…^g(Gn)
。也就是说，游戏的和的
SG
函数值是它的所有子游戏的
SG
函数值的异或。
再考虑在本文一开头的一句话：任何一个 ICG
都可以抽象成一个有向图游戏。所以
“SG
函数
”
和
“
游戏的和
”
的概念就不是局限于有向图游戏。我们给每个
ICG
的每个
position
定义
SG
值，也可以定义
n
个
ICG
的和。所以说当我们面对由
n
个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的
SG
值的方法，就可以把这些
SG
值全部看成
Nim
的石子堆，然后依照找
Nim
的必胜策略的方法来找这个游戏的必胜策略了！
回到本文开头的 问题。有 n
堆石子，每次可以从第
1
堆石子里取
1
颗、
2
颗或
3
颗，可以从第
2
堆石子里取奇数颗，可以从第
3
堆及以后石子里取任意颗
……
我们可以把它看作
3
个 子游戏，第
1
个子游戏只有一堆石子，每次可以取
1
、
2
、
3
颗，很容易看出
x
颗石子的局面的
SG
值是
x%4
。第
2
个子游戏也是只有一堆石子，每次可以取奇数 颗，经过简单的画图可以知道这个游戏有
x
颗石子时的
SG
值是
x%2
。第
3
个游戏有
n-2
堆石子，就是一个
Nim
游戏。对于原游戏的每个局面，把三个子游戏 的
SG
值异或一下就得到了整个游戏的
SG
值，然后就可以根据这个
SG
值判断是否有必胜策略以及做出决策了。其实看作
3
个子游戏还是保守了些，干脆看作
n
个 子游戏，其中第
1
、
2
个子游戏如上所述，第
3
个及以后的子游戏都是
“1
堆石子，每次取几颗都可以
”
，称为
“
任取石子游戏
”
，这个超简单的游戏有
x
颗石子的
SG
值显然就是
x
。其实，
n
堆石子的
Nim
游戏本身不就是
n
个
“
任取石子游戏
”
的和吗？
所以，对于我们来说， SG
函数与
“
游戏的和
”
的概念不是让我们去组合、制造稀奇古怪的游戏，而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的
SG
函数，然后全部异或起来就得到了原游戏的
SG
函数，就可以解决原游戏了。