在许多地方曾经流行过这样一个小游戏 note摆出三堆硬币，分别包含 3 枚、5 枚、7 枚。两人轮流行动，每次可以任选一堆，从中取走任意多枚硬币，可把一堆取光，但不能不取。取走最后一枚硬币者获得胜利。 这类游戏可以推广为更加一般的形式： note给定 nnn 堆物品，第 iii 堆物品有 AiA_iAi 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手能否必胜。 我们把这种游戏称为 NIM 博弈。 把游戏过程中面临的状态称为局面。 整个游戏第一个行动的称为先手，第二个行动的称为后手。 若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。 所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对手面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。 我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。NIM 博弈不存在平局，只有先手必胜和先手必败两种情况。 importantNIM 博弈先手必胜，当且仅当： A1 xor A2 xor … xor An≠0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0A1 xor A2 xor … xor An=0 证明 终态局面：所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 A1 xor A2 xor … xor An=0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0A1 xor A2 xor … xor An=0。 必胜态转化：对于任意一个局面，如果 A1 xor A2 xor … xor An=x≠0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = x \neq 0A1 xor A2 xor … xor An=x=0，设 xxx 的二进制表示下最高位的 1 在第 kkk 位，那么至少存在一堆石子 AiA_iAi，它的第 kkk 位是 1。显然 Ai xor x<AiA_i \text{ xor } x < A_iAi xor x<Ai，我们就从 AiA_iAi 堆中取走若干石子，使其变为 Ai xor xA_i \text{ xor } xAi xor x，就得到了一个各堆石子数异或起来等于 0 的局面。 必败态转化：对于任意一个局面，如果 A1 xor A2 xor … xor An=0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0A1 xor A2 xor … xor An=0，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于 0。可用反证法证明，假设 AiA_iAi 被取成了 Ai′A_i'Ai′，并且 A1 xor A2 xor … xor Ai′ xor … xor An=0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_i' \text{ xor } \dots \text{ xor } A_n = 0A1 xor A2 xor … xor Ai′ xor … xor An=0。由异或运算的消去律得 Ai′=AiA_i' = A_iAi′=Ai，与“不能不取石子”的规则矛盾。 综上所述，再由数学归纳法可知，A1 xor A2 xor … xor An≠0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n \neq 0A1 xor A2 xor … xor An=0 为必胜局面。存在一种行动让对手面临“各堆石子异或起来等于 0”。A1 xor A2 xor … xor An=0A_1 \text{ xor } A_2 \text{ xor } \dots \text{ xor } A_n = 0A1 xor A2 xor … xor An=0 为必败局面，无论如何行动，都会让对手面临一个“各堆石子异或起来不等于 0”的必胜局面。 证毕。 公平组合游戏 ICG note若一个游戏满足： 由两名玩家交替行动。 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。 不能行动的玩家判负。 则称该游戏为一个公平组合游戏。 NIM 博弈属于公平组合游戏，但常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。 有向图游戏 note给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这张棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面沿合法行动能够到达的下一个局面连有向边。 Mex 运算 note设 SSS 表示一个非负整数集合。定义 mex(S)\text{mex}(S)mex(S) 为求出不属于集合 SSS 的最小非负整数的运算，即： mex(S)=minx∈N,x∉S{x}\text{mex}(S) = \min_{x \in \mathbb{N}, x \notin S} \{x\}mex(S)=minx∈N,x∈/S{x} SG 函数 note在有向图游戏中，对于每个节点 xxx，设从 xxx 出发共有 kkk 条有向边，分别到达节点 y1,y2,…,yky_1, y_2, \dots, y_ky1,y2,…,yk，定义 SG(x)\text{SG}(x)SG(x) 为 xxx 的后继节点 y1,y2,…,yky_1, y_2, \dots, y_ky1,y2,…,yk 的 SG 函数值构成的集合再执行 mex\text{mex}mex 运算的结果，即： SG(x)=mex({SG(y1),SG(y2),…,SG(yk)})\text{SG}(x) = \text{mex}(\{\text{SG}(y_1), \text{SG}(y_2), \dots, \text{SG}(y_k)\})SG(x)=mex({SG(y1),SG(y2),…,SG(yk)})特别地，整个有向图游戏 GGG 的 SG 函数值被定义为有向图游戏起点 sss 的 SG 函数值，即 SG(G)=SG(s)\text{SG}(G) = \text{SG}(s)SG(G)=SG(s)。 定理 important 有向图游戏的某个局面必胜，当且仅当该局面对应节点的 SG 函数值大于 0。 有向图游戏的某个局面必败，当且仅当该局面对应节点的 SG 函数值等于 0。 我们不再详细证明该定理。读者可以这样理解： 在一个没有出边的节点上，棋子不能移动，它的 SG 值为 0，对应必败局面。 若一个节点的某个后继节点 SG 值为 0，在 mex 运算后，该节点的 SG 值大于 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。 若一个节点的后继节点 SG 值均不为 0，在 mex 运算后，该节点的 SG 值为 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。 有向图游戏的和 note设 G1,G2,…,GmG_1, G_2, \dots, G_mG1,G2,…,Gm 是 mmm 个有向图游戏。定义有向图游戏 GGG，它的行动规则是任选某个有向图游戏 GiG_iGi，并在 GiG_iGi 上行动一步。GGG 被称为有向图游戏 G1,G2,…,GmG_1, G_2, \dots, G_mG1,G2,…,Gm 的和。 有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即： SG(G)=SG(G1) xor SG(G2) xor … xor SG(Gm)\text{SG}(G) = \text{SG}(G_1) \text{ xor } \text{SG}(G_2) \text{ xor } \dots \text{ xor } \text{SG}(G_m)SG(G)=SG(G1) xor SG(G2) xor … xor SG(Gm) 对于若干个有向图游戏的和，其证明方法与 NIM 博弈类似。