game theory

组合游戏

Nimber

任意一个

Sprague–Grundy Number

对于一个子游戏状态 , 有 个后续状态

定义它的阶

Sprague–Grundy Theorem

一个游戏 由 个子游戏 组成

则整个游戏的 值为

证明:

Nim Game

有 堆石头, 数量分别为

每次可以从一堆石子取走任意数量的石头

Normal Version

取走最后一个石头的玩家胜

如果异或和 , 则先手必输; 否则先手必胜

Misère Version

取走最后一个石头的玩家输

满足下列条件之一, 则先手必胜:

1. 所有堆的值 , 并且有偶数堆
2. 至少有一个堆的值 , 并且

证明:

Substraction Game