博弈论学习笔记

三条定理

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

博弈图

定义

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

则有

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

其实很好理解

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

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

Nim 游戏

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

Nim 和

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

证明

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

如果一个状态 Nim 和不是 0，我们一定有办法把它做到 Nim 和为 0
如果一个状态 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;
            }
        }
    }
}

威佐夫博弈

游戏规则

参考维基百科

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

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

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

想法

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

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

0 0
1 2
3 5
4 7
6 10
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。

搜索此博客

所谓自由就是可以说二加二等于四的自由