SG潘精灵连线达人是完全随机吗?

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

题目限制和Nim游戏一样
但是拿到最后一个M&M的人输

这类特殊的游戏就叫做Anti_SG

  1. 决策集合為空的操作者胜
  2. 其余规则与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的子游戏的SG值的Nim和为X
因为不为0,那么现在如果X=0 0 于是变为游戏的SG值为0而此时至少存在两个子游戏的SG值超过1

只有一个子游戏的SG值超過1,然后其余有偶数个1

如果只有一个子游戏的SG值超过1然后其余有奇数个1

这样证明了必胜态至少有一个后继状态为必败态

所有SG值不超过1,那么有奇数个1先手就必败无论如何都只能转移到有偶数个1的情况

如果有至少两个子游戏的SG值超过1,那么无论如何都会转移到一个先手必勝局面(有至少一个SG值超过1游戏的SG值不为0)

如果只有一个子游戏的SG值超过1,这是不可能发生的

我要回帖

更多关于 连线达人 的文章

 

随机推荐