转载自我的文章，这里是pdf版。
我们夏令营要每人讲一个知识点，然后就有了这篇文章。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0. 前置知识
纳什均衡（Nash equilibrium）：任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自身的收益。
帕累托最优（Pareto Optimality）：是指资源分配的一种理想状态，假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。
本次题目网址，密码 114514。
1. 博弈论
在生活中，我们常见几种游戏：
* 31 点（每个人说一个 1∼m1\sim m1∼m 之间的数字，数字和率先达到 313131 的玩家获胜）
* 取石子游戏（几堆数量 ≥1\geq1≥1 的石子，每个人轮流取 1∼m1\sim m1∼m 个，率先取完的人获胜）
这几种游戏属于博弈游戏，属于博弈论（Game Theory），是经济学的一个分支。它主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。通俗地，它所研究的是在一个游戏中，进行游戏的多位玩家的策略。
上面列举的几个例子属于公平组合游戏（Impartial Game），一般具有以下特点：
* 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息。
* 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
* 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
当然还存在非公平组合游戏（Partizan Game），即游戏者在某一确定状态可以做出的决策集合与游戏者有关，信息不对等。大部分的棋类都属于非公平组合游戏，如五子棋、象棋、围棋等，以及一些卡牌游戏。
和公平组合游戏相反的，还有反常游戏（Misère Game），其获胜规则与公平组合游戏相反。如 Nim 游戏中取走最后一颗石子的为胜者，而反常 Nim 游戏中取走最后一刻石子的为败者。
本节讲述生活中最常见的博弈类型。当你没写作业的时候，你需要与老师对赌，猜老师会不会仔细检查你的作业；我们常用的最古老的游戏石头剪刀布也是一种博弈。但现在我们考虑一种比较困难的情况：囚徒困境博弈（Prisoner's Dilemma）。
现在有两个小偷 A 和 B 联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果两个犯罪嫌疑人都坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪，各被判刑 888 年；如果只有一个犯罪嫌疑人坦白，另一个人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑 222 年，而坦白者有功被减刑 888 年，即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱 111 年。
画表：
决策 A 坦白 A 抵赖 B 坦白 (8,8)(8,8)(8,8) (10,0)(10,0)(10,0) B 抵赖 (0,10)(0,10)(0,10) (1,1)(1,1)(1,1)
从数学角度分析：
1. 对 A 来说，尽管他不知道 B 作何选择，但他知道无论 B 选择什么，他选择“坦白”总是最优的。显然，根据对称性，B 也会选择“坦白”，这是纳什均衡。结果是两人都被判刑 888 年。
2. 但是，倘若他们都选择“抵赖”，每人只被判刑 111 年。在四种行动选择组合中，【抵赖，抵赖】是较优的，属于帕累托最优，因为偏离这个行动选择组合的任何其他行动选择组合都至少会使一个人的境况变差。
3. 但是，“坦白”是任一犯罪嫌疑人的占优战略，而 【坦白，坦白】是一个占优战略均衡。不难看出，此处与纳什均衡存在冲突。
然而人的行为活动错综复杂，所以囚徒困境只能作为简化模型参考，具体决策还得具体分析。
2. 巴什博弈
巴什博弈（Bash Game）是一个经典的博弈模型，其基本问题为：有一堆总数为 nnn 的物品，222 名玩家轮流从中拿取物品。每次至少拿 111 件，至多拿 mmm 件，不能不拿，最终将物品拿完者获胜。
引入策梅洛定理（Zermelo’s Theorem）：二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。由此可得巴什博弈属于一种公平组合游戏。
巴什博弈的必胜策略：在先取完者胜的巴什博弈中，若 nnn 可被 m+1m+1m+1 整除，则后手方必胜，否则先手方必胜。
证：可以采用 DP 思想，以数学归纳法证明。
首先考虑两种简单情形，我们称某一 nnn 的值是先手方或后手方的制胜位置，是指此 nnn 值下先手方或后手方有必胜策略：
* 我们先考虑 n<m+1n<m+1n<m+1 的简单情形。此时先手方行动，由于物品数量 <m+1<m+1<m+1，故至多为 mmm 件物品，先手方一次性拿完所有物品即可胜利。即 n=1,2,…,mn = 1,2,\ldots,mn=1,2,…,m 是先手方的制胜位置。
* 我们再考虑 n=m+1n=m+1n=m+1 的简单情形。此时先手方行动，他只能拿取 111 至 mmm 件物品，这意味着他无法一次将物品拿完，只能给后手方留下 111 至 mmm 件物品，而这一数量的物品恰好可被后手方一次性拿完。故后手方胜利。即 n=m+1n=m+1n=m+1 是后手方的制胜位置。
下面我们考虑所有的 nnn，设 n=k×(m+1)+rn=k\times(m + 1)+rn=k×(m+1)+r，其中 0≤r<m+10\le r<m+10≤r<m+1。由带余数除法可知，满足上面条件的整数 kkk 与 rrr 是唯一的。仍分为两种情形讨论：
* r=0r=0r=0，此时 n=k×(m+1)n=k\times(m+1)n=k×(m+1)。不妨设先手方取出了 xxx 个物品，后手方只需要取出 m+1−xm+1-xm+1−x 个物品，使得 n=(k−1)×(m+1)n=(k-1)\times(m+1)n=(k−1)×(m+1)，故使得 nnn 仍然整除 m+1m+1m+1 且后手方仍是后手方。如此操作下去，直到 n=m+1n=m+1n=m+1 的简单情形。这就说明了 nnn 可被 m+1m+1m+1 整除时是后手方的制胜位置。
* r≠0r\not=0r=0，此时 0<r<m+10<r<m+10<r<m+1。故此时先手方可以取走 rrr 件物品，使得 nnn 可被 m+1m+1m+1 整除，且自身处于后手方位置，再由上面的讨论可知有必胜策略。这就说明了 nnn 不可被 m+1m+1m+1 整除时是先手方的制胜位置。
整理得证。
另外，当先手有必胜策略时，第一轮拿取的石子数一定，为 n mod (m+1)n\bmod (m+1)nmod(m+1)。接下来两名玩家每轮拿取的石子数量之和为 m+1m+1m+1。请自行证明。
3. NIM 博弈
Nim 博弈（Nim Game）是一种经典的博弈游戏，其基本形式如下：地上有 nnn 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。
根据策梅洛定理，这是一个公平组合游戏，因此存在必胜方和必败方。先引出其获胜条件：当 nnn 堆石子的数量异或结果为 000 时，后手必胜；否则先手必胜。
证：我们把每一轮博弈视作树上的一个节点，形成一棵博弈树（Game Tree）。每个节点的后继表示该节点的递归方式。例如：
易见 000 可以向 111 和 222 转移。现在考虑什么时候 000 这个状态是必胜的？
注意，必胜是对于当前这个状态是必胜的，与是谁无关，赢的人只是处于一个胜的状态而已。
现在看实际问题：我们要得到 000 这个数，那么当你取完时还剩 000 个，你就显然是胜的。然后再通过最后的这个显然的必胜状态，往前递推找出其余的必胜状态。显然博弈论是必然会出现循环节的，因为它是一种不断递归求解的过程，每次都可以取到当前这个循环节上的必胜状态，并且让你的对手能达到的下个状态全部都是必败状态，那样就稳了。
考虑子问题，当 n=1n=1n=1 的时候显然是先手必胜，因为直接全部取掉就好，可以理解成 a1⊕0{a_1} \oplus 0a1 ⊕0；当 n=2n=2n=2 的情况就考虑一堆的石头和另一堆相不相等，可以理解为 a1⊕a2a_1\oplus a_2a1 ⊕a2 。显然，最后结果若是 000，则后手必胜，否则前手必胜。
现在扩展到 nnn，最终获胜式子为 0⊕0⊕0⊕0=00\oplus0\oplus0\oplus0=00⊕0⊕0⊕0=0，其最初状态为 a1⊕a2⊕a3⊕a4=sa_1 \oplus a_2 \oplus a_3 \oplus a_4=sa1 ⊕a2 ⊕a3 ⊕a4 =s（sss 为任意正整数）。由于一个数异或上它自己，答案肯定是 000。尝试转移为：s⊕a1⊕a2⊕a3⊕a4=0s\oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4=0s⊕a1 ⊕a2 ⊕a3 ⊕a4 =0。设 sss 的最高位为 sks_ksk ，如果 sks_ksk 的位数要高于 sss
那么它前面高出的那几位是不会变的，在第 kkk 位上，sk⊕ss_k\oplus ssk ⊕s 得到的答案应该是 000；又因为 sks_ksk 的前几位不变，第 kkk 位从 111 变成了 000 ，所以它是变小了的，这满足了每次从一堆数中取出部分(将原数减小)的要求。也满足了将任意 a1⊕a2⊕a3⊕a4=sa_1 \oplus a_2 \oplus a_3 \oplus a_4=sa1 ⊕a2 ⊕a3 ⊕a4 =s 转移成 a1⊕a2⊕a3⊕a4=0a_1 \oplus a_2 \oplus a_3 \oplus a_4=0a1 ⊕a2 ⊕a3 ⊕a4 =0 。
如何，你不断的将异或和变成 000 ，别人只能被动的把异或和变成 sss ，又因为最后获胜的时异或和要为 000 ，所以不断取 000 的时必胜的。
整理得证。
4. 推荐题目
CodeForces 533C：Board Game
题目大意：A 和 B 各执一枚棋子，位置分别是 (xa,ya)(x_a,y_a)(xa ,ya ) 和 (xb,yb)(x_b,y_b)(xb ,yb )。A 可以向左向上走，B 可以向左向上向左上走，位置不能重叠，每次可以选择走或不走，先到 (0,0)(0,0)(0,0) 的获胜。
题解：热身题，没有涉及任何博弈论知识，纯手推。A 可以往左或下走，而 B 能往左，下或左下走。可以分类讨论：
1. A 的 xxx 和 yyy 加起来没有 B 的 xxx 大，A 赢。
2. A 的 xxx 和 yyy 加起来没有 B 的 yyy 大，A 赢。
3. A 的 xxx 和 yyy 没有对手的 xxx 和 yyy 大，A 赢。
4. 其余 B 赢。
HDU 1846：Brave Game
题目大意：两个人轮流取 1∼m1\sim m1∼m 颗石子，先取完 nnn 颗石子的人获胜。
题解：巴什博弈板子题，不多说。上代码：
HDU 4764：Stone
题目大意：两人在白板上写数字，若一个人写了数字 xxx，则第二个人写的数字 yyy 要满足 1≤y – x≤k1 \le y\ –\ x \le k1≤y – x≤k，且第一次写的数字要满足在 [1,k][1,k][1,k] 内，先写到数字 NNN 的人输。
题解：转换一下，有 NNN 个石子，每次只能取 1∼k1\sim k1∼k 个，先取完的输。这和巴什博弈不同，是一种变形，称为反常游戏（Misère Game），这么考虑：假设我们有 n−1n-1n−1 个石子，如果后手能取完 n−1n-1n−1 个石子，那么下一个人必须取走最后一个石子，所以后手必胜，所以取走 nnn 个石子，取完胜的后手必胜条件等价于取走 n−1n-1n−1 个石子，取完输的后手必胜条件 (n−1) mod (m+1)=0(n-1)\bmod(m+1)=0(n−1)mod(m+1)=0 则后手必胜。
POJ 2368：Buttons
题目大意：给定一堆石头共 kkk 个，每人轮流拿 1∼L1\sim L1∼L 个石头，求出最小的 LLL 使后者存在必胜策略。
题解：典型的巴什博弈。首先想让后手胜，就必须把 L+1L+1L+1 的局面留给先手。这题没问我们谁会赢，问的是后手要赢的最小 LLL 值为多少。那我们就找到能被 kkk 整除的最小大于 222 的因数，之后减 111 就是答案了。
洛谷 P2197：Nim 游戏
题目大意：地上有 nnn 堆石子（每堆石子数量小于 10410^4104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，他想知道是否存在先手必胜的策略。
题解：Nim 博弈板子题，不多说。上代码：
POJ 2975：Nim
题目大意：给定 nnn 堆石子，分别有 a1,a2,a…,ana_1,a_2,a_{\ldots},a_na1 ,a2 ,a… ,an 个，问有多少种方法使得第一次操作是必胜决策。
题解：求出异或值 x=a1⊕a2⊕…⊕anx=a_1\oplus a_2\oplus \ldots \oplus a_nx=a1 ⊕a2 ⊕…⊕an ，因而有 x⊕a1⊕a2⊕…⊕an=0x\oplus a_1\oplus a_2\oplus \ldots \oplus a_n=0x⊕a1 ⊕a2 ⊕…⊕an =0，依次组合 xxx 和每个 aia_iai 。然而对于 aia_iai ，取之后必然越来越小，所以要 ai⊕x<aia_i\oplus x<a_iai ⊕x<ai 即可将 aia_iai 变成 ai⊕xa_i\oplus xai ⊕x，拿去
ai−(ai⊕x)a_i−(a_i\oplus x)ai −(ai ⊕x) 个棋子。
统计满足 ai⊕x<aia_i\oplus x<a_iai ⊕x<ai 的个数即可。
CodeForces 731E：Funny Game
题目大意：一个长度为 NNN 的序列 aia_iai ，双方轮流操作。每次的操作是选择一个长度大于 111 的前缀，计算它的和 sss ，然后用 sss 替换它的前缀，同时当前玩家获得 sss 的分数。当只剩下一个元素时，游戏结束。双方均想最大化自己的分数-对手的分数，计算这个值。
题解：我们不关心谁是先手谁是后手，只关注分差。令 dpidp_idpi 表示从后往前第 iii 位的最大得分差，则有：
dpi=maxj∈[i+1,n]{prej−dpj}dp_i=\max_{j\in[i+1,n]}\{pre_j-dp_j\} dpi =j∈[i+1,n]max {prej −dpj }
计算前缀和，dpdpdp 序列转移即可。
5. 应试技巧
对于博弈问题，常见几个字眼：
* 石子游戏
* 取数游戏
* Alice 和 Bob
博弈论常与以下知识点联考：
* 动态规划 DP
* 贪心
