原文:http://blog.sina.com.cn/s/blog_51cea4040100h3l9.html

一、Anti-SG
定义:桌子上有N堆石子,游戏者轮流取石子。
      每次只能从一堆中取出任意数目的石子,但不能不取。
      取走最后一个石子者败。

因为要求是取走最后一个石子的人败,那么,想赢的人,肯定是想,我就要留一个石子让你去取。
所以,我们在考虑条件的时候,就要加上石子数是不是1这个条件了。当然,还有SG函数本身。

贾志豪发明的SJ定理(Sprague Grundy——Jia Zhihao)解决了这个问题。

SJ定理:
对于任意一个Anti-SG游戏,如果我们规定当局面中所有的单一游戏的SG值为0时,游戏结束。
先手必胜当且仅当:(1)游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1;(2)游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

我们提出定理里的两个限制:1、SG函数为不为0。2、有没有某单一游戏的SG函数大于1。
通过这两个限制,我们可以组合出4种情况:
(1)SG==0,有某单一游戏的SG>1。
(2)SG!=0,有某单一游戏的SG>1。(必胜SJ)
(3)SG==0,无某单一游戏的SG>1。(必胜SJ)
(4)SG!=0,无某单一游戏的SG>1。

对于情况(1):
当SG==0,存在某单一游戏的SG>1,因为SG==0,所以一定存在至少两个单一游戏的SG>1。而一次操作只能改变一个单一游戏的SG值,那么,操作后,一定到情况(2)。所以情况(1)是先手必败。

对于情况(2):
当SG!=0时,<1>若只有一个单一游戏的SG>1,我们一定可以通过一次操作,使得剩下的单一游戏一共有奇数个1,这样就先手必胜。<2>若不只一个单一游戏的SG>1,我们可以通过一次操作,使得情况变为SG==0,有某单一游戏的SG>1。对于情况(2)来说,都有子状态是必败状态,所以,情况(2)是先手必胜。

对于情况(3):
当SG==0,并且没有一单一游戏的SG>1,说明这里只存在偶数个1。如果1的个数为0,则先手必胜。如果1个个数大于0,说明一共有偶数个1,依然是先手必胜。

对于情况(4):
当SG!=0,无某单一游戏的SG>1,说明现在有奇数个SG==1,操作有两种。
<1>将某一单一游戏的SG值变成大于1,转移后SG依然不等于0,且有一个单一游戏的SG>1,这就到了情况(2)。
<2>将一个SG==1的转移为SG==0,这样就到了情况(3)。
所以情况(4)下是先手必败。

二、Multi-SG
定义:Multi-SG游戏规定,在符合拓扑原则的前提下,一个单一游戏的后继可以为多个单一游戏。
      Multi-SG其他规则与SG游戏相同。
关于这个,如果ccy没理解错,就相当于POI1999/2000的Stripes那题。
http://blog.sina.com.cn/s/blog_51cea4040100h37e.html

三、Every-SG
定义:Every-SG 游戏规定,对于还没有结束的单一游戏,游戏者必须对该游戏进行一步决策。
      Every-SG 游戏的其他规则与普通SG 游戏相同。

这种类型,可以想成这样,有N组游戏,有N个穿红色衣服的人代表先手,有N个穿蓝色衣服的人代表后手,这个时候,编号相同的人和游戏分到一组游戏,既第i号穿红色衣服人和第i号穿蓝色衣服的人做第i个游戏。游戏开始后,首先所有穿红衣服的人先操作,然后所有穿蓝色衣服的人再操作,这样轮流下去。直到最后还没游戏完的一组,这组如果是红色衣服的人胜利,那么该游戏先手必胜,如果是蓝色衣服的人胜利,就是先手必败。
很明显,Every-SG不仅仅像其他SG那样仅仅跟SG值有关,还与一个游戏的时间长度有关。

如果先手想赢,那么,在做先手必胜的单一游戏时,他肯定是想把战线尽量拉长。在做先手必败的单一游戏时,他肯定是想把游戏尽快结束。

于是我们开一个Step数组。
表示对于先手必胜的单一游戏而言,它最少走好多步胜利。对于先手必败的单一游戏而言,它最多走好多步。
这样,我们只需要看最后所有单一游戏最大的step那组的SG是0还是非0就可以断定是否先手必胜了。

很容易得出:
(u是v的子状态)
step[v] = 0;                 (v为终止状态)
step[v] = max{step[u]} + 1;  (sg[v]>0,sg[u]=0)
step[v] = min{step[u]} + 1;  (sg[v]==0)

现在需要证明两个东西:
(1)先手必胜,step表示的是最少走好多步。
(2)先手必败,step表示的是最多走好多步。

证明(1):
对于v点,先手必胜。先手总是从sg>1的到sg==0,他可以保证自己每次减少的步数为1。对手每次是从sg==0到sg>1,最少将步数减小1,既对方走的min值所取的结点,如果选其他的,步数反而到那步后还要增加。所以,先手必胜,step表示的是最少走好多步。
(反起想,这也是为什么step第三个递推式是用min的原因。)

证明(2):
对于v点,先手必败。先手总是从sg==0到sg>1,他可以保证自己每次减少的步数为1。对手每次是从sg>1到sg==0,对手肯定想让战线拉长,那么他只让步数减少1.所以,先手必败,step表示的是最多走好多步。

这里,式子的推导和证明柔和起来看更有利于理解。
值得注意理解的是,这里的最多和最少并不是绝对的最多最少。
对于(1)(2)而言,都是先手保证自己的操作后,看对手操作而决定最多最少。
而这里的最多最少正好等于step也是我们强制先手每次只减少步数1而得来的。

不过,我们是先手嘛,当然可以多个脑壳决定自己了!!!

贾志豪在证Every-SG时,多证明了一条,就是最大的step为奇数时必胜。
ccy觉得这个虽然好证明,但是何必呢?最多step的那个单一游戏判断下它的SG是不是为0不就可以了吗?
关于step为奇这个,也说一下。
最终状态,sg[v]==0,step[v]==0,为偶。
每个sg[v]!=0的step是由sg[u]==0的step[u]加上1得到,所以为奇。
每个sg[v]==0的step是由下面sg[u]!=0的step[u]加上1得到,所以为偶。
所以,sg[v]!=0的,step为奇。