博弈论学习笔记

xzh7 · 2025-11-06 19:58:41 · 算法·理论

博弈论

状态：到某一时刻为止，所有可能与状态有关的信息。
局面：到某一时刻为止，双方玩家面对的局势。
游戏：博弈图上的一个节点，通常用局面代替。
博弈图：每个状态向下一个状态连边形成的有向图（可证明无环）。
游戏的和：即许多游戏拼到一起，例如Nim游戏就是许多单堆Nim游戏的和。
游戏的等价关系：如果对于所有游戏 H ，游戏 G_1+H 与 G_2+H 都为必胜状态以及必败状态，那么称游戏 G_1 和 G_2 等价，记作 G_1 \approx G_2 。

描述：共有 n 堆石子，第 i 堆有 a_i 枚石子，两位玩家每轮取走任意堆中的任意数量个石子，但不能不取。取走最后一个石子的玩家获胜。

所有状态可分为必胜状态及必败状态两种。

以下有三条引理（必胜或者必败是用来描述先手的，先手决定下一个状态）：

定义：自然数 a_1,a_2...a_n 的Nim和定义为 a_1 \oplus a_2 \oplus ... \oplus a_n。

定理：在Nim游戏中，状态 (a_1,a_2...a_n) 是必败状态，当且仅当Nim和 a_1 \oplus a_2 \oplus ... \oplus a_n=0。

核心思想：如果当前状态的异或和 S=0，那么无论当前玩家怎么移动，都会使异或和变为非零；而对手总是能从非零异或和的状态中移动，使异或和重新变为零。这样，当前玩家最终会被迫面对所有堆为零的状态（无法移动，输掉游戏）。

数学证明：使用归纳法。

如果 a_i=0 对所有的 i=1,2...n 都成立，那么该状态为必败状态，且Nim和为0,符合条件。
如果当前 S=0，那么先手无论如何都会破坏这个状态；
如果接上一步，那么后手一定有办法使其重新变成 0。具体方法：找到先手选完后 S 的二进制表示中第一个非零的位置，可以证明目前的每个石子堆中石子个数的二进制表示中一定至少有一个这一位也是 1 ，那么，我们就可以把这个 1 变成 0 ，然后其后面的位置随便放 0 或 1 ，这样改变后的石子个数不会超过原先的，后面 0 与 1 的重新排列也可以使异或和重新变为 0 。