博弈⚓︎

博弈论（ $\text{Game Theory}$ ）是一门研究决策者在特定规则下如何做出最优决策的数学理论。

博弈的基本要素包括参与者（ $\text{Players}$ ）、策略（ $\text{Strategies}$ ）和收益（ $\text{Payoffs}$ ）。
博弈的几种类型：

完全信息博弈（ $\text{Perfect Information Game}$ ）：所有参与者都知道游戏的所有历史信息
不完全信息博弈（ $\text{Imperfect Information Game}$ ）：某些信息对部分或所有参与者是未知的
零和博弈（ $\text{Zero-sum Game}$ ）：一个参与者的收益完全来自另一个参与者的损失
非零和博弈（ $\text{Non-zero-sum Game}$ ）：参与者的收益可以同时增加或减少

此处只讨论有限的完全信息零和博弈。

策梅洛定理

在有限的完全信息、无随机因素的双人轮流博弈中，如果不存在平局，那么任意局面都只能属于先手必胜态或后手必胜态。

一个双方轮流行动的游戏如果满足以下条件:

在有限步内结束
场上所有信息对双方公开（完全信息）
没有随机因素（确定性）
没有平局（零和）
双方智力均无限（理性）

那么必然存在先手必胜策略或后手必胜策略

巴什博弈⚓︎

巴什博弈（ $\text{Bash Game}$ ）通常描述为两名玩家轮流从一个堆中取走一定数量的物品，目标是让对手成为无法继续取物品的玩家。

假设有 $n$ 个物品，每次玩家可以取走 $1$ 到 $m$ 个物品。则先手玩家的必胜条件是 $n \bmod (m + 1) \neq 0$ 。

为什么？

设 $n \bmod (m + 1) = k$ ，则先手玩家可以在第一次行动时取走 $k$ 个物品，使得剩余物品数变为 $n - k = t(m + 1), t \geq 0$ 。
这样，无论后手玩家取走多少个物品（记为 $x, 1 \leq x \leq m$ ），先手玩家都可以在下一轮取走 $m + 1 - x$ 个物品，使得每次轮到后手玩家时，剩余物品数总是 $(t - 1)(m + 1)$ 的形式。
最终，当物品数减少到 $0$ 时，后手玩家将无法继续取物品，从而先手玩家获胜。
巴什博弈的关键在于通过控制每轮结束时的物品数，使其保持在特定的模数关系下，从而确保自己处于有利位置。

Roy&October之取石子

$n$ 个石子，两人轮流取石子，每次可以取 $p^k$ 个，其中 $p$ 为质数，取完石子的人获胜。问谁能获胜。

Hint

$n=1,2,3,4,5$ 时先手都能一次取完获胜。 $n=6$ 时无论先手取 $1,2,3,4,5$ 个，后手都能取完获胜。
当 $n = 6k$ 时，先手无论取 $p^k$ 个石子，后手都能取 $6k - p^k$ 个石子，使得剩余石子数变为 $6(k-1)$ 。
因此，先手的必胜条件是 $n \bmod 6 \neq 0$ 。

C++

#include <iostream>
using namespace std;

int main() {
  int t, n;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    cin >> n;
    if (n % 6 == 0)
      cout << "Roy wins!" << endl;
    else
      cout << "October wins!" << endl;
  }
}

Nim博弈⚓︎

$\text{Nim}$ 博弈（ $\text{Nim Game}$ ）通常描述为两名玩家轮流从多个堆中取走物品，目标是让对手无法继续进行有效的操作。

在 $\text{Nim}$ 博弈中，玩家可以从任意一个非空的堆中取走任意数量的物品（至少 $1$ 个），并且每个堆的物品数量是有限的。游戏的胜利条件是使对手无法继续进行有效的操作。

$\text{Nim}$ 博弈的关键在于异或运算。通过计算所有堆的物品数量的异或和（ $\text{XOR}$ ），可以判断当前局面是否为先手必胜局面。

具体来说，如果异或和不为 $0$ ，则先手玩家有必胜策略；如果异或和为 $0$ ，则后手玩家有必胜策略。

为什么？

设有 $n$ 堆物品，分别为 $a_1, a_2, \ldots, a_n$ 。定义异或和为 $S = a_1 \oplus a_2 \oplus \ldots \oplus a_n$ 。

如果 $S = 0$ ，则当前局面为后手必胜局面。无论先手玩家如何操作，都会使得异或和变为非零，从而使得后手玩家可以通过适当的操作将异或和重新变为零。
如果 $S \neq 0$ ，则当前局面为先手必胜局面。先手玩家可以通过选择一个堆并取走适当数量的物品，使得新的异或和变为零，从而确保自己处于有利位置。

具体操作如下：

计算当前所有堆的异或和 $S$ 。
找到一个堆 $a_i$ ，使得 $a_i \oplus S < a_i$ 。这意味着通过取走 $a_i - (a_i \oplus S)$ 个物品，可以使得新的异或和变为零。
执行上述操作后，轮到对手时，异或和为零，对手无论如何操作，都会使得异或和变为非零，从而使得先手玩家可以继续保持优势。

通过这种策略，先手玩家可以确保在每次轮到自己时，局面总是处于有利位置，最终赢得游戏。

【模板】Nim 游戏

C++

#include <iostream>
#include <vector>
using namespace std;

bool nim_game(const vector<int> &piles) {
  int xor_sum = 0;
  for (int stones : piles) { xor_sum ^= stones; }
  return (xor_sum != 0);
}

void solve() {
  int n;
  cin >> n;
  vector<int> piles(n);
  for (int i = 0; i < n; i++) { cin >> piles[i]; }
  if (nim_game(piles)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t t = 1;
  cin >> t;
  while ((t--) != 0) { solve(); }
  return 0;
}

反尼姆博弈（反常游戏）⚓︎

反尼姆博弈（ $\text{Misère Nim}$ ）是一种变体的 $\text{Nim}$ 博弈，规则与 $\text{Nim}$ 博弈类似，但胜利条件相反，即最后一个取走物品的玩家输掉游戏。

在反尼姆博弈中，玩家仍然可以从任意一个非空的堆中取走任意数量的物品（至少 $1$ 个），但目标是避免成为无法继续取物品的玩家。换句话说，最后一个取走物品的玩家输掉游戏。

反尼姆博弈的分析与 $\text{Nim}$ 博弈类似，但需要考虑特殊情况。具体来说，反尼姆博弈的胜利条件可以通过以下规则来判断：

如果所有堆的物品数量均为 $1$
- 如果堆的数量为奇数，则当前局面为后手必胜局面。
- 如果堆的数量为偶数，则当前局面为先手必胜局面。
如果存在至少一个堆的物品数量大于 $1$ ，则当前局面与标准的 $\text{Nim}$ 博弈相同
- 异或和不为 $0$ 时，先手玩家有必胜策略；
- 异或和恰为 $0$ 时，后手玩家有必胜策略。

为什么？

设有 $n$ 堆物品，分别为 $a_1, a_2, \ldots, a_n$ 。定义异或和为 $S = a_1 \oplus a_2 \oplus \ldots \oplus a_n$ 。

如果所有堆的物品数量均为 $1$ ，则游戏变为两人轮流取走单个物品的游戏。
- 当堆的数量为奇数时，先手玩家无论如何取走一个物品，都会使得剩余堆的数量变为偶数，从而使得后手玩家可以通过取走一个物品，使得剩余堆的数量再次变为奇数。最终，当只剩下一个堆时，先手玩家只能取走最后一个物品，从而输掉游戏。
- 当堆的数量为偶数时，先手玩家可以通过取走一个物品，使得剩余堆的数量变为奇数，从而确保自己处于有利位置。最终，当只剩下一个堆时，后手玩家只能取走最后一个物品，从而输掉游戏。
如果存在至少一个堆的物品数量大于 $1$ ，则可以通过适当的操作将局面转化为标准的 $\text{Nim}$ 博弈局面。
- 先手玩家可以通过选择一个堆并取走适当数量的物品，使得新的异或和变为零，从而确保自己处于有利位置。
- 这样，无论后手玩家如何操作，都会使得异或和变为非零，从而使得先手玩家可以继续保持优势。

通过这种策略，先手玩家可以确保在每次轮到自己时，局面总是处于有利位置，最终赢得游戏。

小约翰的游戏

C++

#include <iostream>
#include <vector>
using namespace std;

bool misere_nim_game(vector<int> &piles) {
  int xor_sum    = 0;
  int count_ones = 0;  // 只有一颗石头的堆数
  for (int stones : piles) {
    xor_sum ^= stones;
    if (stones == 1) { count_ones++; }
  }
  if (count_ones == piles.size()) {  // 全是单石堆
    return (count_ones % 2 == 0);    // 石头堆数为偶数时，先手必胜
  }
  return (xor_sum != 0);  // 否则与普通尼姆博弈相同
}

void solve() {
  int n;
  cin >> n;
  vector<int> piles(n);
  for (int i = 0; i < n; i++) { cin >> piles[i]; }
  if (misere_nim_game(piles)) {
    cout << "John\n";
  } else {
    cout << "Brother\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t t = 1;
  cin >> t;
  while ((t--) != 0) { solve(); }
  return 0;
}

斐波那契博弈⚓︎

斐波那契博弈（ $\text{Fibonacci Game}$ ）通常描述为两名玩家轮流从一个堆中取走物品，目标是避免成为无法继续取物品的玩家。

在斐波那契博弈中，第一次可以取走任意数量的物品（至少 $1$ 个），但不能全部取完。之后每次玩家只能取走不超过上一次玩家取走数量的物品的 $2$ 倍。游戏的胜利条件是使对手无法继续进行有效的操作。

齐肯多夫定理（

$\text{Zeckendorf's Theorem}$ ）

每个正整数都可以唯一表示为若干不相邻斐波那契数之和（不包括 $F_1 = 1$ 和 $F_2 = 1$ ）。

Example

例如， $100 = 89 + 8 + 3$ ，其中 $89, 8, 3$ 都是斐波那契数，并且它们在斐波那契数列中不相邻。

为什么？

设斐波那契数列为 $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \ldots$ 。
对于任意正整数 $n$ ，可以通过以下步骤找到其斐波那契表示：

找到最大的斐波那契数 $F_k$ ，使得 $F_k \leq n$
将 $n$ 减去 $F_k$ ，得到新的数 $n' = n - F_k$
重复步骤 $1$ 和 $2$ ，直到 $n'$ 为 $0$

在这个过程中，由于每次选择的斐波那契数都是最大的，因此不会选择相邻的斐波那契数，否则可以将这两个相邻的斐波那契数替换为它们的和，从而得到更大的斐波那契数，违反了选择最大的原则。
通过这种方式，可以确保每个正整数都可以表示为若干不相邻斐波那契数之和，从而保证了表示的唯一性。

当前局面为 $n$ 个物品时，先手玩家的必胜条件是 $n$ 不是斐波那契数。

为什么？

设斐波那契数列为 $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \ldots$ 。

如果 $n$ 是斐波那契数，即 $n = F_k$ ，则先手玩家无论取走多少个物品（记为 $x$ ，其中 $1 \leq x < F_k$ ），都会使得剩余物品数变为 $F_k - x$ 。
根据斐波那契数列的性质， $F_k - x$ 可以表示为若干不相邻的斐波那契数之和（齐肯多夫定理）。
因此，后手玩家可以通过适当的操作，将剩余物品数逐步减少到下一个斐波那契数，从而确保自己处于有利位置。
如果 $n$ 不是斐波那契数，则先手玩家可以通过选择一个合适的数量 $x$ ，使得剩余物品数变为下一个较小的斐波那契数 $F_m$ （其中 $F_m < n < F_{m+1}$ ）。
这样，无论后手玩家如何操作，都会使得剩余物品数变为非斐波那契数，从而使得先手玩家可以继续保持优势。

通过这种策略，先手玩家可以确保在每次轮到自己时，局面总是处于有利位置，最终赢得游戏。

取石子游戏

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, max_n = -1;
  vector<int64_t> n_values;
  while (cin >> n) {
    if (n == 0) { break; }
    n_values.push_back(n);
    max_n = max(max_n, n);
  }

  vector<int64_t> fib = {0, 1};
  while (true) {
    int64_t next = fib[fib.size() - 1] + fib[fib.size() - 2];
    fib.push_back(next);
    if (next > max_n) { break; }
  }

  for (int64_t n : n_values) {
    if (binary_search(fib.begin(), fib.end(), n)) {
      cout << "Second win\n";
    } else {
      cout << "First win\n";
    }
  }
  return 0;
}

如果允许第一次取完所有物品，则先手玩家必胜。但是先手想知道，自己能否通过第一次不取完所有物品的方式，确保自己在后续的游戏中仍然处于必胜位置。也就是第一次应该至少取走多少个物品就能确保自己必胜。

将 $n$ 分解为若干不相邻斐波那契数之和 $n = F_{k_1} + F_{k_2} + \ldots + F_{k_m}$ ，其中 $F_{k1} < F_{k2} < \ldots < F_{km}$ ，则先手玩家至少需要取走 $F_{k_1}$ 个物品，才能确保自己处于必胜位置。

为什么？

将石子总数划分为若干不相邻的斐波那契数，每次取当前最小的斐波那契数 $f_i$ ，下一部分的最小值为 $f_{i+2}$ 。由于 $2f_i < f_{i+2}$ ，保证了划分的合法性。

先手策略：

先手每次取走当前最小的斐波那契数
由于后手无法一次取走下一个斐波那契数，后手只能取部分石子
取完当前部分后，先手仍然可以继续按照相同的策略操作

HRPA

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int64_t fibonacci_game(int64_t n) {
  if (n <= 2) { return 1; }
  vector<int64_t> fib = {1, 2};  // 斐波那契数列
  while (true) {
    int64_t next = fib[fib.size() - 1] + fib[fib.size() - 2];
    fib.push_back(next);
    if (next > n) { break; }
  }
  // 分解n, 找到最小的斐波那契数
  while (true) {
    auto it = std::lower_bound(fib.begin(), fib.end(), n);  // 找到第一个大于等于n的斐波那契数
    if (*it == n) { return n; }                             // n 本身就是斐波那契数
    --it;                                                   // it 指向小于 n 的最大斐波那契数
    n -= *it;
  }
}

int main() {
  int64_t n;
  cin >> n;
  cout << fibonacci_game(n) << "\n";
  return 0;
}

威佐夫博弈⚓︎

威佐夫博弈（ $\text{Wythoff's Game}$ ）通常描述为两名玩家轮流从两个堆中取走物品，目标是避免成为无法继续取物品的玩家。

在威佐夫博弈中，玩家可以从任意一个非空的堆中取走任意数量的物品（至少 $1$ 个），或者从两个堆中同时取走相同数量的物品。游戏的胜利条件是使对手无法继续进行有效的操作。

结论：

当前局面 $(a, b)$ （ $a \leq b$ ）为后手必胜局面，当且仅当存在整数 $k$ ，使得 $a = \lfloor k \phi \rfloor$ 且 $b = \lfloor k \phi^2 \rfloor$ ，其中 $\phi = \frac{1 + \sqrt{5}}{2}$ 是黄金比例。

由 $\phi^2 = \phi + 1$ 可得 $b - a = \lfloor k \phi^2 \rfloor - \lfloor k \phi \rfloor = \lfloor k (\phi + 1) \rfloor - \lfloor k \phi \rfloor = \lfloor k \phi \rfloor + k - \lfloor k \phi \rfloor = k$ 。

因此， $b - a = k$ 。

判断条件：

$a = \lfloor k \phi \rfloor \Longrightarrow a \leq k \phi \lt a + 1 \Longrightarrow 2a \leq (1 + \sqrt{5})k \lt 2(a + 2)$ (1)

$n = \lfloor x \rfloor \Longrightarrow n \leq x \lt n + 1$

将 $k$ 移项并且两边平方得： $(2a - k)^{2} \leq 5k^{2} \lt (2(a + 1) - k)^{2}$

取石子游戏 |【模板】威佐夫博弈

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;

bool wythoff_game(int64_t a, int64_t b) {
  if (a > b) { swap(a, b); }
  int64_t k     = b - a;
  int64_t left  = (2 * a - k) * (2 * a - k);
  int64_t mid   = 5 * k * k;
  int64_t right = (2 * (a + 1) - k) * (2 * (a + 1) - k);
  // 先手必胜局面
  return mid < left || mid >= right;  // 等价于 a != floor(k * phi)
}

int main() {
  int64_t a, b;
  cin >> a >> b;
  if (a == 0 && b == 0) {  // 特判
    cout << 0 << "\n";
    return 0;
  }
  cout << (wythoff_game(a, b) ? 1 : 0) << "\n";
  return 0;
}

SG函数⚓︎

在组合博弈论中， $SG$ 函数（ $\text{Sprague-Grundy Function}$ ）是一种用于分析和解决无偏博弈（ $\text{Impartial Game}$ ）的数学工具。 $SG$ 函数的基本思想是将每个局面映射到一个非负整数，称为该局面的格朗特值（ $\text{Grundy Value}$ ）。通过计算格朗特值，可以判断当前局面是必胜局面还是必败局面。

对于任意一个无向图上的无穷游戏（如取石子游戏），每个局面都可以分配一个非负整数 $SG$ 值。

$SG$ 值的递推定义：

终止局面（无法再走）的 $SG$ 值为 0
非终止局面的 $SG$ 值为所有下一步能到达的局面 $SG$ 值的最小非负整数（MEX）。

$SG$ 定理

一个由若干子游戏组成的合成游戏的 $SG$ 值为各子游戏 $SG$ 值的异或和。

因此，合成游戏的先手必胜条件是各子游戏 $SG$ 值的异或和不为 $0$

计算 $SG$ 函数

C++

int get_sg(int state, const vector<vector<int>> &moves, vector<int> &sg) {
  if (sg[state] != -1) { return sg[state]; }
  unordered_set<int> next_sg;
  for (int move : moves[state]) { next_sg.insert(get_sg(move, moves, sg)); }
  int g = 0;
  while (next_sg.contains(g)) { ++g; }
  return sg[state] = g;
}

博弈⚓︎

巴什博弈⚓︎

Nim博弈⚓︎

反尼姆博弈（反常游戏）⚓︎

斐波那契博弈⚓︎

威佐夫博弈⚓︎

SG函数⚓︎

评论