2.6-组合博弈入门

组合博弈入门

组合游戏

要求

1. 有两个玩家；
2. 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；
3. 游戏双方轮流操作；
4. 双方的每次操作必须符合游戏规定；
5. 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；
6. 无论如何操作，游戏总能在有限次操作后结束。

必败点和必胜点（P点&N点）

必败点（P点）：上一个选手（Previous player）将取胜的位置成为必败点。

必胜点（N点）：下一个选手（Next player）将取胜的位置成为必胜点。

必败（必胜）点属性

1. 所有终结点是必败点（P点）；

2. 从任何必胜点（N点）操作， 至少有一种方法可以进入必败点（P点）；

3. 无论如何操作，从必败点（P点）都只能进入必败点（P点）。

取子游戏的算法实现

步骤1：将所有终结位置标记为必败点（P点）；

步骤2：将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）

步骤3：如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；

步骤4：如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

NIM游戏

NIM游戏是组合博弈中的经典游戏。游戏场景如下：有若干堆石子，每堆石子的数量都是有限的，游戏双方轮流从某一堆中取走任意数量的石子（至少取1个），取走最后一个石子的玩家获胜。

NIM游戏的二进制证明

设游戏中有 $n$ 堆石子，各堆石子数分别为 $a_1,a_2,\cdots ,a_n$。将这些石子数都表示成二进制形式。

定义NIM - 和为 $a_1\oplus a_2\oplus \cdots \oplus a_n$（$\oplus$ 表示按位异或运算）。

1. 定理：NIM游戏中，当且仅当 $a_1\oplus a_2\oplus \cdots \oplus a_n=0$ 时，当前局面为必败局面；当 $a_1\oplus a_2\oplus \cdots \oplus a_n\ne 0$ 时，当前局面为必胜局面。

2. 证明

   • 终结局面：当所有堆石子数都为 $0$ 时，$0\oplus 0\oplus \cdots \oplus 0=0$，此时是必败局面。

   • 必胜局面可转化为必败局面：若 $a_1\oplus a_2\oplus \cdots \oplus a_n=k\ne 0$，则 $k$ 的二进制表示中至少有一位为 $1$。在 $a_1,a_2,\cdots ,a_n$ 中一定存在一个 $a_i$，其对应的二进制位上也为 $1$。通过从第 $i$ 堆中取走一定数量的石子，使得取走后这堆石子数变为 $a_i^{\prime }$，满足 $a_1\oplus a_2\oplus \cdots \oplus a_{i-1}\oplus a_i^{\prime }\oplus a_{i+1}\oplus \cdots \oplus a_n=0$。

   • 必败局面只能转化为必胜局面：若 $a_1\oplus a_2\oplus \cdots \oplus a_n=0$，假设从第 $i$ 堆取走石子后变为 $a_i^{\prime }$，那么 $a_1\oplus a_2\oplus \cdots \oplus a_{i-1}\oplus a_i^{\prime }\oplus a_{i+1}\oplus \cdots \oplus a_n\ne 0$。因为异或运算的性质决定了，改变其中一个数后，异或和必然改变。

SG函数

对于一个组合游戏的每个状态 $x$，定义其SG函数值 $SG(x)$。

1. 计算方法：

   • 首先，对于所有的终结状态 $x$，$SG(x)=0$。

   • 对于非终结状态 $x$，设 $x$ 能通过一步操作到达的所有状态为 $y_1,y_2,\cdots ,y_k$，则 S G ( x ) = m e x ( { S G ( y 1 ) , S G ( y 2 ) , ⋯ , S G ( y k ) } ) SG(x)=mex(\{SG(y_1),SG(y_2),\cdots,SG(y_k)\}) SG(x)=mex({SG(y1​),SG(y2​),⋯,SG(yk​)})，其中 $mex$ 函数是求一个集合中未出现的最小非负整数。例如，若集合为 { 0 , 1 , 3 } \{0,1,3\} {0,1,3}，则 m e x ( { 0 , 1 , 3 } ) = 2 mex(\{0,1,3\}) = 2 mex({0,1,3})=2。

2. 作用：

• 当一个组合游戏可以拆分为多个子游戏时，整个游戏的胜负情况可以通过各个子游戏的SG函数值的异或和来判断。设整个游戏由 $n$ 个子游戏组成，每个子游戏的当前状态对应的SG函数值分别为 $S{G}_1,S{G}_2,\cdots ,S{G}_n$，则当 $S{G}_1\oplus S{G}_2\oplus \cdots \oplus S{G}_n=0$ 时，当前游戏局面为必败局面；当 $S{G}_1\oplus S{G}_2\oplus \cdots \oplus S{G}_n\ne 0$ 时，当前游戏局面为必胜局面。这使得我们可以将复杂的组合游戏分解为简单子游戏来分析胜负情况。

组合游戏的并

定义：组合游戏的并是指将多个组合游戏同时进行的一种游戏形式。假设有 $k$ 个组合游戏 $G_1,G_2,\cdots ,G_k$，组合游戏的并 $G=G_1+G_2+\cdots +G_k$。在游戏 $G$ 中，玩家的一步操作是在 $G_1,G_2,\cdots ,G_k$ 中的某一个游戏中进行一步合法操作。

SG 定理：对于组合游戏的并 $G=G_1+G_2+\cdots +G_k$，其某状态的 $SG$ 值等于各个子游戏在相应状态下 $SG$ 值的异或和，即 $SG(G)=SG(G_1)\oplus SG(G_2)\oplus \cdots \oplus SG(G_k)$。这个定理非常重要，它使得我们可以通过分别计算各个子游戏的 $SG$ 值，再求异或和来判断组合游戏并的胜负情况。

以下是一个简单示例代码，展示如何利用 SG 定理计算组合游戏的并的胜负情况（假设已有 sg 函数用于计算单个游戏状态的 $SG$ 值）

#include<bits/stdc++.h>using namespace std;// 假设已经有了计算单个游戏 SG 值的函数 sgint sg(int state) {// 具体实现省略，根据实际游戏规则编写return 0; }计算组合游戏的并的 SG 值int combinedSG(int numGames, int* states) {int result = 0;for (int i = 0; i < numGames; ++i) {result ^= sg(states[i]);}return result;}// 判断胜负示例函数void determineWinner(int numGames, int* states) {int combinedSgValue = combinedSG(numGames, states);if (combinedSgValue == 0) {cout << "当前局面为必败局面" << endl;}else {cout << "当前局面为必胜局面" << endl;}}int main() {int numGames = 3;  // 假设有 3 个子游戏int states[3] = {1, 2, 3};  // 各个子游戏的状态determineWinner(numGames, states);return 0;}