sg游戏官网,sg游戏官网

sg游戏官网,sg游戏官网

sg游戏官网,sg游戏官网,博弈论进阶之Anti

在上一节中,我们初步了解了一下SG函数与SG定理。

今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理

首先从最基本的Anti-Nim游戏开始

Anti-Nim游戏是这样的

有两个顶尖聪明的人在玩游戏,游戏规则是这样的:
有\(n\)堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),拿走最后一个石子的人失败。问谁会胜利

Anti-Nim游戏与Nim游戏唯一的不同就是两人的胜利条件发生了改变,不过这并不影响我们对结论的推导

对于这个游戏,先手必胜有两种情况

当每堆石子都只有一个,且游戏的SG值为\(0\) 至少一堆石子多于一个,且游戏的SG值不为\(0\)

粗略的证明一下

游戏大概可以被分为\(3\)种情况

每堆只有一个石子 当异或值为\(0\)时,先手必胜 当异或值不为\(0\)时,先手必败 只有一堆石子数大于1,先手必胜

经过分析不难发现,先手可以对数量大于1的那堆石子下手脚,从而构造出后手必败的状态

存在至少两堆石子数大于1 当异或和为0时,先手必败 当异或和不为0时,先手必败

这一步的结论与Nim游戏非常相似,同时它们的证明也非常相似,大概就是从异或和为\(0\)的状态无论怎样都会变为异或和不为\(0\)的状态,反过来从异或和不为\(0\)的状态总有一步能到达异或和为\(0\)的状态

按照我们学习SG函数的思路,我们是否可以把Anti-Nim游戏推广开来呢?

答案是肯定的

定义Anti-SG游戏