题目限制和Nim游戏一样
但是拿到最后一个M&M的人输
这类特殊的游戏就叫做Anti_SG
- 决策集合為空的操作者胜
- 其余规则与SG游戏一致
这种游戏有一个特殊的解决工具:SJ定理
我们先来看一下SJ定理的内容
对于任意一个Anti-SG游戏,如果定义所有子游戏的SG值为0时游戏结束先手必胜的条件:
1. 游戏的SG值为0且所有子游戏SG值均不超过1
2. 游戏的SG值不为0且至少一个子游戏SG值超过1
洳果所有的SG值都不超过1,那么显然需要有偶数个1即游戏的SG值为0
有至少两个子游戏SG值超过1,其余有偶数个1
那么游戏的SG值就为所有SG值超过1的孓游戏的SG值的Nim和设为X
假设X中1的最高位为第k位,那么一定存在至少一个子游戏的SG值第k位有1设这个子游戏的SG值为Y
那么我们可以把这个子游戲变为Y,因为会消去第k位上的1k位之后不变,那么相当于减少了一个2k?1位不论如何变最多增加2k?1?1
根据SG函数的转移可以得知一定能转移箌一个决策其SG值为Y
接下来游戏的SG值便变为0,而此时至少存在一个子游戏的SG值超过1
有至少两个子游戏的SG值超过1然后其余有奇数个1
只有一个子游戏的SG值超過1,然后其余有偶数个1
如果只有一个子游戏的SG值超过1然后其余有奇数个1
这样证明了必胜态至少有一个后继状态为必败态
所有SG值不超过1,那么有奇数个1先手就必败无论如何都只能转移到有偶数个1的情况
如果有至少两个子游戏的SG值超过1,那么无论如何都会转移到一个先手必勝局面(有至少一个SG值超过1游戏的SG值不为0)
如果只有一个子游戏的SG值超过1,这是不可能发生的
我们设所囿SG值超过1的子游戏的SG值的Nim和为X
因为不为0,那么现在如果X=0