组合博弈

引言

组合博弈如今是信息学竞赛中十分重要的组成部分，因为一方面其天然与动态规划等算法思想契合，有着各种优美的性质；另一方面其形式多变，主要偏重于对思维的考察，对代码能力的要求相对较低，所以适合出成竞赛题。本文中，我们从组合博弈的原始形态：NIM博弈谈起，再谈到更一般的无向图上的组合博弈，并给出这类问题的一个通解。接下来我们引入NIM游戏和，NIM游戏积的概念，得到了单个游戏的组合情形，并利用SG定理给出相应的解法。最后，我们引入SG的一些变形形式，并分别对其提供解答。

本文写作的初衷，是想将所有信息学竞赛相关的组合博弈知识融汇贯通，为ACM选手及OI选手提供一些有价值的信息。

定义

我们先给出在组合博弈概念中所有出现的名词：

玩家：即组合博弈的参与者，用大写字母 $，$ 表示。
局面：游戏中某一时刻的状态，比如在围棋游戏中，某一时刻棋盘的状态就是一个局面，可以用一个的矩阵来记录这个局面。我们记局面为小写字母。所有可能发生的局面构成的集合，称为一个局面集合，用大写字母表示，且。
操作：对一个局面进行操作可以得到另一个局面，如果一个局面在一步操作之后可以得到局面，我们可以记操作为。
局面的后继：对于任意一个局面，如果可以通过操作得到局面 , 则称是通过操作得到的后继局面。特别地，对于局面，如果可以通过操作集合得到后继状态，则后继状态集合可以被表示为。
策略：由一个或多个玩家及其对应的有序的操作序列构成

接下来我们给出组合博弈的一般定义：

由两名玩家：左玩家和右玩家参与，后文中常用先手表示左玩家，后手表示右玩家
游戏的局面集合是有限的，即
游戏双方轮流操作
游戏是公平的，在任一状态，双方操作得到的后继状态集合一致，即
游戏是透明的，在任一时刻，双方都知道对方的之前的操作序列
游戏是有边界的，即有些状态没有后继状态
游戏是有穷的，即一定保证游戏在有限步内结束
游戏是确定的，对于玩家在某一局面的某一操作，只会产生唯一的后继局面

事实上，如果将所有状态及其后继状态之间连一条有向边，我们将得到一个DAG。对于任何一个组合游戏，我们都可以理解为一个有向图游戏，初始时刻有一个棋子在某一节点（局面）上，双方（玩家）轮流沿着有向边移动棋子（操作），最先满足某种条件的玩家获得胜利。棋子移动的路径及每轮的移动者构成一个策略。

我们要解决的一般有两种问题

胜负性检验
必胜后继状态求解

第一个实例：Bash Game

题目描述

有一堆石子，两人轮流从中取石子，每次可以取个或个或个石子，问先手是否有必胜策略。如果有，输出先手第一步应该取几个；如果没有，输出0。

题目分析

在这个问题中，一个局面可以可以用一个整数表示，即这堆石子还剩多少个。在给定初始局面的情况下，其所有直接或间接后继局面构成的集合显然是有限的，即满足有限性；每次取石子后，总数都会变少，所以游戏是有穷的，不会形成回路；组合博弈其他的性质也都满足，所以我们认为这是一个组合博弈问题。

事实上，如果用有向图来表示这个游戏，就是一个链上添加若干的边，即一个有向图。

题目解法

这是一道小学奥数题，观察打表可以发现，当先手必败，否则先手必胜（胜负性检验）。先手只要取个石子即可保证自己必胜（必胜后继状态求解）。

基本解法

上文中我们通过观察得到了问题的解，事实上，观察/打表是组合博弈的一种通用解法，打表可以快速得到问题的特征，从而推断出解法，再用数学归纳法等方法证明解法的正确性。所以我们先研究这类问题的一个通用解法，保证对于任何一个组合博弈问题，在不考虑复杂度的情况下，问题总是可解的。

必胜态，必败态

回到上文的 Bash Game，不难发现，如果先手想要获胜，就得将后手的局面变成，这样不管后手如何操作，都会得到，先手可以不停重复上述循环直到。而如果先手一开始就是，则其无论如何操作，后手都可以用类似的方法制裁他。看上去是问题的一个关键点，谁将对手逼到上，谁就能获得胜利。

在这里，我们可以认为为一个必败态，而其他所有状态都是必胜态。我们将从中导出组合博弈问题的一般形式——NP局势。

NP局势

首先给出必败态的定义，一个局面局势当且仅当其满足以下两条之一：

，即即没有后继状态

且有必胜态定义，一个局面局势当且仅当：

换言之，必胜态一定有一个后继局面是必败态；必败态的所有后继局面都是必胜态（或者不存在）。一个推论是，在组合博弈对偶的有向图中，如果从所有的汇点（必败态）开始做拓扑排序，可以将图中每一个节点都染成必胜态或者必败态，由定义可知成立。并且在同一状态为先后手的局面恰好状态相反，这也是显然的，因为一个获胜另一个必然失败。

回到 Bash Game，是一个必败态，从而 $，，$ 可以抵达，为必胜态；只能达到 $，，$ ，无论怎么做都是让对手获胜，所以为必败态，以此类推可以得到所有局面的NP状态。

动态规划/拓扑排序

现在我们可以尝试用通法解决 Bash Game 了。

首先我们找出所有的局势 $，，，，$ ，画成点；
然后找出所有的操作；
建立DAG；
找到边界局面；
做拓扑排序，计算NP状态。

接下来对于每一个状态，我们直接输出其NP状态即可，复杂度为。拓扑排序实质上是一种动态规化的思想，所以动态规划的相关算法也可以用上，比如记忆化搜索，矩阵加速，四边形不等式等等。在一些查询稀疏的问题上，使用记忆化搜索有时会有更好的效果。

当然，这种解法的复杂度实在太高，虽然有着很强的通用性，但是时空复杂度消耗太大，完全没有用上问题本身可以用来优化的性质。所以在实际应用中，这种解法常常用来打小规模的表用于找规律。接下来我们将介绍一些可以用于优化的性质。

此外，在只需要计算胜负态的游戏中，在dp求解时，只需要在所有必败态上去更新必胜态，如果必败态稀疏时，复杂度将会很低(只需要访问少数的转移边)，需要注意这一点。

NIM和——SG函数

在 Bash Game 中，我们只处理一堆石子，如果有多堆石子呢？

第二个实例：nim游戏

题目描述

有堆石子，第堆石子有颗，每次可以从其中任意一堆中取不少于颗石子，取走最后一颗石子的玩家获胜，问先手是否有必胜策略。如果有，输出先手第一步应该取几个；如果没有，输出0。

题目分析

沿袭朴素解法的思路，建立大小为的状态空间，建边，建DAG，拓扑排序求解，复杂度指数级开外，不可做。

但是可以发现，每个石子堆都是独立的，即这个 Nim Game 其实是多个独立游戏的和，且每次操作只能改变其中一个游戏的局面。这时，我们引入SG定理来解决这类游戏和的问题。

题目解法

令，即将所有异或起来，如果结果为则必败，反之必胜。先手必胜策略为，取某堆中的若干石子使得余下的石子异或和为，可以证明必定有解。

SG定理

关于SG产生的心路历程，可参阅 SG函数是怎么想出来的，在这里只给出定理内容。

定义为局面上的一个函数，且

其中表示集合中最小的没有出现过的正整数，如。

对于任意状态，当时有，反之为。

则对于游戏和游戏的和，有：

$SG(x+y)=SG(x)\oplus SG(y)$

分析上面的 Nim Game，对于每一堆石子，根据SG函数定义，恰好成立，所以答案就是他们颗数的异或和。

相关的一些推导可以参考博弈论 | 详解搞定组合博弈问题的SG函数，本文中不再赘述。

SG函数求解

多个游戏加在一起不好算，单个问题还不好算么，继续拿出拓扑排序的算法：

首先我们找出单个游戏中所有的局势 $，，，，$ ，画成点；
然后找出所有相应的操作；
建立DAG；
找到边界局面；
做拓扑排序，维护数组，求解各点SG值。

在这里有一些常用的小技巧，比如 mex 数组范围可以设置为有向图中最长链的长度；在线性问题上递推求解时，为了避免初始化mex数组带来的时间损耗，可以填写mex时将填入值设置为当前节点的编号，免去memset苦恼，如

int mex[maxn];
for(int i=0;i<n;++i){
	for(int j=0;j<g[i].size();++j){
		/*这里替换为你的 mex 计算算法*/
		mex[g[i][j]]=i;
	}
	for(sg[i]=0;sg[i]==i;++sg[i]);
}

NIM游戏与游戏和

当我们考虑游戏的“和”时，我们就会用到SG函数的概念。事实上，对于一个局面，如果有，我们可以等价的认为这个局面是 NIM Game 中一堆数量为的石子，这样就建立起SG函数与 NIM Game 之间的等价性。对于所有的和游戏，我们都可以计算出每个局面的 SG 值，然后将其规约为普通的 NIM Game 进行处理。

在建立这个等价关系的时候需要注意一点，在 NIM Game 中，的子游戏有且仅有空石子堆，且没有后继状态；而在更普遍的和游戏中，这样的可能只是一个必败的中间局面，且其所有后继局面都是的必败态。SG函数可以认为是NP状态的一种拓展，对于每个必胜态继续细分其特征，从而实现游戏和的快速求解。

NIM积——高维NIM游戏

第三个实例：Switch lights

题目描述

在一个二维网格，每个格子上有一个灯泡，有若干个灯泡亮着，每次玩家可以选择其中一个位于的亮着的灯泡，并且选择一个满足，翻转位于位置上的灯泡。关掉最后一盏灯者获胜，问先手是否有必胜策略。

题目分析

如果是一维的，那么这就是一个nim游戏，那么几个灯泡放一块本质上就是一个nim和，把每个灯泡的sg值求出来异或即可。

现在问题在于，每个灯泡怎么求。

题目解决

NIM提供了一个解决方案,对于坐标，算法如下:

/* TEMPLATE BEGINS HERE*/

int n,sg[2][2]={0,0,0,1};   
//definition

int mulp(int x,int y){      
//calc nim production of x and y as power of 2
    if(x<2)return sg[x][y];

    int m;
    for(m=2;m*m<=x;m*=m);
    int p=x/m,s=y/m,t=y%m;
    int d1=mulp(p,s);
    int d2=mulp(p,t);
    return (m*(d1^d2))^mulp(m/2,d1);
}

int mul(int x,int y){       
//calc nim production of x and y
    if(x<y)swap(x,y);
    if(x<2)return sg[x][y];

    int m;
    for(m=2;m*m<=x;m*=m);
    int p=x/m,q=x%m,s=y/m,t=y%m;
    int c1=mul(p,s);
    int c2=mul(p,t)^mul(q,s);
    int c3=mul(q,t);
    return (m*(c1^c2))^c3^mulp(m/2,c1);
}

/* Call this function DIRECTLY for usage */
/* May exploit DP(Memory search) for acceleration*/

int solve(int x,int y){
    return mul(x,y);
}

/* TEMPLATE ENDS HERE*/

高维NIM积

NIM积给出一个在高维情形下的求解方式，对于一个任意维度的矩形，坐标的上的点如果可以取一个各个坐标都小于他的点，并且这两点生成的高维矩阵的顶点都进行一次switch。那么可以使用NIM积求解。

上面给出了二元nim积，对于更高维度的情形，只要重复调用，全部累计在一起即可。

推导过程参见 NIM积解法小结，算法出自《从“k倍动态减法游戏”出发探究一类组合游戏问题》。

SG的变体形式

ANTI-SG(SJ)

ANTI-NIM 指取走最后一个石子的人落败的 NIM 游戏。给出 ANTI-NIM 更一般的定义：

操作集合为空的玩家获胜
其余规则与SG游戏一致

则有 SJ 定理（出自《组合游戏略述——浅谈SG游戏的若干拓展及变形》，这篇论文介绍了很多组合博弈的模型，可以参考博弈:关于SG函数的一些心得的总结，下一节 MULTI-SG 也出自这篇论文），对于任意一个Anti-SG游戏，如果定义所有子游戏的SG值为0时游戏结束，先手必胜的条件：

游戏的SG值为0且所有子游戏SG值均不超过1
游戏的SG值不为0且至少一个子游戏SG值超过1

该定理只在所有的必败态局面都没有后继局面存在时成立，所以当该问题从 NIM 外推到更一般的 ANTI-游戏和问题时，需要判断所有必败态是否都没有后继局面，若不满足则该定理不保证正确。

在解决该类问题时，仍然按照经典的 SG 函数的方法计算 SG 函数，如果存在某个子游戏 SG 值大于1，则该问题与一般的游戏和问题结果一致（局面SG值够大时先手选择余地更多，直觉上总能找到更多好的解）；如果所有SG值均小于等于1，则该游戏胜负则倒置（局面SG值都很小时，选择余地有限，和的局面的奇偶数强相关，也因此如果如果存在一个很大SG很大的后继局面，则问题将会复杂到难以快速求解）。

但是反过来，如果不使用SJ定理（即不满足无后继条件且局面集合够小时），则设置所有没有后继局面的的局面为必胜态，即满足，在此基础上进行拓扑排序。需要注意的是，这种情况下也能求一个类似 SG 值的数值，但是因为定义发生了变化，所以这个类 SG 值不能用于游戏和的快速求解，因此没有必要求这个值，直接推断 NP 状态即可。

MULTI-SG

MULTI-SG也是一种游戏和模型，一个子游戏在一次操作后可能出现多个后继子游戏。给出 MULTI-NIM 游戏更一般的定义：

一个子游戏在一次操作后可能出现多个后继子游戏
其余规则与SG游戏一致

事实上，根据 SG 定理，我们只要把局面中某个子游戏的某次操作后产生几个子游戏对应的局面的 SG 值异或起来，将他们的游戏和看成一个后继局面，则该问题就变成了一般的 SG 游戏和问题。即若有局面及其后继局面集合 $F(g)=\{g'_1,g'_2,\cdots,g'_n,u'_1,u'_2,\cdots,u'_m\}$
其中表示分成的若干个子游戏。定义，则有 MULTI-SG 下的 SG 值计算式：

$SG(g)=mex(\{SG(x)|x\in F(g)\})$

如此 MULTI-SG 也可也视为一般的 SG 问题求解，从而规约到 NIM Game 上。

如果是 MULTI-ANTI-NIM 问题，只要先用 MULTI-SG 计算每个局面的 SG 值，再使用 SJ 定理给出答案即可。

异常边界：一个子游戏获胜就获胜

在一些问题中，可能会有一些SG的变形形式，改变游戏的终止条件(ANTI-NIM也可也视为一种异常边界的情形)。这时我们要手动对边界进行调整，直到所有的边界状态都成为必败态，这样就可以直接使用 SG 定理求解。

以题目 Cutting Game 为例：给一个的方格纸，两人轮流沿着坐标轴和网格线切，每次切成两块(类似于MULTI-NIM)，最先切出的小方格的玩家获胜。

因为边界条件发生变化，难以直接求解每个子局面的 SG 值，所以考虑修改边界。因为只要出现一个就立刻获胜，意味着一定是一个必败态，取，在此基础上递推计算 SG 值即可。

一些常见的非典型单游戏组合博弈形式举例

阶梯博弈

阶梯博弈指，有一个台阶，每个台阶上有一些石子，每次可以将任意个石子从任意台阶上往下挪一格，如Georgia and Bob，没有操作可行者判负。假设最低一层是第1层，则该问题等价于每堆奇数阶上的石子的游戏和，即一个所有奇数阶石子构成的 NIM Game。证明可以参考我谈阶梯博弈，此处不多做展开。

威佐夫博弈

Wythoff Game 指有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

看上去像一个游戏和模型，但是事实上因为可以同时从两堆中取，破坏了子游戏的独立性，所以不能使用游戏和的模型求解。在这里我们考虑 Betty 数列的模型，构造奇异局势，来实现告诉判定，具体细节可以参阅博弈论——两人取子游戏与威佐夫博弈，隐藏在背后的黄金分割。

结语

本文列举了组合博弈中一些常见的模型，以及其对应的解法，限于篇幅限制，不能全部展示，读者可以自行阅读从“k倍动态减法游戏”出发探究一类组合游戏问题，组合游戏略述——浅谈SG游戏的若干拓展及变形等论文自行了解。此外，出于光学不练假把式的思想，笔者归纳了一套题库，并分别打上了 TAG，其解法在本文中大多有题及，读者可以自行查阅。

习题

引用

SG函数是怎么想出来的
 博弈:关于SG函数的一些心得
 NIM积解法小结
 我谈阶梯博弈