这篇文章上次修改于 507 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记5——组合博弈

问题引入

问题：一共有10张牌，你与一个人进行游戏，每次只能取走1或2或3张牌，谁取走最后一张，你是先手，如何获胜。

题解：根据以前的经验，我们能保证一轮取走4张牌，而且设定每一轮我们是后手，对手取走1张，我取走3张。对手取走2张，我也取走2张。对手取走3张，我取走1张。易得结果。

思考总结

但在进行这个游戏的时候，我们心中就有个概念，只要我这么走，无论对方怎么走，我的结果就是赢，我们称这个状态为必胜点，同理，对于除了必胜点意外的其它点，对方就会必胜，此状态我们称为必败点

从这个角度上再来看这道题，我们可以让剩余的卡片数量作为状态，并且我们设必胜为N必败为P

剩余卡片	0	1	2	3	4	5	6	7	8	9	10
状态情况	P	N	N	N	P	N	N	N	P	N	N

根据此次标记，我们可以找到一些规律：

终结位置可以直接标记为必败点（没有牌给对面选意味着对面输了）
所有能进入必败点的前置点都为必胜点（我能进入让对方必输的状态）
如果该点进行所有操作能进入的点都为必胜，则改点必败（无论怎么下都会让对方必胜）

按照该规律，我们还可以进行变版游戏，每次只能取走1或3或4张牌，这时我们难以找到像开始4的倍数规律，但根据必败必胜点规律，我们依旧可以打表

剩余卡片	0	1	2	3	4	5	6	7	8	9	10
状态情况	P	N	P	N	N	N	N	P	N	P	N

就又可以判断如何必胜

按照此规律不能只局限于线性表，类似于二维表，甚至图的结构都可以解决。

Nim游戏（Nim-Sum）

游戏规则

有两个玩家，三堆扑克牌（比如：分别是5, 7, 9张），双方轮流操作
玩家的每次操作是选择其中某一堆牌，然后从中取走任意张
最后一次取牌的一方为获胜方

初次尝试

按照我们原本的思路来看，这道题再根据必胜必败点，我们将(a1, a2, a3)为三个三堆扑克牌的剩余牌数量

可得(0, 0, 0)为必败点，(0, 0, x)为必胜点，(0, 1, 1)为必败点，n(0, k, k)为必败点。

依据这样来计算，将会花费大量空间，我们需要更好的规律来计算这类问题。

引入概念: Nim-Sum

定义

Nim-Sum的运算对象(x1, x2, x3 … xn)

(x1, x2, x3 … xn)和(y1, y2, y3 … yn)的Nim-Sum是(z1, z2, z3 … zn)

其中对于所有 zk = xk + yk (mod 2) （k=0…m）

定理

对于本游戏，每个游戏状态都有一个Nim-Sum，就是对所有牌堆的牌数量进行Nim-Sum

对于nim游戏的某个位置(x1,x2,x3)，当且仅当它各部分的nim-sum等于0时（即x1⊕x2⊕x3=0），则当前位于必败点。

例如点(0, 0, 0)属于必败点，(3, 5, 6) 即b11^b101^b110 = 0，即必败点。

证明

对于每次取牌，都可以取任意张，唯一的局限性就是，只能取其中的一堆的牌，只有一堆的牌的数量会变化。

同时，假如此时状态的Nim-Sum是0，那么修改其中一堆牌的二进制必定会影响nim-sum而使其不为0，所以nim-sum=0的点（除了最终状态）永远无法一步到达最终状态，故nim-sum=0的点为必败点。

同时，又因为nim-sum不为0的状态点，我们要去除除二进制的多个1，当最高位有1的时候，说明三堆牌中也有最高位为1的，修改它，并将之后所有的1位变为0，也就是nim-sum不为0的状态点都能一步到达nim-sum=0的点，能到达必败点的点就是必胜点，一旦nim-sum不为0，其必胜。

例子：

13 = 1101b  ->  0100b
12 = 1100b  ->  0101b
 8 = 1000b  ->  0001b
 ____________异或运算
     1001b  ->  0000b（目的）

此时，修改任意一堆牌以符合要求，见以上修改，即可进入必败点。

bool isPointWin(const vector<int> & nims){
    int nimSum = 0;
    for(int x: nims){
		nimSum ^= x;
    }
    return nimSum != 0;
}

SG函数（Sprague-Grundy Function）

定义

SG函数同样为每个状态建立了一个值

g(x) =min{n ≥ 0 : n != g(y) for y ∈ F(x)}

即X节点的SG值是除X的后继节点的SG值后的最小的非负整数。

定理

必败点: 当节点x的 sg(x) = 0
必胜点: 当节点x的 sg(x) > 0

证明

终止状态的SG函数值为0。
如果SG(x)不为0，根据SG函数的定义，x的后继中一定存在某一个状态的SG函数值为0，我们称之为y。那么，我们一定可以通过操作将x转移到y，从而留给对手一个SG函数值为0的状态。
如果SG(x)为0，根据SG函数的定义，x的后继中不存在SG函数值为0的状态。所以，无论如何操作，都一定会留给对手一个SG函数值不为0的状态。

因此，如果玩家处于一个SG函数值不等于0的状态，那么他是必胜的，否则他是必败的。SG函数确实可以作为必胜点进行使用。

组合型组合博弈

题目

有三堆扑克牌，分别为5,7,9张；
双方轮流取牌，每次可以选择任意一堆牌取走1~3张；
最后取牌的一方获胜。

定理

如果图游戏G由若干子图游戏Gi组成，即：G = G1 +···+ Gn ，假设gi是Gi（i = 1, …,n）的SG函数值，那么，图游戏G的SG值计算如下：
g(x1, ...,xn) = g1(x1)⊕...⊕gn(xn)

题解

按照本题套定理，三堆扑克牌也就属于三个子游戏，每个点都有自己的sg值

int calculateSG(const vector<int>& moves, int state, unordered_set<int>& memo) {
    if (memo.find(state) != memo.end()) {
        return memo[state];
    }

    unordered_set<int> reachableStates;

    for (int move : moves) {
        int nextState = state - move;

        if (nextState >= 0) {
            int nextSG = calculateSG(moves, nextState, memo);
            reachableStates.insert(nextSG);
        }
    }

    int currentSG = 0;
    while (reachableStates.find(currentSG) != reachableStates.end()) {
        currentSG++;
    }

    memo[state] = currentSG;  // 记忆化
    return currentSG;
}

int main() {
    // 定义游戏的可行动集合
    vector<int> moves = {1, 2, 3};

    // 输入初始状态
    int initial_state;
    cout << "输入博弈的初始状态（正整数）：";
    cin >> initial_state;

    unordered_set<int> memo;

    int sgValue = calculateSG(moves, initial_state, memo);

    cout << "SG值为：" << sgValue << endl;

    return 0;
}

证明

这里简单说明一下

我们将sg用于三堆牌的行为，同时，一次操作只能修改一堆牌。

同步到这个问题，三堆牌都有自己的sg值来代表必胜点和必败点

sg值是根据后继节点判断的，一个sg的值为5，代表它的后继必有0,1,2,3,4。类似于取牌游戏，5可以任意变成5以下的数字，sg值的变化和取牌等价，取牌也可以取任意张使得sg值随意变小，直到三堆牌的sg都变为0，便可直接结合应用。

严谨证明参考

Mai Icy