基础博弈

下面都是石子游戏，轮流取走物品。

方便起见，称场上 $n$ 堆石子 $a_{1}, \dots, a_{n}$ 为局势。

常见的是公平组合游戏：

两个玩家轮流决策，均知道游戏的完整信息。
以玩家无法行动作为结束标志。
游戏一定在有限步结束，且一定能分出胜负。

博弈图和状态

若能将当前局势看作节点，双方的操作看作节点之间的有向边，则博弈可以看作一个图论问题。

若先手必胜，则称该局势为必胜状态；若先手必败，则称该局势为必败状态。

容易验证以下关键结论：

定理 1：一个局势必胜当且仅当存在至少一个后继状态必败。
定理 2：一个局势必败当且仅当它的所有后继状态必胜。

Nim 博弈

共 $n$ 堆分别有 $a_{i}$ 个物品，两人轮流取走任意一堆的任意个物品，不能不取。最后取光者获胜。

原理

对于特殊情况

a_{1} \oplus \dots \oplus a_{n} = 0

若先手取走了 $k$ ，则后手应尝试也取 $k$ ，保持异或和为 $0$ ，因此后手总是可以行动，永远不败。

考虑证明后手总是能取 $k$ 。由异或定义知，一定存在 $a_{i}$ 在 $k$ 的 $h i g h_b i t (k)$ 下是 $1$ ，否则 $a_{i}$ 该位不可能为 $1$ 。

将此 $a_{i}$ 变成 $a_{i}^{'} = a_{i} \oplus k$ ，则该位由 $1$ 变 $0$ ，即有 $a_{i} > a_{i} \oplus k$ 。于是应在 $a_{i}$ 取 $a_{i} - a_{i} \oplus k$ 。

对于

a_{1} \oplus \dots \oplus a_{n} = k \neq 0

由前论述，先手一定存在取走 $k$ 的取法，转为后手永远不败。

cpp

bool Nim(const vector<ll> &a, ll n) {
    ll ans = 0;
    for (auto ai : a)
        ans ^= ai;
    if (ans == 0)
        return true;
    return false;
}

bool Nim(const vector<ll> &a, ll n) {
    ll ans = 0;
    for (auto ai : a)
        ans ^= ai;
    if (ans == 0)
        return true;
    return false;
}

Wythoff 博奕

两堆分别有 $a, b$ 各物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，不可不取。最后取光者获胜。

原理

先手必输的局势称为奇异局势（Cold Position）。

奇异局势可以简单的判断

cpp

const ld phi = 1.6180339887498948482045868343656;
bool Wythoff(ll a, ll b) {
    if (a > b)
        swap(a, b);
    ll t = (ll) (b - a) * phi;
    if (t == a)
        return false;
    return true;
}

const ld phi = 1.6180339887498948482045868343656;
bool Wythoff(ll a, ll b) {
    if (a > b)
        swap(a, b);
    ll t = (ll) (b - a) * phi;
    if (t == a)
        return false;
    return true;
}

所有自然数都出现在奇异局势中，不重不漏。第 $k$ 个奇异局势（其中 $(0, 0)$ 为第 $0$ 个）为

(a_{k - 1}, b_{k - 1}) = (⌊ φ k ⌋, ⌊ φ k ⌋ + k)

其中 $φ = \frac{\sqrt{5} + 1}{2}$ 为黄金分割数。

SG 函数

Todo

基础博弈 ​

博弈图和状态 ​

Nim 博弈 ​

原理 ​

Wythoff 博奕 ​