Skip to content

阅读约 6 分钟English

博弈论学习笔记

博弈论学习笔记，涵盖必胜必败态三定理、Nim 游戏、SG 函数与 SG 定理，以及威佐夫博弈。

三条定理

有个叫博弈图的东西，把每个状态看作一个点，把它向它能推到的状态连边，如下图。

博弈图

定义

  • 必胜状态: 先手必胜的状态
  • 必败状态: 先手必败的状态

则有

  1. 没有后继状态的状态是必败状态
  2. 一个状态是必胜状态，当且仅当它的至少一个后继状态是必败状态
  3. 一个状态是必败状态，当且仅当它的所有后继状态是必胜状态

其实很好理解

  1. 玩不下去了，就败北了
  2. 如果至少一个后继状态是必败的，那么只要往这个状态走，对面就必败了
  3. 如果后继的所有状态都是必胜的，不管怎么走，对面都躺赢

从这个开始会不会感觉好一点，为什么其它文章都是从Nim游戏引入的，让人丧失自信心

Nim游戏

n 堆物品，每堆 a[i] 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。取走最后一个物品的人获胜。

Nim和

有一个神秘结论，计算每堆物品个数的异或和 a[1] ^ a[2] ^ ... ^ a[n]（这玩意又叫 Nim和），如果这个数为0，当前状态必败，否则必胜。

证明

我们试图证明。参照上面的三个定理，我们只要说明以下两句话的正确性，就可以证明了。

  1. 如果一个状态Nim和不是0，我们一定有办法把它做到Nim和为0
  2. 如果一个状态Nim和是0，那么它要么没有后继状态，要么所有后继状态Nim和都不是0

（由于物品个数单调递减，最后肯定会被取完，所以只要能让对手的Nim和保持0，就稳了）

首先，异或和不是0，意味着把这些数二进制排列后，如图

堆的大小 第3位 第2位 第1位 第0位
7 0 1 1 1
9 1 0 0 1
12 1 1 0 0
15 1 1 1 1

这组数据的Nim和是13。

在Nim和的最高位这一列（设为k）上，肯定有奇数个1。把第k位1的任意一个数拎出来，与Nim和异或下，再放进去，这样保证了

  • 这个数与Nim和的异或结果肯定小于这个数（本来这个数至少是二进制下的k位数，现在至多k - 1位）
  • Nim和为0（异或自身为0）

我们挑选15这个数，异或上13，可以得到一个Nim和为0的表。

堆的大小 第3位 第2位 第1位 第0位
7 0 1 1 1
9 1 0 0 1
12 1 1 0 0
2 0 0 1 0

如果一个状态的Nim和为0，那每个位置都有偶数个1。最简单的情况是这些位置全是0，这样就输了。如果不是这种情况，由于只能取一堆，而且不能不取，这样无论取（同一行）哪些位置的1，都把原来某一列的偶数个1变成奇数个1了。

SG函数和SG定理

mex函数

我们先定义一个mex (minimum excludent) 函数，这个函数返回集合中不存在的最小非负整数。例如 mex{0, 1, 5} = 2, mex{2, 3, 4} = 0, mex{} = 0。

SG函数

定义 SG(x) = mex(S), 其中 S是x所有后继状态SG函数值的集合。例如x有3个后继状态 a, b, c，那么 SG(x) = mex{SG(a), SG(b), SG(c)}。根据mex函数的定义，如果x没有后继状态，S是个空集，那么 SG(x) = 0。当且仅当x为必败点时，SG(x) = 0。

SG定理

游戏和的SG函数等于各个游戏SG函数的Nim和。因为SG(x) = 0意味着当前必败，假设对于n局游戏，起点分别为 S1, S2, ..., Sn，当且仅当 SG(S1) ^ SG(S2) ^ ... ^ SG(n) != 0 时这个游戏先手必胜。这个定理常被用来分治。

取石子问题

有n个石子，每次只能取 1, 3, 4 个石子，先取完石子者胜利，那么1 ~ n的SG值为多少？

首先，SG(0) = 0。

（以下建议手推，加强印象）

  • x = 1 时，可以取走 {1} 个石子，剩余 {0} 个，所以 SG(1) = mex{SG(0)} = mex{0} = 1
  • x = 2 时，可以取走 {1} 个石子，剩余 {1} 个，所以 SG(2) = mex{SG(1)} = mex{1} = 0
  • x = 3 时，可以取走 {1, 3} 个石子，剩余 {2, 0} 个，所以 SG(3) = mex{SG(2), SG(0)} = mex{0, 1} = 2
  • x = 4 时，可以取走 {1, 3, 4} 个石子，剩余 {3, 1, 0} 个，所以 SG(4) = mex{SG(3), SG(1), SG(0)} = mex{2, 0, 1} = 3
  • x = 5 时，可以取走 {1, 3, 4} 个石子，剩余 {4, 2, 1} 个，所以 SG(5) = mex{SG(4), SG(2), SG(1)} = mex{3, 0, 1} = 2
  • x = 6 时，可以取走 {1, 3, 4} 个石子，剩余 {5, 3, 2} 个，所以 SG(6) = mex{SG(5), SG(3), SG(2)} = mex{3, 2} = 0
  • x = 7 时，可以取走 {1, 3, 4} 个石子，剩余 {6, 4, 3} 个，所以 SG(7) = mex{SG(6), SG(4), SG(3)} = mex{0, 3, 2} = 1
  • x = 8 时，可以取走 {1, 3, 4} 个石子，剩余 {7, 5, 4} 个，所以 SG(8) = mex{SG(7), SG(5), SG(4)} = mex{1, 2, 3} = 0

…

x 0 1 2 3 4 5 6 7 8
SG(x) 0 1 0 2 3 2 0 1 0

所以，我们可以这样计算SG函数。

// f: 可改变当前状态的方式，要在 getSG 之前预处理
// SG: 0 ~ n的 SG 函数值
// S: x 后继状态的集合

int f[N], SG[MX];
bitset<MX> S;

void getSG(int n)
{
    memset(SG, 0, sizeof(SG));
    // 因为 SG(0) 始终等于0，所以 i 从 1 开始
    for (int i = 1; i <= n; i++)
    {
        // 每一次都要将上一状态的后继集合重置
        S.reset();
        for (int j = 0; f[j] <= i && j <= N; j++)
        {
            S.set(SG[i - f[j]]); // 将后继状态的 SG 函数值进行标记
        }
        for (int j = 0;; j++)
        {
            if (!S.test(j))
            { // 查询当前后继状态 SG 值中最小的非零值
                SG[i] = j;
                break;
            }
        }
    }
}

威佐夫博弈

游戏规则

参考维基百科

有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以

  1. 从任意一堆石子中取任意多的石子
  2. 从两堆石子中取同样多的石子

不能取的人输，问谁会获得胜利。

想法

设两堆石子中较小的一堆大小为a，另一堆大小为b，并称 (a, b) 这个数对为当前的状态。注意到 Δ = b - a 在第二种操作下不会改变。

列出如下后手必胜的局面（后称奇异状态）：

  1. 0 0
  2. 1 2
  3. 3 5
  4. 4 7
  5. 6 10
  6. 8 13

奇异状态是没法一步变到更小的奇异状态的状态。比如 1 2 只能变到 0 1 / 0 2 / 1 1，而没法变到 0 0。对于 2 x，可以一步变到 1 2。如果状态 (a, b) 的a已经在之前的奇异状态出现过了，那么显然可以通过第一种操作一步转到之前的奇异状态，所以奇异状态中的第一个数一定是之前的奇异状态中没有出现的数。然后如果把 0 0 当成第0个奇异状态的话，奇异状态的 b = a + i（这一个可以观察出来）。感性说明下，2 3 / 3 4 / 4 5 这类状态都可以通过第二种操作变成 1 2，但是 3 5 就不行，因为之前的奇异状态没有相差2的，4 7 也不行，因为之前的奇异状态没有相差3的。

也许可以这样理解：我们把可以通过奇异状态反推一步得到的状态都划掉，留下的就是下一个奇异状态。

快速判定奇异状态

威佐夫的结论是 delta * (sqrt(5) + 1) / 2 = a 时先手必败，否则先手必胜。其中 (sqrt(5) + 1) / 2 是 黄金分割数 + 1。