公平组合游戏 ICG
1.两名玩家交替
2.操作与是哪名玩家无关
3.不能行动者判负
公平组合游戏都是有向图游戏(一个状态指向另一个状态)
都可以使用 (SG) 定理
每个状态要么是“必胜态”,要么是“必败态”
必胜态一定能走到必败态
必败态无论怎么走都走到必胜态
例子——nim游戏
(n) 堆石子,大小为 (a_i) ,两人轮流选一堆取至少一个,取走最后一个石子者胜(即没的取得人输)
令 (t=a_1 XOR a_2 XOR dots XOR a_n)
若 (t=0) ,先手负
若 (t
eq 0) ,先手胜
SG函数与SG定理
SG函数:
设 (x) 的后继节点为 (y_1,y_2,...)
则 (SG(x)=mex{SG(y_1),SG(y_2),...})
SG定理:
定义有向图游戏的和 (G) ——(m)个有向图游戏 (G_1,G_2,...,G_m) ,每次操作可任选一个游戏操作
(SG(G)=SG(G_1) XOR SG(G_2) XOR ... SG(G_m))
若 (SG(G)=0),先手负
若 (SG(G)
eq 0),先手胜
一些变形
multi-SG
一个状态 (G) 在一次操作后可拆成若干子状态 (g_i) ,则可看成把这些子状态看为一个状态 (F),$SG(F)=SG(g_1) XOR SG(g_2) ... $
其他的都一样
阶梯nim
(n) 堆石子,大小为 (a_i)
每次可选取一堆 (i) ,取至少一个石子,挪到第 (i-1) 堆
最终要所有石子挪到第 (0) 堆。无法操作者负。
可看成是奇数位的堆做 (nim)
anti-SG
规则不同——无法操作者胜
有 (SJ) 定理
对某一局面,先手必胜的条件为以下两条之一:
1.所有单一状态的 (SG) 值不大于1,该局面 (SG) 值为0
2.存在单一状态的 (SG) 值大于1,该局面的 (SG) 值大于0