当前位置：首页 > news >正文

Wythoff Game

news 2026/6/16 14:06:32

模型介绍

Wythoff Game 是一个经典的二人博弈游戏，规则如下：

有两堆物品，分别有 \(a\) 和 \(b\) 个；
两名玩家轮流操作，每次可以：

从其中一堆取任意数量的物品（至少 \(1\) 个）；
从两堆中同时取相同数量的物品（至少 \(1\) 个）；

最后取光所有物品的玩家获胜。

历史背景

Wythoff Game 由荷兰数学家 Willem Abraham Wythoff 在 \(1907\) 年提出。这个游戏是组合博弈论中的重要模型，其解与黄金比例有着深刻的联系。

核心结论与证明

奇异局势（必败态）

Wythoff Game 存在一系列的必败位置，称为"奇异局势"。这些位置可以表示为：

\[(a_k,b_k)=(\lfloor k\varphi\rfloor,\lfloor k\varphi^2\rfloor)=(\lfloor k\varphi\rfloor,\lfloor k\varphi\rfloor+k) \]

其中 \(\varphi=\frac{1+\sqrt5}{2}\approx 1.61803\) 是黄金比例，\(k=0,1,2,\cdots\)

前几个奇异局势：

\((0,0)\)
\((1,2)\)
\((3,5)\)
\((4,7)\)
\((6,10)\)
\((8,13)\)
\((9,15)\)
\(\cdots\)

判断方法

对于任意位置 \((a,b)\)（假设 \(a\le b\)）：

计算 \(k=b-a\)；
计算 \(a_k=\lfloor k\varphi\rfloor\)；
如果 \(a=a_k\)，则该位置是奇异局势（先手必败）；
否则，先手必胜。

证明

Beatty 定理背景：

如果 \(\alpha\) 和 \(\beta\) 是正无理数且满足 \(\frac{1}{\alpha}+\frac{1}{\beta}=1\)，那么序列 \(\lfloor n\alpha\rfloor\) 和 \(\lfloor n\beta\rfloor\) 恰好覆盖所有正整数且不相交。

构造证明：

令 \(\alpha=\varphi,\beta=\varphi²\)；
由于 \(\varphi\) 和 \(\varphi^2\) 满足 \(\frac{1}{\varphi}+\frac{1}{\varphi^2}=1\)；
根据 Beatty 定理，序列 \(\lfloor k\varphi\rfloor\) 和 \(\lfloor k\varphi^2\rfloor\) 覆盖所有正整数；
且 \(\lfloor k\varphi^2\rfloor=\lfloor k\varphi+k\rfloor=\lfloor k\varphi\rfloor+k\)。

转移性质证明：

从任意奇异局势出发：

如果只取一堆：会破坏 Beatty 序列的覆盖性质；
如果同时取两堆：差值 \(k\) 不变，但较小的数会改变。

从任意非奇异局势出发：

总能通过一次操作到达奇异局势。

代码实现

基础判断

#include <bits/stdc++.h>
#define int long longusing namespace std;const double kPhi = (1.0 + sqrt(5.0)) / 2.0;// 判断是否为奇异局势（必败态）
bool isLosingPosition(int a, int b) {if (a > b) swap(a, b);int k = b - a;int ak = floor(k * kPhi);return a == ak;
}// 获取必胜策略
void findWinningMove(int a, int b, int& take_from, int& take_count) {if (a > b) swap(a, b);int k = b - a;int ak = floor(k * kPhi);int bk = ak + k;if (a == ak) {// 已经是奇异局势，没有必胜策略take_from = -1;take_count = -1;return;}if (a > ak) {// 从两堆同时取 (a - ak) 个take_from = 0;  // 0 表示同时取两堆take_count = a - ak;} else {// 需要调整使得到达奇异局势// 从较大的堆取，使得较小的堆等于某个奇异局势的第一分量for (int i = 0; i <= k; i++) {int candidate_ak = floor(i * kPhi);int candidate_bk = candidate_ak + i;if (a == candidate_ak && b > candidate_bk) {take_from = 2;  // 从第二堆取take_count = b - candidate_bk;return;}if (a == candidate_bk && b > candidate_ak) {take_from = 2;take_count = b - candidate_ak;return;}}// 如果上述方法不行，从任意一堆取1个take_from = 1;take_count = 1;}
}

完整游戏模拟

#include <bits/stdc++.h>
#define int long longusing namespace std;class WythoffGame {private:int pileA, pileB;const double PHI = (1.0 + sqrt(5.0)) / 2.0;public:WythoffGame(int a, int b) : pileA(a), pileB(b) {}bool isGameOver() {return pileA == 0 && pileB == 0;}bool isValidMove(int from, int count) {if (count <= 0) return false;if (from == 1) {  // 从第一堆取return count <= pileA;} else if (from == 2) {  // 从第二堆取return count <= pileB;} else if (from == 0) {  // 从两堆同时取return count <= min(pileA, pileB);}return false;}bool makeMove(int from, int count) {if (!isValidMove(from, count)) return false;if (from == 1) {pileA -= count;} else if (from == 2) {pileB -= count;} else if (from == 0) {pileA -= count;pileB -= count;}return true;}void printState() {cout << "当前状态: (" << pileA << ", " << pileB << ")" << endl;}// 电脑的智能移动void computerMove() {int from, count;findWinningMove(pileA, pileB, from, count);if (from == -1) {// 必败态，随机移动if (pileA > 0) {from = 1;count = 1;} else if (pileB > 0) {from = 2;count = 1;} else {from = 0;count = 0;}}makeMove(from, count);cout << "电脑: ";if (from == 0) {cout << "从两堆同时取 " << count << " 个" << endl;} else if (from == 1) {cout << "从第一堆取 " << count << " 个" << endl;} else {cout << "从第二堆取 " << count << " 个" << endl;}}
};void playWythoffGame() {WythoffGame game(15, 25);bool playerTurn = true;cout << "Wythoff Game 开始！" << endl;cout << "初始状态: (15, 25)" << endl;cout << "移动方式: 1-从第一堆取, 2-从第二堆取, 0-从两堆同时取" << endl;while (!game.isGameOver()) {game.printState();if (playerTurn) {int from, count;cout << "你的回合 - 输入移动方式(0,1,2)和数量: ";cin >> from >> count;if (!game.makeMove(from, count)) {cout << "无效移动！请重新输入。" << endl;continue;}} else {game.computerMove();}playerTurn = !playerTurn;}cout << "游戏结束！" << (playerTurn ? "电脑" : "玩家") << "获胜！" << endl;
}

变种题目与解法

变种 1：最后取者输

规则：其他规则相同，但最后取物品的人输；
解法：需要重新分析奇异局势。

bool isLosingPositionMisere(int a, int b) {if (a == 0 && b == 0) return false;  // 没有物品，上一个人已经输了if (a == 1 && b == 1) return true;   // 特殊情况// 其他情况与正常游戏类似，但需要调整return isLosingPosition(a, b);
}

变种 2：多堆 Wythoff Game

规则：有 \(n\) 堆物品，每次可以：

从任意一堆取任意数量；
从所有堆中取相同数量；

解法：使用 Grundy 数。

int calculateGrundy(int n) {vector<int> grundy(n + 1, 0);for (int i = 1; i <= n; i++) {set<int> moves;// 从当前堆取任意数量for (int take = 1; take <= i; take++) {moves.insert(grundy[i - take]);}// 从所有堆取相同数量（在单堆情况下无法表示）// 在多堆情况下需要特殊处理int g = 0;while (moves.count(g)) g++;grundy[i] = g;}return grundy[n];
}bool multiPileWythoff(vector<int>& piles) {int xor_sum = 0;for (int pile : piles) {xor_sum ^= calculateGrundy(pile);}return xor_sum != 0;
}

变种3：受限 Wythoff Game

规则：每次取物品数量有限制；
解法：动态规划。

bool limitedWythoff(int a, int b, int max_take) {vector<vector<bool>> dp(a + 1, vector<bool>(b + 1, false));for (int i = 0; i <= a; i++) {for (int j = 0; j <= b; j++) {// 从第一堆取for (int take = 1; take <= min(i, max_take); take++) {if (!dp[i - take][j]) {dp[i][j] = true;break;}}if (dp[i][j]) continue;// 从第二堆取for (int take = 1; take <= min(j, max_take); take++) {if (!dp[i][j - take]) {dp[i][j] = true;break;}}if (dp[i][j]) continue;// 从两堆同时取for (int take = 1; take <= min(i, j, max_take); take++) {if (!dp[i - take][j - take]) {dp[i][j] = true;break;}}}}return dp[a][b];
}