分析的是什么游戏?
考虑由局面组成的有限有向无环图。边代表合法走法;在同一局面,两名玩家的合法走法相同,不能走的一方落败。这些是有限、无偏、正常玩法的假设:它们排除了无限游戏,不涵盖走法依玩家而异或终局规则不同的游戏。
定义 5.1.1
(Mex 与局面的值)
对非负整数有限集合 , 是不在其中的最小非负整数;特别有 。递归定义局面 的值为
终局的值为零。无环性让我们可以向后定义所有值。
零值与致胜走法
定理 5.1.2
(值为零表示轮到走的一方落败)
在有限的无偏正常玩法游戏中,值为零的局面对轮到走的一方是必败的(双方最佳对弈);值为正的局面是必胜的:该方可走到值为零的局面。
证明
(对游戏图向后归纳)
值为零的局面没有值为零的后继,因为零不在后继值中。值为正的局面有值为零的后继,因为比其 mex 小的每个非负整数都必须出现。然后从终局向后归纳:终局的值为零而且无法走步,所以轮到走的一方落败。若某局面的值为零,它所有后继的值都是正的,由归纳假设,每个后继对下一步的走子者都是必胜的,所以现在走的一方落败。若它的值为正,走的一方可走到值为零的后继,由归纳假设,该局面对在那里走子的一方是必败的。此结论使用了上述正常玩法规则。
反例模式
Mex 不是走法数目
若一堆中每步可取走一或两个代币,三个代币有两个合法走法,分别到达两个及一个代币。后继值是 和 ,所以其值为 。单靠合法走法数目不能决定局面值。
为何独立游戏以异或合并
定义 5.1.3
(游戏的和)
对局面 ,其和 指每一步只在其中一个分量走一步。非负整数上的 表示按位异或。
定理 5.1.4
(和的异或规则)
对有限无偏正常玩法游戏的局面 ,
证明
(对剩余走法数归纳)
对两个分量的最长剩余走法数之和归纳。设 、、。只改变 的后继由归纳假设有值 ;因 不在 的后继值中,,所以后继值不可能是 。只改变 时同理。
现在任取整数 ,令 。在 与 不同的最高位, 是 而 是 。因为 , 至少一个在该位是 。假设是 ,则 。mex 的定义保证 有值为 的后继,而所得和的值为 。选中 的情况相同。因此没有后继的值是 ,但每个小于 的值都出现,故其 mex 是 。
证明透视
Mex 证明的两部分
这个证明须对同一个数 说明两件事:和的后继没有一个的值是 ,并且每个比它小的值都出现。第一件只用到 不在 的后继值中、 不在 的后继值中,即 mex 定义中“不在集合内”的一半。第二件才是不寻常的一步: 与 不同的最高位,指出一个可以借助与 异或而降低其值的分量,然后 mex 定义中“每个更小的值都出现”的一半提供所需的后继。异或正是用在找出该位为 的分量这一处;对普通的值相加,这个论证没有对应的版本。归纳之所以能收尾,是因为每走一步,剩余的走法就缩短。
证明可重复用于有限多个分量;它确定游戏值,不只是胜负。异或值非零时可走到零;异或值为零时每个合法后继都非零。
常见错误
(把值相加而不是异或)
两堆各有一个代币,值分别为 与 。其和局面的值为 :先手走到 ,后手取走最后一个代币,先手落败。若把值相加会得 ,错误地暗示先手获胜。合并的规则是异或。
一个取子游戏
设一堆有 个代币,每步可在数量足够时取走 或 个。
定理 5.1.5
(每步取一个或两个的游戏的值)
在这个游戏中,对每个 都有 。
证明
(对堆的大小归纳)
基础值为 和 。当 ,由归纳假设,后继 的值是模 余数中不等于 的另外两个;由 mex 定义, 是剩下的余数。
这也证明了上面反例使用的值。
例题 5.1.6
(用 mex 算出最初几个值)
局面 是终局,所以 。局面 只有后继 ,所以 。局面 的后继为 ,值为 ,所以 。局面 的后继为 ,值为 ,所以 。局面 的后继为 ,值为 ,所以 。局面 的后继为 ,值为 ,所以 。局面 的后继为 ,值为 ,所以 。数列 就是 。终局 是唯一没有后继的情况,所以它的值是空集合的 mex。
例题 5.1.7
(大小为 4 与 8 的两堆)
若两堆分别为 和 ,其值为 和 ,异或为 ,故轮到走的一方获胜。第一堆取走 得 ,其值为 ;第二堆取走 得 ,其值为 。两步均得到零异或。其他合法首步是 或 ,异或均非零,所以上述就是全部致胜首步。
例题 5.1.8
(三堆,其中一堆的值为零)
在同一个游戏中取三堆 。其值为 ,异或为 ,所以轮到走的一方获胜。要使异或为零,必须把某一堆走到“其余两堆的异或”那个值:对 的一堆(值 ),目标是 ,取走一个代币得 即可;对 的一堆(值 ),目标是 ,取走两个代币得 即可。结果 与 的值分别为 与 。 的一堆值为 ,没有致胜的走法:把它走到 或 ,异或分别是 或 ,都不为零。
先异或游戏值,再找出合法一步
从实际选项建立 Grundy 值,组合独立堆,并比较每个合法后继。游戏异或为零表示轮到的人必败,不一定表示无步可走。
改变规则、堆数或石数是在编辑新的分析局面:清空对局记录,由玩家 1 开始。只有走步按钮才执行合法回合。Mex 检查器与对局独立。
没有可撤销的对局回合。
当前正常玩法局面: (4,5); 轮到的玩家: 1; 对轮到的玩家的结果: 必胜.
堆 1: n=4, g(n)=1.
堆 2: n=5, g(n)=2.
受限堆一般有 g(n)≠n。原石数不是组件游戏值,即使这次异或碰巧判定相同胜负。
| 堆 | 石数 | Grundy 值 | 二进制游戏值 |
|---|---|---|---|
| 1 | 4 | 1 | 0001 |
| 2 | 5 | 2 | 0010 |
| 总异或 | 不适用 | 3 | 0011 |
构造一个零异或走法
G 最高置位的掩码值: 2; 选定组件: 2; 所需下一游戏值: 2 xor 3 = 1.
堆 2: 取走石数 1; 实际下一堆石数: 4; 下一游戏异或: 0.
目标是 Grundy 值,不是指定石数。须找一个有该值的真正合法选项。此构造给出一步,但可能另有必胜走法。
| 堆 | 取走石数 | 之后各堆石数 | 之后各游戏值 | 下一游戏异或 | 对下一玩家的结果 | 对当前玩家的必胜一步 | 走这一步 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | (3,5) | (0,2) | 2 | 必胜 | 否 | |
| 1 | 2 | (2,5) | (2,2) | 0 | 必败 | 是 | |
| 2 | 1 | (4,4) | (1,1) | 0 | 必败 | 是 | |
| 2 | 2 | (4,3) | (1,0) | 1 | 必胜 | 否 |
取最小缺少的选项值: g(5)=mex({0,1})=2.
箭头由检查石数指向其合法较小石数。节点数字是石数,g 标签是游戏值。选项表列出相同有向选择;没有连线的参考节点不会增加选项。
| 取走石数 | 后继堆石数 | 选项游戏值 |
|---|---|---|
| 1 | 4 | 1 |
| 2 | 3 | 0 |
- 0: 出现
- 1: 出现
- 2: 首个缺少:mex
零至八石的单堆值
| 石数 | 合法后继石数 | 这些选项的值 | Mex |
|---|---|---|---|
| 0 | 无 | ∅ | 0 |
| 1 | (0) | (0) | 1 |
| 2 | (1,0) | (1,0) | 2 |
| 3 | (2,1) | (2,1) | 0 |
| 4 | (3,2) | (0,2) | 1 |
| 5 | (4,3) | (1,0) | 2 |
| 6 | (5,4) | (2,1) | 0 |
| 7 | (6,5) | (0,2) | 1 |
| 8 | (7,6) | (1,0) | 2 |
只记录实际走步
| 回合 | 轮到的玩家 | 之前各堆 | 堆 | 取走石数 | 之后各堆石数 |
|---|
- 轮到的玩家
- 1
- 游戏值的异或
- 3
- 原石数的异或
- 1
- 对轮到的玩家的结果
- 必胜
- 只用石数异或会判定的结果
- 必胜
- 合法步数
- 4
- 零异或后继数
- 2
- 没有合法步
- 否
取 1 或 2; 当前正常玩法局面: (4,5); 轮到的玩家: 1; 游戏值的异或: 3; 对轮到的玩家的结果: 必胜. 合法步数: 4; 零异或后继数: 2; 检查此石数的 mex: 5, g=2.
为何此值能预测必胜一步
这些是有限、公平的正常玩法游戏。每一步只从一堆取走正数石,总石数严格下降,对局必然结束。没有合法步的玩家输。必败不同于终局:取一或二的 (3,6) 堆有合法步,但没有必胜一步。
Mex 是选项值中最小的缺少非负整数。因此没有选项与原局面 Grundy 值相同,而每个更小值都由某个选项达到。终局 mex 为零。局面当且仅当 mex 为零才必败:其全部选项值非零;正 mex 则有值零的选项。
独立组件的值异或记为 G。走一步把某个 g_i 换成不同的选项值,所以没有后继值等于 G。对任意 z<G,在 G 与 z 最高不同位中选一个有置位的组件。较小目标 h=g_i xor G xor z 由 mex 保证存在,所得后继异或为 z。因此后继值的 mex 是 G,以归纳证明异或规则。
G≠0 时,选游戏值包含 G 最高置位的组件,目标 h=g_i xor G<g_i,必有合法选项达到。例题 (4,5) 的组件值为 (1,2),故 G=3。构造把第二堆目标设为值 1,可取一石留四石。第一堆取二也得异或零;构造不必列出全部必胜步。
取一或二时 g(n)=n modulo 3。改为取 1、2、3,零至八的值为 [0,1,2,3,0,1,2,3,0],同一余数公式在三石已错。普通 Nim 则有 g(n)=n。受限堆 (3,6) 的值 (0,0) 表示必败,原石数异或却是 5。游戏值由规则决定,不由外观相似决定。
定理需要独立组件、公平走法、有限无环对局及正常结束规则。同时改变几个组件、共享资源、无限循环或反常玩法,都需另外分析。这里取最后一石会赢;反常玩法则会输。本图精确计算零至八石的组件表及合法步,不把较大游戏值理解成步数或信心分数。
为何零异或仍可有步走?
零异或表示每个合法后继对下一玩家必胜,不表示没有后继。受限局面 (3,6) 的每堆值都为零,但仍能取石。构造零异或的按钮会停用,合法走步按钮则仍可使用。
本图支持一至三个独立堆,每堆零至八石,使用同一所选规则,并列出全部合法步。胜负是对现在轮到的人而言,走一步会换玩家。编辑控件建立新分析,不是合法回合。这是最佳对弈下的正常玩法预测,没有随机或和局;反常及循环游戏不在范围。
习题与解答
快速检查
(空堆的值是多少?)
它没有后继。
解答 · 答案
,即空集合的 mex。
快速检查
(在此取子游戏中, 个代币的值是多少?)
使用 的公式。
解答 · 答案
。
快速检查
(在上述规则下,从 出发谁会赢?)
计算两堆的值。
解答 · 答案
两堆值均为零,故异或为零;双方最佳对弈下轮到走的一方落败。
快速检查
(若改成不能走的一方获胜,可不加证明地沿用零值结论吗?)
归纳的哪一步用到终局规则?
解答 · 答案
不可。这改变了终局条件,正常玩法的归纳不再按原样适用。