博弈论

教程：

• 算法讲解095【必备】博弈类问题必备内容详解-上_哔哩哔哩_bilibili
• 算法讲解096【必备】博弈类问题必备内容详解-下_哔哩哔哩_bilibili

资料：

• Games on arbitrary graphs - Algorithms for Competitive Programming
• 浅谈算法——博弈论 - Wolfycz - 博客园

概念

公平组合游戏 ：

游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

非公平组合游戏

非公平组合游戏（Partizan Game）与公平组合游戏的区别在于在非公平组合游戏中，游戏者在某一确定状态可以做出的决策集合与游戏者有关。大部分的棋类游戏都不是公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。

反常游戏

反常游戏（Misère Game）按照传统的游戏规则进行游戏，但是其胜者为第一个无法行动的玩家。以 Nim 游戏为例，Nim 游戏中取走最后一颗石子的为胜者，而反常 Nim 游戏中取走最后一刻石子的为败者。

巴什博弈(Bash Game)

一共 $n$ 颗石子，两个人轮流拿，每次可以拿 $1-m$ 颗，没有石子可以拿的一方失败。

练习： P4018 Roy&October之取石子 - 洛谷 | 计算机科学教育新生态判断是否为 6 的倍数即可。

尼姆博弈(Nim Game)

$n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜。

定义 Nim 和 $=a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n$，若 Nim 和为 0，则后手 win，不为 0，则先手 win。

即 NIm 和 $\ne 0$ 为必胜态，Nim 和 $=0$ 为必败态

• $0\to \ne 0$ ，一旦拿走了石子，则在二进制某些位上的奇偶性一定会发生变化
• $\ne 0\to 0$ ，对于在每一位上都可以变化其奇偶性，一定有某种方式使得 $\ne 0\to 0$

P2197 【模板】Nim 游戏 - 洛谷 | 计算机科学教育新生态

反常游戏

谁先拿走最后的物品，谁输。其他和 Nim 相同。

若所有数都为 1，则根据奇偶性获胜，否则 Nim 和 $\ne 0$ ，则先手 win，Nim 和 $=0$，则后手 win

斐波那契博弈 (Fibonacci Game + Zeckendorf 定理）

P6487 [COCI2010-2011#4] HRPA - 洛谷 | 计算机科学教育新生态

有 $n$ 枚石子。两位玩家定了如下规则进行游戏：保证 $2\le n\le {10}^{15}$。

• Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
• Mirko 在第一次取石子时可以取走任意多个；
• 接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍。当然，玩家取走的数量必须不大于目前场上剩余的石子数量。
• 取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能够获胜。

Zeckendorf (齐肯多夫) 定理：任意一个非斐波那契数一定能被拆分为若干个不相邻的斐波那契数。
(证明可用反证法)

若 $n$ 为斐波那契数，则先手必败，必须直接取走全部

若 $n$ 不是斐波那契数，则答案则为表示法中最小的数

ll fi[85];
void solve() {
    int n;cin >> n;
    fi[1] = 1;fi[2] = 1;
    for (int i = 3;i <= 80;i++)fi[i] = fi[i - 1] + fi[i - 2];
    while (n) {
        auto x = upper_bound(fi, fi + 80, n);
        if (*--x == n) {
            cout << n << '\n';return;
        }
        n -= *x;
    }
}

威佐夫博弈(Wythoff Game)

P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈 - 洛谷 | 计算机科学教育新生态

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。

游戏规定，每次有两种不同的取法：

• 可以在任意的一堆中取走任意多的石子；
• 可以在两堆中同时取走相同数量的石子。

最后把石子全部取完者为胜者。
现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

结论：小 $\ne$ (大-小) $\times$ 黄金分割比例，先手 win，否则，后手 win

SG 函数

SG 函数 (Sprague-Grundy 函数)，如下是 SG 返回值的求解方式，俗称 mex 过程
最终必败点是 A，规定 SG (A)=0
假设状态点是 B，那么 SG (B)=查看 B 所有后继节点的 sg 值，其中没有出现过的最小自然数
SG (B)!=0，那么状态 B 为必胜态; SG (B)=0，那么状态 B 为必败态

SG 定理 (Bouton 定理)
如果一个 ICG 游戏 (总)，由若干个独立的 ICG 子游戏构成 (分 1、分 2、分 3..)，那么:
SG (总)=SG (分 1)^SG (分 2)^ SG (分 3).. 任何 ICG 游戏都是如此，正确性证明类似尼姆博弈
当数据规模较大时，要善于通过对数器的手段，打印 SG 表并观察，看看能不能发现简洁规律