公平组合游戏
这里讨论无随机因素、双方信息完全、轮流行动且可选操作不因玩家身份而改变的游戏。对下面的 SG 递推,还要求状态转移有限且无环,并采用无法行动者输的正常规则。
Nim 游戏
每次从一堆石子里取走正数个石子,取走最后一枚的人获胜。若各堆大小为 ,必败态恰好满足
SG 函数
令 表示不在集合 中的最小非负整数。状态 的 SG 值是
终止状态的值为 。多个相互独立的子游戏组成的和游戏,其 SG 值为各子游戏 SG 值的异或;总值为 是必败态,非零是必胜态。
使用前检查
子游戏之间必须独立。存在平局、循环,或者采用取走最后一枚者输的规则时,需要重新分析,不能直接沿用上述判定。
来源与延伸
根据旧库同名学习笔记整理,补充了正常规则与有限无环的适用条件。