博弈论

发表于 更新于 分类于

Bash游戏

\(A\)和\(B\),有\(n\)颗石子,每次可以取\(x\)颗,其中\(1\leq x\leq m\\\),求\(A\)是否能赢.

考虑直接令石子数量为状态,有\(SG(x)=mex\{SG(y)|\max\{0,x-m\}\leq y\leq x-1\}\\\),注意到\(SG(x)=0\)当且仅当\(x\equiv 0(\mod m+1)\).

我们使用数学归纳证明:

当\(0\leq x\leq m\)时,显然成立.

而对于\(x\),如果\(x\equiv 0(\mod m+1)\\\),那么集合\(S=\{y\in \mathbb{Z}|\max\{0,x-m\}\leq y\leq x-1\}\)中一定\(\nexists y\)满足\(y\equiv0(\mod m+1)\\\).

也就是\(\nexists y\)满足\(SG(y)=0\),那么\(SG(n)=0\).反之,一定存在.

Nim游戏

\(A\)和\(B\),有\(n\)堆石子,第\(i\)堆石子有\(x_i\)个石子.每次可以任选一堆取走若干个石子,最后不能取的人输.求先手是否必胜.

注意到如果\(x\)均等于\(0\)一定先手必败.考虑令\(w=x_1\oplus x_2\oplus...\oplus x_n\)(\(w\)即为全游戏的\(SG\)值),那么先手必败当且仅当\(w=0\\\).

证明: 只需证明当\(w\ne 0\)时一定存在一种方法使得\(w=0\\\).

考虑\(w\)的最高位为第\(k\)位,那么一定存在一个\(x_i\)的第\(k\)位为\(1\).将它改为\(0\),然后这个\(x_i\)的后面几位可以随意更改.

Example1(Nimk游戏)

\(A\)和\(B\),有\(n\)堆石子,第\(i\)堆石子有\(x_i\)个石子.每次可以任选不超过\(k\)堆取走若干个石子,最后不能取的人输.

将\(x_i\)写成二进制,如果每一位的\(1\)的个数均是\(k+1\)的倍数,那么先手一定必败.道理是差不多的.

Example2(Multi-Nim游戏)

Nim游戏,但是玩家每回合可以将任意一堆石子数量大于等于\(2\)的石子堆分成任意两堆不为空的石子堆.没法操作的人输.

本质仍然是SG游戏,我们正常做就行.

\(SG(x)=mex\{\{SG(v)|x\rightarrow v\},\{SG(x-i)\oplus SG(i)|1\leq i<x\}\}\\\).

找一下规律可以发现: \[ SG(x)=\begin{cases} x-1&x\equiv 0(\mod 4)\\ x&x\equiv 1或2(\mod 4)\\ x+1&x\equiv 3(\mod 4)\\ \end{cases}\\ \] 不妨设当\(x\leq 4k\)时结论成立.

当\(x=4k+1\)时,前半部分一定是取遍了\([1,4k]\).

但是一定不存在\(a\)和\(b\)满足\(a+b=4k+1\)并且\(SG(a)\oplus SG(b)=4k+1\).讨论一下\(a\)和\(b\)在\(\mod 4\)意义下的值就会发现不可能.

其他的是同理的.

SG游戏

\(n\)个DAG,每个DAG只有一个起始点,起始点上有一枚棋子.\(A\)和\(B\)每次可以选一个图,将上面的棋子沿DAG移动一条边,不能移动的人输.

直接使用\(SG(u)=mex\{SG(v)|u\rightarrow v\}\).

那么先手必败当且仅当所有DAG初始节点的SG异或起来是\(0\).

首先如果\(SG(u)=x\),那么\(\forall 0\leq y<x\),\(\exists v\)使得\(u\rightarrow v\)且\(SG(v)=y\).可以发现这就如同Nim游戏了.

但是与Nim游戏不同的是,可能\(\exists y>x\),但是仍然可以转移到.

但在这种情况下,我可以继续转移到一个\(u'\)使得\(SG(u')=x\),因此异或值不变.

Example1(Anti-SG游戏)

SG游戏,但是不能取的人赢.

SJ定理:

先手必胜当且仅当下面两个条件满足一个:

  1. 游戏的SG函数不为\(0\)且游戏中某个单一游戏的SG函数大于\(1\).
  2. 游戏的SG函数为\(0\)且游戏中没有单一游戏的SG函数大于\(1\).

如果没有单一游戏的SG函数大于\(1\),那么显然游戏的SG函数为\(0\)就赢了,否则就输了.

而如果SG函数为\(0\)且存在某个单一游戏的SG函数大于\(1\),一定是输的.

因为这个情况下,后手先按照正常\(SG\)游戏压着先手,最后一定会剩两堆一样大于\(1\)的,无论你怎么选,对手都可以压着你.如果你把一堆全选了,此时对手就可以把另一堆剩下一个,这样就必输;如果你把这一堆选的只剩下一个,对手就可以把它那一堆全选了,这样就也是必输的.

Example2(Every-SG)

SG游戏,但是每次每个能移动的游戏都必须移动,不能移动任何游戏的人输.

对于每个子游戏,如果先手必胜,先手一定会尽可能多争取时间.

反之,先手一定会尽可能早结束游戏.

在\(DAG\)上dp的时候除了\(SG\)我们再加一维表示时间耗费,就可以dp了.

Example2.5(Every-SG)

n个游戏,每个游戏两堆石子,每次可以从大的那堆中取小的那堆石子大小的整数倍的石子.

直接套用Every-SG的做法就行.

Example3(Nim on tree)

一棵有根树两个人,每次可以挑一棵真子树删掉,不能操作者输.

结论:\(SG(u)=\bigoplus_{u\rightarrow v}(SG(v)+1)\).

考虑归纳假设.如果\(u\)只有\(v\)一个儿子.那么要么将\(v\)子树全删,要么删一部分,有: \[ SG(u)=mex(x|x=0\or 0\leq x-1< SG(v))=SG(v)+1 \] 而如果有多个儿子,则每个儿子都相当于是一个SG子游戏,异或起来即可.

另一种理解方式:考虑只有一个儿子的情况,那么相当于这个儿子的所有状态都向终止节点连了一条边,终止节点的\(SG\)为\(0\),而显然\(SG\)图中的其它节点的\(SG\)均要\(+1\).

Example4

\(n\)个有根仙人掌,保证所有的环与树的结构只有一个公共点(环只有一条连到环外的边).

两个人分别操作删边,与根不连通的边都被删掉.

结论:奇环\(SG=1\),偶环\(SG=0\).

这么考虑:边数为\(k\)的链的\(SG\)为\(k\).

而拆开奇环后,你得到的两条链奇偶性一定相同,因而不可能得到\(1\).偶环同理,不可能得到\(0\).

Example5

无向图,每次删掉一条边以及与根节点不连通的部分,无法操作者输.

考虑Example2.

Fusion定理:将偶环替换成一个新点,奇环替换成一个新点连出去一条边,做边双.对于一个边双,\(SG\)值只和他边的奇偶性有关.证明大概和上面一样.

斐波那契博弈

一个数\(N\),两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次的两倍.

不能操作者输.

结论为:当且仅当\(N\)是斐波那契数时,先手必败.

考虑归纳证明:

先证明当\(N\)是斐波那契数时必败,不妨假设\(N=N_0+N_1\), 考虑将\(N\)看成两堆,因为如果第一次取走了大于\(N_1\)颗石子,由于\(N_0\leq N_1\\\),则后手第二步可以全取走,必败.

并且一开始先手一定要在\(N_0\)堆取石子,原因是如果取了大于\(N_0\)颗石子,由于\(N=N_0+N_1\leq 3N_0\\\).这样下一步后手就可以全取完.

那么现在先手应该开始取\(N_0\)这一堆,如果在这一堆取的过程中,先手一直取得不超过\(N_0\)剩下的数,那么根据归纳假设,后手一定可以取走\(N_0\)堆的最后一个石子,此时局面变成了只剩\(N_1\)颗石子.只要此时先手不能一次取走\(N_1\)颗石子,先手就必败.而后手最后一步拿走石子最多会拿走\(\frac 2 3N_0\)的石子,但是,\(\frac 4 3N_0<N_1\),因此一定不可能.

否则,仍然是先手取走了\(N_0\)全部石子,又当了先手取\(N_1\)的石子.仍然是必败的.

齐肯多夫定理:任意一个正整数都可以被表示成若干不连续的斐波那契数之和.

设\(N=\sum_{i=1}^k f_{p_i}\),其中\(p_1<p_2<p_3<...<p_k\\\),先手取走\(f_{p_1}\\\).由于\(2f_{p_1}<f_{p_2}\),因此后手接下来无论如何不可能取得大于等于\(f_{p_2}\\\),问题转化为一堆大小为\(f_{p_2}\)的石子,此时先手必败.因此原问题的先手必胜.

二分图博弈

给出一张二分图和起点\(S\),\(A\)和\(B\)轮流操作,每次操作只能选与上一个被选的点相邻的点,且不能选已经选过的点.

考虑二分图的所有最大匹配,如果在所有的最大匹配的方案中都包含了起点\(S\),那么先手必胜,否则先手必败.

证明:

如果所有匹配都包含\(S\),那么\(A\)只需要每次走到一个和\(S\)匹配的点即可.\(B\)无论如何不可能走到一个不在最大匹配中的点,不然,我们将路径全部取反,就得到了一个最大匹配不变但不包含\(S\)的点,与假设不符.

而如果存在一个匹配不包含\(S\),如果\(A\)仍然第一步走到一个和\(S\)匹配的点那么\(B\)一定能想办法走到一个不在当前\(A\)选择的最大匹配中的点而在一个不包含\(S\)的最大匹配中的点,于是\(B\)必胜.

Example1([2022qbxt国庆Day5]C)

显然,一个人敢抢金条当且仅当没有人敢抢他的金条.假设\(dp_{S,x}=0/1\)表示目前集合\(S\)中的所有人都已经离场了,而目前金条在\(x\)手中,金条会不会被抢.显然,如果\(\exists y\)满足\(dp_{S\cup\{x\},y}=0\),也就是金条在\(y\)手里不会被抢,那\(x\)手中的金条必定会被抢.

将这个抢的过程看作二分图博弈中走到相邻的点的过程,于是这个问题等价于二分图博弈.也就是说,如果二分图博弈先手必胜,那么第一个拿到金条的人一定会被抢.

因此,我们需要找到所有与\(S\)匹配的可能出现在最大匹配中的边,对应编号最小的那个点,金条最后一定在他手里.(第一步这么走后,一定能构造出)

这个怎么构造呢,我们考虑先跑一遍dinic求最大匹配,然后做一遍tarjan缩点,然后如果\(S\)和\(x\)并未匹配,那么我们判断二者是否在一个强连通分量中,如果在,那他们可以被匹配.

至于判断\(S\)是否一定在其中,只需要先删去\(S\),跑dinic,再在残联网络上加上\(S\),判断是否有新的增广路.

树上博弈

Example1(zr[23省选10连 day1] Clashmas)

注意到删点对树形态的影响,考虑重心

  1. \(n\)为奇数,重心为后手点.

注意到此时后手一定可以通过一些方式维持重心不变,因此后手必胜.

  1. \(n\)为奇数,重心为先手点.

我们不妨设先手是A,后手是B.

考虑一个事实:对于这样一棵树,我们删着删着一定会出现一个时刻使得此时\(n\)为偶数,有两个重心(比如最后只剩下两个点的时刻),根据(4)和(5)的讨论,此时胜负已分.而且不难注意到此时A变为了实际上的后手.

根据(5),如果B掌控了任意一个重心,那A就输了.因此A必定要使当前局面的两个中心均为A的点.考虑原重心的所有儿子,它们有的是A点,有的是B点.由于树的重心的性质,树的重心的移动一定是一点一点挪的,也就是说第一次出现上面的局面的时候,两个重心必有一个是原重心,另一个是原重心的儿子,接下来A和B就要对于另一个重心能取到哪个儿子做争夺.我们不妨设A的点的集合为\(S_A\),B的点的集合为\(S_B\).以原重心为根建树,设其所有儿子组成的集合为\(S_C\),不难发现A能胜利(也就是让两个重心全都属于他)当且仅当\(\sum_{u\in S_A\cap S_C}siz_u\geq\sum_{u\in S_B\cap S_C}siz_u\).

原因很简单:A和B必然每次都会去杀属于对方的子树中\(siz\)最大的那棵.由于A有着先手优势,因此只要满足上面的条件,A总能获胜.

  1. \(n\)为偶数,唯一重心,重心为后手点.

类似(2)的讨论,最后一定有某个时刻使得此时\(n\)为偶数,有两个重心(比如最后只剩下两个点的时刻),此时A仍然是先手,根据(5),只要他掌控一个重心就可以获胜.

类似地,不难发现胜利条件等价于(2).

  1. \(n\)为偶数,两个重心,重心均为后手点.

注意到此时整棵树分为两个大小相等的部分,因此后手一定可以维持这个场面不动,后手必胜.

  1. \(n\)为偶数,至少有一个重心是先手点.

注意到此时先手一定存在一种方式开局,使得重心仍为这个先手点,这样就转化为第一种情况,先手必胜.

散题

Problem1([CSP-S2020]贪吃蛇)

首先注意到,如果一个蛇吃完后还不是最小的蛇,那它一定会吃.因为被吃的蛇是单调不降的,而吃蛇的蛇是单调不增的,因此下一个蛇如果要吃,那一定会比它还小,所以至少会先被吃掉,而那条蛇会被吃掉,它就一定不会选,所以无论如何这条蛇都不会被吃掉.

我们考虑如果吃完后变成了最小的蛇后会怎么样,我们设\(f_i\)为还剩\(i\)条蛇的时候能不能吃,那\(f_i=1\)的话,要么\(i=2\),要么吃完后不是最小的,要么\(f_{i-1}=0\).

递归做就好了.另外这题需要复杂度\(O(n)\),需要用几个队列/双端队列维护.

Problem2([AGC023D]Go Home)

首先,最后一个人要么是最左边的,要么是最右边的.而显然这两边中人数较少的一个将会是最后一个到家的,那么这个人的目标就是帮助另一边的人尽可能快到家,于是会帮着它投票.以此类推不断递归下去.

Problem3(牛客38727E)

首先考虑如果有人作为第\(n-p+1\)个人复读了,那接下来复读一定不会被惩罚,于是没复读的都会复读,这样这个人就必死.于是最多只会复读\(n-p\)个人.

继续思考,如果有人作为第\(n-2p+1\)个人复读了会怎么样,后面的人也都不会被惩罚了,于是也会继续复读.

以此类推,会发现最后只会有\(n\mod p\)个人复读,并且一定是前\(n\mod p\)在一轮内复读完.

Problem4(arc155D)

考虑直接转移,但是有可能出现在原地转的情况,注意到这种情况我们只需要记录\(f_{i,j}\)表示当前的\(G\)是\(i\),\(G\)的倍数还剩下\(j\)个,然后做转移,再进一步发现我们只关心\(j\)的奇偶性.于是记\(f_{i,0/1}\)即可.

这题给我最大的启示是,我们不能假定让双方共同遵守一个”君子协定”,博弈论最重要的就是博弈,不能说我们最后再选倍数之类的,他的转移路线会变化的. ##### Problem5

给一个“日”字型图,七条边,每条边有一堆石子.每次可以选任意多条不构成环的边,然后将这些边上的石子堆取走任意多个石子.求先手必胜策略,以及如果每条边的石子数量在\([l_i,r_i]\),那么有多少种先手必胜的情况.

考虑将这个图分成三部分,上面三条边,中间一条边,下面三条边.那么这三部分一定不能全选至少两部分,不然会构成环.反之一定构不成环.

先手必败当且仅当,这三部分内部的边上石子均相等,并且所有边异或值为\(0\).

否则,考虑将上部分和下部分三条边先全改成相等的,会修改较大的两条边.

接下来,我们剩了三条边,我们只能选择改其中一条,使得他们仨异或值为\(0\).

换句话说,我们现在有\(x_1,x_2,x_3\),我们要将其中一个\(x_i\)改为\(y_i\),其他不变,使得他们仨异或值为\(0\).和Nim游戏类似,假设他们仨异或值的最高位为\(k\).那么一定有一个\(x_i\)的第\(k\)位为\(1\),将它改为\(0\),后面就可以随意变换.

思路具体怎么想到的呢,可以发现整个图只有三个环,并且这三个环都可以由这几部分组成.接下来就可以每个部分的\([l_i,r_i]\)求个交,用FWT做一遍异或卷积.数位dp也可以做.

Problem6

Nim游戏,但是每堆石子有一个\(K_i\).如果这堆石子剩\(x_i\)个每次最多取\(\lfloor\frac {x_i} {K_i}\rfloor\)个石子.求先手是否必胜.

结论是\(SG(n,k)=\begin{cases} SG(n-\lfloor\frac n k\rfloor,k)&n\ne 0(\mod k)\\ \frac n k&n=0(\mod k)\\ \end{cases}\\\)

考虑数学归纳就可以证明.

然后我们就只需要对于\(k\)是否大于\(\sqrt n\)讨论一下,如果\(k<\sqrt n\)暴力,最多只会做\(\sqrt n\)次.否则,意识到此时可以通过求一个区间\([l,r]\),满足\(\forall x\in [l,r],\lfloor\frac x k\rfloor\)均相等,加速一下.这种区间最多只会有\(\sqrt n\)个.

Problem7

一个数\(N\),两个人轮流令他减去一个数,第一次不能减完,每次减的不能超过上一次.不能操作者输.

先手必败当且仅当\(N=2^k\),不然,每次选lowbit即可.

Problem8

A和B,有\(n\)颗石子,每次可以取\(x\)颗,其中\(1\leq x\leq \lceil\frac n 2\rceil\\\).

仍然令石子数量为状态,注意到\(SG(x)=0\)当且仅当\(x+1=2^k-1\),也即\(x=2^k-2\\\).首先,注意到: \[ n-\lceil\frac n 2\rceil=\lfloor\frac{n}{2}\rfloor\\ SG(n)=mex\{SG(y)|\lfloor\frac{n}{2}\rfloor\leq y\leq n-1\}\\ \] 设\(n=2^k-w\),其中: \[ -2^{k-1}+2\leq w\leq 2\\ \lfloor \frac {2^k-w}2\rfloor=2^{k-1}-\lfloor\frac w 2\rfloor\\ \] 当\(w=2\)时,原式\(=2^{k-1}-1>2^{k-1}-2\\\).反之.\(2^k-2\leq\)原式.因此数学归纳即可证明.