Sprague-Grundy定理

博主： admin
发布时间：2021 年 02 月 25 日
727次浏览
1 条评论
2707字数
分类：定理

# Sprague-Grundy定理

## 问题引入

初始时有一个由 `+` 组成的字符串，例如 `++++++` 。游戏双方轮流进行如下操作：选取相邻的两个加号，把它们变成减号。若轮到某一方时，字符串中不再有相邻的两个加号，则这一方输掉游戏。

## 策梅洛定理

在`二人`的`有限`且`无平局`游戏中，如果双方皆拥有`完全的资讯`，并且`运气因素并不牵涉在游戏中`，那先行或后行者当一必有一方有`必胜/必不败`的策略。

对于游戏的任何一个状态要么先手有必胜策略，要么后手有必胜策略，分别称为`胜态`、`败态`。

显然上面的游戏满足策梅洛定理的条件。

### 证明

* 对于终局，可以根据游戏规则判断先手(面对此状态的玩家)的胜负。
* 对于非终局状态 A ，若 A 的所有次态均为胜态，那么 A 是败态；否则 A 是胜态，并且获胜的策略就是选取败态留给对方。由于游戏是有限的，那么递归可以结束。

## 状态的组合

一个状态可以由一些`相互独立`的子状态组成，如果可以通过子状态的胜负推出母状态的的胜负，那么效率将大大提高。

### 前提

上面的游戏还有3个特征，也是下文讨论的前提：

* 游戏双方可以采取的行动是相同的
* 游戏双方的目标是相同的
* 走最后一步者胜利

### 败态 + 败态

两个败态的组合是`败态`。先手将一个败态变成胜态，后手只需将胜态再变成败态就可以把两个败态再抛给先手，由于游戏是有限的，并且终局是败态，那么最后一定是先手面对两个败态组成的败态。

### 胜态 + 败态

一个胜态一个败态组成的状态是`胜态`，先手只要将胜态变成败态，后手便处于两个败态组成的败态之中。

### 胜态 + 胜态

面对胜态与胜态的组合，先手不可能选择将其中一个胜态变成败态，因为这样就把胜态与败态组成的胜态留给了后手。所以先手会把一个胜态变成另一个新的胜态，而后手也会执行相同的策略。但是游戏是有限的，总有一玩家只能把一个胜态变成败态，从而将组成的胜态留给对方，但是我们不知道这一步发生在什么时候。因此仅仅知道两个子状态是胜态并`不能确定`母状态的状态。我们还需要关于胜态的更多的性质。

## Sprague-Grundy数

状态 `++` 是最简单的胜态，他的所有次态都是败态。而胜态 `++++` 的次态有 `-++` 和 `+-+` ，分别是胜态和败态。

上述的是两种不同的胜态，像 `++` 和 `+++` 这种只能变成败态的胜态叫做`1级胜态`，而像 `++++` 这种即能变成败态，又能变成1级胜态的胜态，叫做`2级胜态`。类似地，如果一个胜态即能变成败态，又能变成1,2,...,n-1级胜态，我们称之为n级胜态。特别地，`败态叫做0级胜态`。

对于两个同级胜态，先手会将其中一个胜态变成一个级数稍小的胜态(若调高胜态级数，后手可以调回去，在这里不考虑)，而后手会将另一个胜态调整为级数相同的胜态，这样又把同级胜态抛给了先手，最终先手不得不将其中一个胜态变成败态，从而后手获胜，因此`两个同级胜态的组合是败态`。对于两个不同级胜态，先手只需将高级胜态调整为与低级胜态同级，便将两个同级胜态组成的败态留给了后手，因此`两个不同级状态的组合是胜态`。

实际上，上面定义胜态的级数就是 Sprague-Grundy 数(简称 SG 数)，其定义如下：

$$
SG(A)=mex\{SG(B)|A \rightarrow B\}

其中 A、B 代表状态，mex(minimal excludant) 表示不属于集合的最小非负整数，例如：$mex\{0,1,3\}=2$ 。

## 状态组合时的SG数运算

到这里，我们已经知道了由两个互相独立的子状态组成的母状态的胜负，但是对于三个状态呢。我们可以先将其中两个状态看出一组，求出母状态的 SG 数，然后再与第三个状态运算即可确定胜负。由此可见我们不仅需要知道两个状态组成的母状态的胜负还需要知道母状态的 SG 数。

定义 $a \oplus b=c$ 表示由SG数分别为 a、b 的子状态构成的母状态的 SG 数为 c ，那么：

* 败态与败态组合为败态，$0\oplus0=0$
* 胜态与败态组合为同级胜态，$a\oplus0=a$
* 同级胜态组合为败态，$a\oplus a=0$
* $2\oplus1$ 的所有次态为 $1\oplus1=0,0\oplus1=1,2\oplus0=2$，因此 $2\oplus1=3$
* $3\oplus1$ 的所有次态为 $2\oplus1=3,1\oplus1=0,0\oplus1=1,3\oplus0=3$，因此 $3\oplus1=2$
* $3\oplus2$ 的所有次态为 $3,2,2,3,0$，因此 $3\oplus2=1$

显然，$\oplus$ 是`异或`操作，且 $SG(A+B)=SG(A)\oplus SG(B)$，证明略(数学归纳法)。当母状态由许多子状态组成时，母状态的SG数是这些子状态的异或值。

## 代码

```python
mem = {}
def SG(A):                      # 求状态A的SG数
    if A not in mem:
        S = sub_states(A)       # sub_states(A)将A尽可能细致地拆分成子状态
        if len(S) > 1:          # A可以拆分，用子状态的异或求其SG数
            mem[A] = reduce(operator.xor, [SG(B) for B in S])
        else:                   # A不可拆分，根据定义求其SG数
            mem[A] = mex(set(SG(B) for B in next_states(A)))
                                # next_states(A)返回A的所有次态
                                # 注意这条语句蕴含了“终局态的SG数为0”
    return mem[A]
```

最后修改：2021 年 02 月 25 日 06 : 52 PM

如果觉得我的文章对你有用，请随意赞赏