「博弈论学习笔记」#1 组合游戏基础

OI 中的博弈论主要研究公平组合游戏（ICG）。

此外还有非公平组合游戏，比如大部分的棋类；反常游戏，ICG中的胜者改为败者。

公平组合游戏

定义

如果一个游戏满足以下条件，就称其为一个公平组合游戏

由两名玩家交替行动。
在游戏的任意时刻，能执行的合法操作与当前是那一名玩家无关。
先无法行动者告负。

同时公平组合游戏一定只有先手必胜和先手必败两种情况。

Bash Game

Bash 游戏形式如下

有 \(n\) 个石子，两人博弈，每人每次可以拿 \(1 \sim m\) 个石子，无法拿石子的人告负。给定 \(n\)，\(m\)，求先手是否必胜。

若 \(n \le m\)，那么先手直接全部拿走即可，必胜。
若 \(n = m+1\)，那么先手不能一次都拿走且后手一定能全部拿走，先手必败。

将上述情况进行扩展，如果 \(m+1 \mid n\)，那么若先手拿走 \(k\) 个，后手只要拿走 \(m+1-k\) 个，那么仍然满足 \(m+1 \mid n\)。由于当 \(n=0\) 时 \(m+1 \mid n\)，所以如此循环往复下去先手一定会面临 \(n=0\) 的局面，所以先手必败。

否则先手只要取 \(k\) 个使得 \(m+1 \mid n-k\)，就能回到上述状态，只不过上面的「先手」是现在的后手，其必败，所以这种情况先手必胜。

luogu4018

题面

将上题取 \(1 \sim m\) 个改为取任意能表示为 \(p^k\) 的数个，其中 \(p\) 是质数且 \(k \in \mathbb{N^+}\)，同时 \(p^k\) 小于等于当前剩余石子数。

考虑 \(n \in [1,5]\) 时，先手都可以一次取完。

而当 \(n=6\) 时则不能。

由唯一分解定理容易发现任何 \(6\) 的倍数都不能写成 \(p^k\) 的形式。

所以仿照上述操作，如果 \(6 \mid n\)，那么先手一定无法取 \(6\) 的倍数个，而后手一定能使得两次取走 \(6\) 的倍数个，所以此时先手必败。

否则先手将 \(n\) 取成 \(6\) 的倍数个即可，必胜。

Nim Game

\(n\) 堆石头，第 \(i\) 堆有 \(a_i\) 个石子。两名玩家博弈，每次可以选择一堆并取走其中任意非 \(0\) 个石子，无法取石子者告负。判断先手必胜还是必败。

定理：

Nim游戏先手必胜，当且仅当 \(\bigoplus_{i=1}^n a_i \neq 0\)，也就是 nim 和为 \(0\)。

证明：

所有石子被取走的局面是失败局面，此时 nim 和为 \(0\)。考虑一个 nim 和 \(x\) 不为 \(0\) 的情况，那么设 \(x\) 最高为的 \(1\) 在第 \(k\) 位，一定存在至少一个 \(a_i\) 满足第 \(k\) 位为 \(1\)。设它为 \(a_j\)，那么有 \(a_j \oplus x < a_j\)，而 \(a_j \oplus x\) 与 \(x \oplus a_j\) 做异或运算为 \(0\)，其中后者表示 nim 和除掉 \(a_j\)。因此只要让 \(a_j\) 变成 \(a_j \oplus x\) 就能使得 nim 和为 \(0\)，而后者小于前者，因此可以通过一次操作使得 nim 和为 \(0\)。
如此重复，一定能使得后手只会面临 nim 和为 \(0\) 的局面，最终到无法取走石子。

hdu1850

Nim 游戏，先手第一次操作有多少种必胜方法。

仿照证明过程，如果 nim 和不为 \(0\)，那么任意选择一个 \(a_i \oplus x < a_i\) 的就行

有向图游戏与 SG 函数

有向图游戏

给定一个 DAG，形式化地写作 \(G(X,F)\)，其中点集 \(X\) 为局面集合，\(F\) 是 \(X\) 上的函数，对于节点 \(x \in X\)，\(F(x)\) 表示从其出发能够一步移动到的位置集合，表示了一个形式上的边集。如果 \(F(x) = \varnothing\)，那么称 \(x\) 为终点，如果 \(y\) 不属于任何一个 \(F(x)\)，那么称其为起点。

两人轮流移动初始在起点的一枚棋子，若其在 \(x_0\)，那么可以移动到 \(F(x_0)\) 内的任意节点。无法移动者告负。

任何一个 ICG 都能转化成有向图游戏，具体方法是将每个局面都带入点集 \(X\)，从局面 \(x\) 能到达的局面集合构成 \(F(x)\)。由 ICG 的定义可知其不可能存在环，若存在环则游戏一定存在平局。

上文有一些很奇妙的内容。

我们能通过考虑小范围的胜负情况来让大范围的状态归约到它们上；失败局面可以倒推出先手必败局面；本来是先手必败的状态，经过一次操作之后就变成先手必胜了。

把这一切放到图上就容易理解了。由于 ICG 只有先手必胜局面和先手必败局面，所以每个节点（状态）都是必胜或必败状态之一。而且状态可以转化，对于 \(x\)，\(F(x)\) 都是他的「子游戏」，二者之间相差一次操作。所以对于一条从终点倒推向起点的链，其节点状态必然是必败，必胜，必败，必胜。在一张图上，一个节点连到的点，他们到终点的长度不一样，自然有必胜也有必败。

比较简单的情况就是如果 \(F(x)\) 都是必败局面，那么无论怎么操作 \(x\)，对方都一定面临必败局面，所以是必胜；反过来也一样。

但考虑到二者绝顶聪明，只要 \(F(x)\) 中又一个必败局面，当前玩家一定会这样操作。而如果 \(F(x)\) 中存在一个必胜局面，玩家绝对不会这样做。所以只有 \(F(x)\) 全都是必胜局面，\(x\) 才是必败局面。

此时引入概念后继状态。对于 \(x\)，其后继状态为 \(F(x)\)，在图上也可称后继节点。

SG 函数

定义 \[ SG(x)= \operatorname{mex} \big\{ SG(y) | y \in F(x) \big\} \] 也就是 \(x\) 所有后继状态的 \(SG\) 函数值中没有出现过的最小非负整数。

整个游戏的 \(SG\) 函数值为起点的 \(SG\) 函数值。

特殊规定终点的 \(SG\) 函数值为 \(0\)，同时要保证必败局面的 \(SG\) 函数值都为 \(0\)。

如果存在一个 \(SG(x) > 0\)，那么 \(x\) 的后继状态中一定存在 \(SG\) 函数值为 \(0\) 的状态，也就是存在必败局面，此时 \(x\) 为必胜局面。否则 \(SG(x)=0\)，那么 \(x\) 的后继状态中一定不存在 \(SG\) 函数值为 \(0\) 的状态，也就是全部为必胜局面，此时 \(x\) 必败。

得到

有向图游戏的某个局面 \(x\) 必胜，当且仅当 \(SG(x)> 0\)。
有向图游戏的某个局面 \(x\) 必败，当且仅当 \(SG(x) = 0\)。

SG 定理

设 \(G_1,G_2,\cdots G_m\) 为 \(m\) 个有向图游戏，存在一个有向图游戏 \(G\)，其规则是选择其中一个有向图游戏 \(G_i\)，在其之上操作一次，无法操作者告负。\(G\) 也成为 \(\{G_i\}\) 的和。

那么 \[ SG(G) = \bigoplus_{i=1}^m SG(G_i) \] \(G\) 先手必胜，当且仅当 \(SG(G) > 0\)。

证明。

类似与 Nim 游戏的做法，考虑 \(x = SG(G)\)，那么仍然找到 \(SG(G_j)\) 第 \(k\) 为和 \(x\) 第 \(k\) 位都为 \(1\)。此时 \(SG(G_j) \oplus x < SG(G_j)\)。考虑 \(\operatorname{mex}\) 运算的本质，就能发现 \(\big[0,SG(G_j)\big)\) 都能在操作一次 \(G_j\) 后得到，因此一定能通过一次操作使得 \(SG(G_j) \leftarrow SG(G_j) \oplus x\)，从而使得 \(SG(G)=0\)。

code

随便写一下 Nim 游戏的 \(SG\) 函数做法。

void pre() {
    // sg[i]表示大小为i的石子堆的SG函数值
    rep(i,1,N) {
        SET(s,0);
        rep(j,1,i) s[sg[i-j]]=1;
        rep(j,0,i) if(!s[j]) { sg[i]=j; break; }
    }
}
signed main() {
    pre();
    int ans=0;
    rep(i,1,n) a[i]=read(), ans^=sg[a[i]];
    if(ans>0) puts("win"); else puts("lose");
}