【转载】SG定理

转载自:https://blog.csdn.net/PhilipsWeng/article/details/48395375

SG定理


初始问题

给定N堆石子,每堆有Ai个石子。两个人轮流操作,每轮可以选一堆石子来取石子,可以取完,但不能不取。无法操作者输。问先手是否必胜。

SG定理

相信很多人都已经知道了这个定理。

假设现在有一个有向无环的游戏图G(V,E),若(i,j)E则表示状态i可以转移到状态j.

我们还要定义必胜态与必败态的概念。
必胜态表示,从当前状态可以转移到一个必败态。
必败态表示,从当前状态无法转移到一个必败态。

我们规定整个图不存在平局态。

SGX

SGX=MEX({SGY,Y|(X,Y)E})

MEX是一个作用于集合的函数。MEX(S)的值为最小的自然数b,满足bS.

最终若SGX为0,则X为一个必败态。否则X为必胜态。

证明

我们归纳的来证明这个定理。

假设对于之前的状态这是成立的。
现在新增了一个状态X.
SGX>0,则必然存在一个Y:(X,Y)E 满足SGY=0.因为SGY=0,所以Y为一个必败态。因此X为一个必胜态。

SGX=0,则y:(X,Y)E,SGY>0.也就是说他只能转移到必胜态。因此X为一个必败态。

最终由于没有出边的状态Q为必败态,SGQ=0.所以归纳成立。

回归原问题

好像有了上面的定理我们就能做了???其实是不能的。

因为原问题中我们的一个状态X=(A1,A2,,AN).状态数实在是太多了。根本不可能存的下来。

但是假如只有一堆石子的话,
SG(A1)=MEX({SG(j),j<A1})

最终化简得SG(A1)=A1.

然而并没有什么卵用

原问题是多个堆。但是两两之间没有什么影响啊??能不能缩?

Another theorem

设一个游戏间的运算+,X+Y表示将XY复合。即这两个游戏相互不影响,但在同一个游戏X+Y中。

设游戏X=X1+X2++XN
表示xor.
SGX=SGX1SGX2SGXN.

Why?

Proof

首先考虑游戏X具有的转移。
X=X1+X2++XN.
因为一次只能选择一个单独的游戏进行,所以X具有的转移其实是
X1+X2++Xi++XN,1iN.
其中XiXi的一个转移。

FXX的转移集合。

b=SGX1SGX2SGXN.

那么为了证明SGX=b,我们事实上只需要证明两条性质。

  1. aN,a<b,xFxSGX=a.

  2. xFxSGXb

证明第一条性质

我们同样需要采用归纳法来证明。

aN,a<b,xFxSGX=a.

d=b  a,d的最高位为k.则必存在SGXi的第k位为1.

因为SGXi  d<SGXi,所以必然存在XFXi,SGX=SGXi  d.

因为d=b  aa=b  d.即

a=SGX1SGX2SGXidSGXN

又因为存在XFXi,SGX=SGXid,

a=SGX1SGX2SGXSGXN

因为XFXi,所以X1+X2++X++XNFX.

所以
aN,a<b,xFxSGX=a.

证明第二条性质

我们现在用反证法。

假设xFxSGX=b

那么

SGX=SGX1SGX2SGXN

X=X1+X2++Xi++XN
X=X1+X2++Xi++XN
那么

SGX=SGX1SGX2SGXiSGXN

那么就有SGXi=SGXi

因为

SGXi=MEX(SGXi)

SGXiSGXi

矛盾

所以不存在SGX=b

得证。

上一篇:c#-从不同项目继承基类的SetupFixture(nunit)


下一篇:如何用NUnit(C#)替换MSTest