博弈整理(一)

Impartial game

wikipedia链接:https://en.wikipedia.org/wiki/Impartial_game

impartial game 是指满足如下条件的游戏: - 两个玩家轮流操作,直到达到不能操作的状态(terminal position)。 - 当一个玩家不能操作时,winner 就被确定了。 - 每个状态的操作数和状态总数是有限的。 - 所有的操作必须同时能被两个玩家进行。 - 所有操作的结果都是确定性的。

Normal play convention

wikipedia链接:https://en.wikipedia.org/wiki/Normal_play_convention
Impartial game 的 Normal play convention :最后一个可以操作的玩家获胜。

Nim游戏

wikipedia链接:https://en.wikipedia.org/wiki/Nim
有若干堆石子,两个人轮流取石子。每次轮到的人可以选择从某一堆中拿走若干颗石子(不能不拿),不能按规则操作的人输。
Nim 游戏属于 Impartial game。

Nim游戏的胜利条件

定理:当且仅当每堆石子的个数异或和不为 \(0\) 时,先手必胜。
证明
对于 terminal position,即没有石的情况,异或和为 \(0\),轮到这个状态的人输。定理对 terminal position 成立。
引理1 若一个状态,每堆石子个数异或和不为 \(0\),则它必定可以转移到一个石子个数为 \(0\) 的状态。
证明
设每堆石子个数的异或和为 \(s\)
\(s\) 最高的二进制位是第 \(k\) 位(从低到高,最低位为第 \(0\) 位)。
一定存在一堆石子个数为 \(x\),二进制下 \(x\) 的第 \(k\) 位为 \(1\)
除了这堆石子外,其他堆石子个数的异或和为 \(s\oplus x\)
\(s\oplus x\)\(x\) 在所有比第 \(k\) 位高的二进制位上相等,\(s\oplus x\) 的第 \(k\) 位为 \(0\)\(x\) 的第 \(k\) 位为 \(1\),所以 \(s \oplus x < x\)
可以从这堆石子中取走 \(x-s\oplus x\) 个石子,使异或和变为 \(0\)

引理2 若一个状态,每堆石子个数异或和为 \(0\),无论怎么操作都会转移到一个每堆石子个数异或和不为 \(0\) 的状态。
证明
设操作的堆在操作前有 \(x\) 颗石子。
那么除了这堆以外的其他堆石子数异或和也为 \(x\)
在取石子后,这堆石子的个数一定不为 \(x\)
只有这堆石子的个数为 \(x\) 时,与其他堆石子个数的异或和才会为 \(0\)
所以操作后,每堆石子个数的异或和一定非 \(0\)
根据结构归纳法可知定理成立。

Sprague–Grundy 定理

wikipedia链接:https://en.wikipedia.org/wiki/Sprague–Grundy_theorem
定义 \(mex\) 运算,一个集合的 \(mex\) 值是最小的没有出现在这个集合中的自然数。
定义 Sprague-Grundy 函数:对于一个状态 \(x\),当 \(x\) 是 terminal position 时,\(SG(x)=mex\{SG(y)|x\) 可以转移到 \(y\}\)
可以用 Sprague-Grundy 函数判断一个状态是必胜状态还是必败状态,因为必胜状态函数值必不为 \(0\),必败状态函数值必为 \(0\)
定义两个游戏的 disjunctive sum 为一个游戏:轮到每个玩家的时候,他可以选择两个游戏中的一个游戏,然后在这个游戏上操作一步,无法操作的人输。
显然 disjunctive sum 满足交换律和结合律。
定理\(n\) 个游戏 \(G_1,G_2,\cdots,G_n\),设他们的 disjunctive sum 为 \(G\)。那么 \(SG(G)=SG(G_1)\oplus SG(G_2)\cdots \oplus SG(G_n)\)
证明可以看这个
这也说明了每一个 normal play convention 下的 impartial game 都等价于一个Nim游戏。