在之前,我们初步了解了一下SG函数与SG定理。
今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理
首先从最基本的Anti-Nim游戏开始
Anti-Nim游戏是这样的
有两个顶尖聪明的人在玩游戏,游戏规则是这样的: 有n堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),
拿走最后一个石子的人失败
。问谁会胜利
Anti-Nim游戏与Nim游戏唯一的不同就是两人的胜利条件发生了改变,不过这并不影响我们对结论的推导
对于这个游戏,先手必胜有两种情况
每
堆石子都只有一个,且游戏的SG值为
0至少
一堆石子多于一个,且游戏的SG值不为
0粗略的证明一下
游戏大概可以被分为3种情况
经过分析不难发现,先手可以对数量大于1的那堆石子下手脚,从而构造出后手必败的状态
这一步的结论与Nim游戏非常相似,同时它们的证明也非常相似,大概就是从异或和为\(0\)的状态无论怎样都会变为异或和不为0的状态,反过来从异或和不为0的状态总有一步能到达异或和为\(0\)的状态
按照我们学习SG函数的思路,我们是否可以把Anti-Nim游戏推广开来呢?
答案是肯定的
定义Anti-SG游戏
同时我们定义SJ定理
对于Anti-SG游戏,如果我们规定当局面中所有单一游戏的SG值为0时,游戏结束,则先手必胜当且仅当
证明与SG函数类似,
不追求完美的可以从DAG上归纳
追求完美的可以用模仿棋证明出该游戏的等价性然后推出该游戏是可数集合然后通过计算推出在模2意义下线性空间的基可以为nim(0),nim(1)最后归纳证明一个后继是若干Anti-nim游戏的游戏等价于mex(S)