博弈问题

Published: by Creative Commons Licence

  • Tags:

动态规划解决博弈问题

博弈问题是指有两个玩家参与,每个玩家轮流做出决策,最后按照结果判断两个玩家的胜负情况。

如果一个游戏先手必胜,我们称该游戏处于N-position,否则后手必胜,我们称游戏处于P-position。

比如我们可以设计这样一个问题,有一组数,记做$a_1,a_2,\ldots,a_n$,数的总和为奇数。玩家A与B先后轮流决策,每次决策,该名玩家必须从数集中取走最左或最右的数,并从数集中删除。当数取完时,取得的数总和较大的胜利。问两个玩家都做最优决策时,哪个玩家会胜利。

这个问题,就是一个经典的博弈问题,我们可以用动态规划枚举所有可能的状态解决。记$dp(l,r)$表示当数集为$a_l,a_{l+1},\ldots,a_r$时,如果游戏是N-position,记为1,否则为P-position,记为0,可以很容易推出公式:$dp(l,r)=\max(1-dp(l+1,r),1-dp(l,r-1))$。

通过上面的动态规划我们就能以$O(n^2)$的时间复杂度解决博弈问题。如果我们将每个$dp$值视作一个结点,并从$dp(l+1,r)$和$dp(l,r-1)$中向$dp(l,r)$连接一条单向边,就可以构造一幅有向无环图。这幅图,可以清晰展示整个决策流程。

实际上,上面这个博弈问题,有非常简单的解决方案,那就是先手必胜,因为先手可以决定自己选择奇下标的数还是偶下标的数,因此必胜。可以看出虽然动态规划很强大,但是如果能直接给出有用的性质,可以大幅优化时间复杂度。

决策不一定是非胜即负的,比如考虑井字游戏,A持白子,B持黑子,每次可以在一个3*3表格中的一个空白格子中落子,如果三个白子连成一条直线,则A胜利,游戏结束,如果三个黑子连成一条直线,则B胜利。

很显然,如果双方都最优决策,那么游戏一定是平局的。在上面的这幅图中,这意味着有一部分结点代表着平局,平局的结点仅有向平局和胜利结点的边。

决策图不一定是无环的,比如这样一个游戏。如果A和B各持有两个整数,整数大小为0~9。二人轮流出牌,当A出牌时,将其中一张牌$x$换成$(x+y)%10$,其中y是上次B出的牌(默认A和B之前出的牌为0),对于B同理,只是y是A上次出的牌。当两个玩家手中持有的牌有一张换成0时,就认为该名玩家获得胜利。

很显然还是能通过状态压缩后建立图来解决。但是图中存在环,因此我们需要利用Bellman-Ford算法的松弛技术来完成。而一个结点如果在松弛完后,状态还是无法确定,那么这个结点一定代表平局。

Nim游戏和Sprague–Grundy函数

用动态规划解决博弈问题,很容易遇到瓶颈,比如状态数过多,无法逐一计算。

考虑Nim游戏,有$n$堆石头,第i堆石头有$a_i$个石头。玩家A、B轮流出手,每次出手,玩家必须选择一堆石头,并从中取走至少一个(最多可以全取)。如果无法完成操作,则认为玩家失败。

很显然,我们可以用动态规划,共$\prod_{i=1}^na_i$种状态,如果有100堆石头,每堆有100个石头,那么状态数将达到$100^{100}$,这显然是无法完成的。

这时候估计大家现在开始纷纷开脑洞,猜测每堆奇偶性会影响胜负等等。

下面说一下正确的解题姿势。

我们之前定义的动态规划函数的值仅为1和0,实际上我们抛弃了很多有用的信息,现在我们把它们加回来。首先所有堆石子为0的结点值为0,保持不变。但是对于其它结点$u$,我们记所有从它出发沿单向边移动一步可以抵达的结点集合为$v_1,v_2,\ldots,v_m$,记$sg(u)=mex(sg(v_1), sg(v_2), \ldots, sg(v_m))$。其中sg为Sprague–Grundy函数。而mex函数值为不同于所有参数的最小非负整数,比如$mex(1,2)=0$,$mex(0,2)=1$。

我们这里提到的Nim游戏,现在可以转换为另外一个问题,我们将每一堆都视作图中的一个棋子,每位玩家都可以选择任意一个棋子沿着有向边移动一步,如果所有棋子都无法移动,那么该名玩家失败。

下面我们讨论两个命题。

命题1:如果仅一枚棋子,那么游戏处于P-position当且仅当该棋子所在结点的sg值为0

证明:对于代表失败结果的结点,该棋子没有外向边,sg值显然为0。对于sg值为0的棋子,其所有相连的结点sg值肯定非0,因此其只能移动到N-position,即该结点必定为P-position。而对于sg值非0的棋子,其一定与某个sg值为0的结点相连,因此移动到该结点,游戏进入P-position,因此该结点对应的是N-position。这里证明不是非常严谨,可以换成归纳法进行证明。

命题2:如果有n个独立棋子,那么游戏处于P-position当且仅当所有棋子所在的sg值的异或和为0

证明:如果所有棋子都处在代表失败结果的结点,那么它们的sg值异或和自然是$0$。如果异或和为$0$,那么移动一枚棋子,记其原来的sg值为$a$,后来的sg值为$b$,必定有$a\neq b$,故此时异或和一定为$a\oplus b \neq 0$,因此N-position之后一定是P-position。而如果异或和$s$不为0,那么我们一定能找到一个棋子,其所处结点的sg值为$x$,满足x包含s中二进制的最高位,我们将该棋子从所在结点移动到sg值为$s\oplus x < x$的后继结点上,这时候异或和为$s\oplus x\oplus x\oplus x=0$,因此我们在N-position后一定能移动到P-position。配合归纳法可以证明。

这样我们就可以将从n堆石头中移除石头看做为n个独立游戏,而我们只要建立n堆石头各自的决策图,并计算棋子所在结点的sg值的异或和就可以判断游戏的状态了。但是由于Nim游戏中每个独立游戏拥有相同的决策图,因此我们可以复用,事实上,这里我们连决策图都不用建立,剩余n个石子对应的结点的sg值一定是n。

我们考虑到我们仅仅利用了决策图的sg值,与决策图具体代表的游戏是无关的。因此我们可以同时玩多个游戏,只需要利用sg函数就可以快速计算游戏所处的状态。比如我们将Nim游戏稍加变形,操作第i堆石头一次性必须移除1~i个石头。我们可以将每一堆石头建立独立的决策图,并计算每个结点的sg值。之后异或所有决策图上棋子的sg值,为0,则游戏处于P-position,否则处于N-position。

棋子分裂

我们稍微修改一下游戏。我们每次并不能移动棋子,但是可以选择一枚棋子,将其分裂为若干颗新的棋子,每个棋子落在特殊的结点上,保证若干步后游戏一定会结束。

这时候我们可以修改每个结点的sg值。在结点$u$上,假设有$k$种分裂策略,第i种分裂策略分裂后棋子分别落在$v_i^1,v_i^2,\ldots$。那么我们定义$sg(u)=mex(v_1^1\oplus v_1^2\oplus \ldots, \ldots, v_k^1\oplus v_k^2\oplus \ldots)$。

稍微修改命题2的证明可以很容易证明游戏处于P-position当且仅当所有棋子所在sg值的异或和为0。

Nim-k博弈

Nim游戏是Nim-k游戏的一个子集。Nim-k游戏定义为,有n堆石头,每堆分别有$a_1,a_2,\ldots,a_n$个石头,两个玩家A、B轮流执行下面操作:

选择1~k个堆,并从这k个堆中各移除若干个石头(不同的堆允许移除不同数量的石子,至少一个)。

如果一个玩家不能执行操作,则认为失败。A先手,B后手,问谁胜利。

对于我们之前的讨论的Nim游戏可以认为是Nim-k中k为1时的特殊情况。之前已经证明过了Nim游戏处于P-position当且仅当每堆石头石子数的异或和为0。这里我们直接给出Nim-k游戏的胜利条件,Nim-k游戏处于P-position当且仅当对于所有i,One(i)为$k+1$的倍数,其中One(i)表示$a_1,a_2,\ldots,a_n$中二进制第i位为1的数值个数。

很显然对于失败态,此时所有One(i)均为0,因此处于P-position。

对于某个P-position,对于任意一次操作后,我们记$j$为本次操作修改的最高比特位。由于是最高位,因此第$j$位的修改一定是$1\rightarrow 0$。$1\rightarrow 0$转移至少发生1次,最多发生k次,而由于初始时$One(j)=0(mod\phantom{1}k+1)$,因此修改后$One'(j)$一定不能整除$k+1$。即P-position转移后一定是N-position。

对于某个N-position,我们可以构造一种取法,使得下一个状态为P-position。我们维护一个集合(初始时为空),并不断向其中加入石堆。

  1. 找到一个最大的值j,使得$r=One(j)%(m+1)\neq 0$。如果不存在则算法终止,否则进入第2步。
  2. 设集合中石头堆中第j位为1的有a个,为0的有b个。那么如果$r\leq a$,我们从中选择r个石头堆将第j比特从1改为0,之后回到第1步。否则进入第3步。
  3. 如果$r+b\geq (m+1)$,则我们从中选择$m+1-r$个堆,将第j比特从0改为1,之后回到第1步。否则进入第4步。
  4. 我们取$r-a$个第j比特位1的石头堆加入集合,并将r个石头堆将第j比特从1改为0。这样我们就将第j比特修正为$k+1$的倍数。此时集合的大小为$r-a+a+b=r+b< m+1$,因此是合法的。

Nim-k游戏虽然类似于Nim游戏,但是不能保证对于一般的决策图也能满足这样的性质。即允许同时操作1~k个棋子在决策图上移动一步,不能保证每个对于每个比特i,$One(i)$均为0就能保证是P-position。考虑这样一个游戏,共4堆石头,数量为1,1,1,2,每次允许选择1~2个石头堆,并移除一个石子。这样4个石头堆对应的SG函数分别为1,1,1,0。因此满足$One(0)=3$能整除$2+1$,因此我们有理由认为这是一个P-position,但是实际上这是一个N-position,因为我们可以将局势改变为0,1,1,1。

斐波那契博弈

有n个石头,A、B轮流出手,每次至少拿一个石头,最多拿对手上一次取的数目的两倍。第一次取的人不能全取。问先手胜还是后手。

直接给答案,如果n是斐波那契数的一项,则游戏是P-position,否则是N-position。

先说点斐波那契数列的性质。

性质1:$\frac{3}{2}F_i<F_{i+1}<2F_i$

性质2:$F_{i+2}\geq 2F_i$

性质3:任意正整数都可以表示为若干个不连续的斐波那契数列项的和

对于0,0是斐波那契数列的第0项,因此是P-position。

下面我们通过归纳法证明,假设对于小于n的斐波那契项都是P-position。如果n是斐波那契数列的一项,我们可以得出n是前两项a、b的和,即a+b=n。则我们选择的一定小于a,否则对手会一次性将剩余的一起取走。由于归纳法,我们得知在经过若干轮交手后,B完成一次操作,使得取走的石子总数为a,留下的石子数为b。考虑B最后一次取的数量,至少为1,最多为$\frac{2}{3}a$。这样A之后最多取$\frac{4}{3}a<b$,即相当于我们在b上玩游戏,且A先手取,不能完全取尽。由归纳法知最后能取尽b的一定是B。因此B一定胜利,游戏处于P-position。

如果n不是斐波那契的任意项,我们可以将其展开为$f_1,f_2,\ldots,f_k$,满足两两不连续,且$f_1<f_2<\ldots,f_k$。A第一次取$f_1$个石子,而之后变成b不能先手取,之后我们能保证A能取到第$f_1,f_1+f_2,\ldots,n$个石子。

对偶博弈

n个石子,围成一个环。A、B轮流出手,每次可以取连续的一段石子,长度为1~k。不能完成操作的认为失败,问谁胜利。

当k为1的时候,每个玩家每次只能取走一个石子,因此游戏的胜负仅于n的奇偶性有关。

当k大于1时,若$n\leq k$,则A一次性能取完,A胜利。

当k大于1且$n>k$时,无论A第一次怎么取,设剩下m个连续石子,B可以通过一次操作,将石子分成两个等长连续段。之后无论A在哪个部分操作,B在另外部分同步操作,就能保证取走最后一个石子,获得胜利。

威佐夫博弈

有两堆石子,分别有n、m个石子。A、B轮流出手,每次可以从一堆取任意石头,或从两堆石子中取相同数量石头。问谁胜利。

不妨设$n\leq m$,游戏处于N-position当且仅当,存在一个k,使得$n=\lfloor Wk \rfloor$且$m=\lfloor (W+1)k\rfloor$,其中$W=\frac{1+\sqrt{5}}{2}$。

记$L(i)=\lfloor Wi \rfloor$,记$R(i)=\lfloor (W+1)i\rfloor$,有$L(N)\cap R(N)=\emptyset$和$L(N)\cup R(N)=N$。

两队列取值问题

有两个队列,每个队列包含一个非负值序列。给定一个阈值m(m不超过两个队列中所有元素之和),我们维护一个值sum,表示已经从两个队列中取出的数值的总和。

现在有两个人A、B。他们每次需要执行下面一个操作:

从两个队列中任选一个非空队列,从队列中弹出头部数值。

如果某个人完成一次操作后,sum值达到m,那么就判定他输,另外一个人赢。

这个问题的解法非常有趣。设队列1的长度为W,队列2的长度H,我们可以绘制一个H+1行W+1列的网格。第i行j列表示队列1已经弹出i个元素,队列2弹出j个元素,接下来操作的人是否会获胜。如果能获胜,我们将网格涂上白色,否则涂上黑色。同理对于无效网格(即执行完这些操作sum已经超出阈值),我们默认它们都是白色。

我们需要证明一些非常有用的命题:

命题1:任意两个黑色网格不会相邻

命题2:如果网格(a,b)是白色的,那么(a+1,b+1)也是白色网格。

证明:

如果(a+1,b+1)是无效网格,命题显然,之后仅考虑(a+1,b+1)是有效网格的情况。证明非常简单,如果网格(a+1,b+1)是有效网格,那么(a,b+1)和(a+1,b)一定也是有效网格。由(a,b)是白色可以推出(a,b+1)和(a+1,b)至少有一个是黑色网格,同理可以推出(a+1,b+1)一定是白色网格。

命题3:如果网格(a+1,b+1)是黑色的,那么(a,b)也是黑色的

证明:

由于(a+1,b+1)是黑色的,因此(a+1,b)和(a,b+1)都一定是白色的,由此可以得知(a,b)是黑色的。

命题4:如果(a+1,b+1)是有效网格,那么网格(a,b)和网格(a+1,b+1)一定同色,

证明:

根据命题2和命题3,我们只需要考虑不存在(a,b)是黑色的,而(a+1,b+1)是白色的情况。

考虑到(a,b)是黑色的,因此(a,b+1),(a+1,b)一定都是白色的有效网格。而考虑到(a+1,b+1)也是白色的,因此(a,b+2),(a+2,b)则一定是黑色的网格。

而由于(a+1,b+1)是白色的有效网格,因此(a+2,b+1),(a+1,b+2)至少一个是黑色网格。而再考虑到(a,b+2),(a+2,b)一定是黑色的网格,这与命题1相悖。因此命题得证。

因此我们希望得知网格(0,0)的颜色,只需要去查询(1,1)的颜色。因此我们实际上需要计算点 的颜色。总的时间复杂度为

提供一道问题

约瑟夫环

约瑟夫环的问题如下:

有n个人围成一圈,我们顺时针将人标记为0,1,…,n-1。从标记为0的人开始沿着顺时针报号(1,2,3等),谁报到k,就会被杀死。之后从被杀死的人后一个人继续重新开始报号。

在这样的一个游戏中,有若干个问题非常有趣:

问题1:第i个死亡的人是谁。

问题2:编号为j的人是第几个死亡的。

先考虑问题1,可以很容易推出一个递推算法,记$f(n,i)$表示剩余n个人的时候,第i个死亡的是谁。$g(n,j)$表示在只剩下n个人的时候,第j个人在第几个回合死去。

得出下面递推公式:

利用这些递推公式,我们可以在$O(n)$的时间复杂度内回答以上问题。

但是可以发现$f(n-1,i-1)+k$大部分时候都会不超过n,因此我们可以直接多步合并执行来优化函数$f$,同理$j-k$大部分时候也都不会小于0,因此可以同样进行优化。

优化后两个函数的时间复杂度应该为$O(min(n, k\ln\frac{n}{k}))$。

取反游戏

考虑有这样一个序列$a_1,a_2,\ldots, a_n$,A和B两个人用这个序列玩一个游戏,A先手,游戏步骤为:

取一个数值$i$,要求$a_i>0$,之后将$a_{i}$减去1,并且可以选择$i$后面的任意多个有效下标$I={i+1,i+2,\ldots}$,$I$可以为空集,对于任意$j\in I$,将$a_j$加上1。一旦有人不能再操作,那么这个人就输去比赛,问先手胜还是后手胜。

很容易发现这个问题和奇偶性有关,我们可以将问题重新描述为:

取一个下标$i$,要求$a_i$为奇数,选择任意多个有效下标$I={i,i+1,i+2,\ldots}$,对于任意$j\in I$,改变$a_j$的奇偶性。一旦有人面对全是偶数的情况,那么这个人就输去比赛,问先手胜还是后手胜。

由于奇偶性问题和数值大小是没有任何关系的,因此我们可以认为$a_i$都足够大,大到能支撑到游戏分出胜负为止。

这个问题还是很难解决,我们可以建立一个新的序列$b_i$,用于描述$a_i$,如果$a_i$与$a_{i-1}$的奇偶性不同,那么$b_i$为1,否则$b_i$为0。这样之前的问题中的区间$[l,r)$的翻转操作,可以用序列${b_i}$中位于$l$处的1移动到$r$处来描述。

取一个下标$i$,要求$b_i$为1,选择某个下标$j$,满足$i<j\leq n$,将位于$i$处的$1$移动$j+1$处。一旦面临$b_1,\ldots, b_n$都是0的情况,那么这个人就输去比赛,问先手胜还是后手胜。

考虑位于$i$处的1,移动1,相当于取石子游戏,它的$SG$函数值应该为$n+1-i$。而序列${b_i}$中的多个1,可以理解为多个独立的NIM游戏。

这边的证明是依赖于直觉的,暂时没有想到严谨的证明。

Nimber的加法和乘法

定义$mex(S)$表示$\min(N/S)$,即$S$中未出现的最小的自然数。其中$mex$的意思是minimum excludant。

Nimber的加法定义为:

其值与$a$和$b$二进制的亦或和相同。

Nimber的乘法运算定义为:

可以Nimber的加法运算符合封闭性,满足结合律和交换律,且加法单位元为$0$,每个数的逆元为自身,因此Nimber构成了一个加法群。

可以发现:

  • $a\otimes 0=0$
  • $a\otimes b=b\otimes a$
  • $a\otimes 1=a$
  • $(a\otimes b)\otimes c=a\otimes (b\otimes c)$
  • $(a\oplus b)\otimes c=(a\otimes c)\oplus (b\otimes c)$

即乘法运算也满足结合性,分配律,交换律等,存在单位元$1$,故Nimber构成了一个交换环。

要计算Nimber乘积,我们需要一些更加强力的性质:

对于任意$x,y<2^{2^a}$

  • $x\otimes 2^{2^a}=x\cdot 2^{2^a}$
  • $x\otimes y<2^{2^a}$
  • $2^{2^a}\otimes 2^{2^a}=\frac{3}{2}2^{2^a}$

利用这些性质我们可以设计一个递归算法,$O(\log_2a\log_2b)$求解$a\otimes b$。具体可以参照参考资料中《从“k倍动态减法游戏”出发探究一类组合游戏问题》这篇文章。

SG定理:设若干个棋子的SG函数值为$SG(x_1),\ldots,SG(x_n)$,则这些棋子共同的SG值为$SG(x_1)\oplus \ldots \oplus SG(x_n)$。

Tartan定理:记若干个游戏$G_1,\ldots,G_n$的积为$G(V,E)=G_1\cdot \ldots \cdot G_n$,其中$V=V_1\times \ldots \times V_N$(笛卡尔积),$E={(x,y)|(x_i,y_i)\in E_i}$,其中$x=(x_1,\ldots,x_n)$,$y=(y_1,\ldots,y_n)$。那么棋子$x=(x_1,\ldots,x_n)$的SG值为$SG(x_1)\otimes\ldots \otimes SG(x_n)$

问题1:我们有一个$n\times m$矩阵$A$,每个网格中都有一盏灯,灯或开或关。现在要求两人进行博弈,轮流操作,每次操作都需要选择一个矩形(长宽均至少为2),且矩阵的右下角的灯必须为开状态,操作完成后,矩阵的四角的灯的状态发生改变(由开变关或由关变开)。无法操作的人视作失败。问先手还是后手必胜。一开始总共有$k$盏灯开着,告诉你它的坐标。这里$1\leq n,m\leq 10^{18},0\leq k\leq 10^5$。

发现单一维度下就是一个普通的NIM游戏,因此我们将行游戏和列游戏计算笛卡尔积就可以得出这个游戏。故$SG(x,y)=x\otimes y$。

一道原题。把这个问题扩展到三维空间题目

这里顺带一提,允许退化的情况(即高度和宽度允许为1),这时候我们在左边和上边额外加一列一行,行号和列号均为0,且这一行一列的SG函数值均为0即可。这时候比如对于高度退化的情况下,我们可以认为矩阵的上部正好匹配了最顶上的那一行。于是乎我们吧原先的行列编号全部加1,就可以复用解法了。

问题2:有$n$个堆,第$i$个堆有$a_i$个石头,两人轮流操作,每次操作需要选择一个堆,拿走至少1个,最多$m$个石头,求先手还是后手必胜。这里$1\leq a_i\leq 10^9$,$1\leq n\leq 10^5$,$1\leq m\leq 10^3$

由于不同堆的规则是相同的,因此我们可以只处理一次SG函数。同时可以发现SG的函数应该满足$SG(x)=SG(x+m+1)$(周期性)。因此我们可以只需要算出$SG(i)$,其中$i\leq m$。

问题3:有一行灯(第一个灯的编号为$0$),每个灯的状态为$0,1$,对应关灯和开灯状态。之后每次你可以选择某个非空子序列,要求前缀最靠右的灯一定处于开状态。要求将整个子序列中的灯的状态进行转换。现在两人轮流进行操作,不能操作的人为输家。问先手还是后手必胜。

这个游戏是Ruler游戏。第$i$盏灯的SG函数值为$SG(i)=lowbit(i+1)$,即$i$二进制形式中的最低一位$1$。具体证明不会。

问题4:有一行灯(第一个灯的编号为$0$),每个灯的状态为$0,1$,对应关灯和开灯状态。之后每次你可以选择长度不超过$k$的子序列,要求子序列z最靠右的的灯一定处于开状态。要求将整个子序列中的灯的状态进行转换。现在两人轮流进行操作,不能操作的人为输家。问先手还是后手必胜。

这道题,与问题3有点类似,只是为3没有长度约束。打表可以发现,对于$k$,其约束与$highbit(k)$是相同的(从$k$减少到$highbit(k)$不会影响最终的胜负)。同时会发现SG函数的周期正好为$highbit(k)$的因数,而前$highbit(k)$个灯的SG函数与没有约束的情况下是相同的,即普通的Ruler博弈。

利用取模,我们对于位于$x$的灯,我们可以推出$SG(x)=lowbit((x\mod highbit(k)) + 1)$。

问题5:我们有一个$n\times m$矩阵$A$,每个网格中都有一盏灯,灯或开或关。现在要求两人进行博弈,轮流操作,每次操作都需要选择一个矩形(长宽均至少为2,宽度不能超过$W$,高度不能超过$H$),且矩阵的右下角的灯必须为开状态,操作完成后,矩阵的四角的灯的状态发生改变(由开变关或由关变开)。无法操作的人视作失败。问先手还是后手必胜。一开始总共有$k$盏灯开着,告诉你它的坐标。这里$1\leq n,m\leq 10^{18},0\leq k\leq 10^5$。

可以发现行游戏和列游戏都是问题4,我们可以将其进行笛卡尔积得到问题5。而合并后的游戏可以用Nimber积求解。

提供一道题目:SRM748 Rectoggle。

Anti-Nim

Anti-Nim的问题描述和Nim游戏基本相同,除了拿走最后一个石子的人认为是输家。

命题:给定$n$个游戏,双方轮流操作,每次操作可以操作一个游戏。当所有游戏的SG函数值均为$0$的时候认为最后一次操作的人失败。那么先手仅在$3$种情况下必胜:

  1. 每个游戏的SG函数值均为$0,1$,且这些游戏的SG函数值亦或和为$0$。
  2. 存在正好一个游戏的SG函数值大于$1$。
  3. 存在多于一个游戏的SG函数值大于$1$,且这些游戏的SG函数值亦或和大于$0$。

证明:

首先我们可以忽略状态为$0$的单个游戏,因为如果一方将其变成非$0$,那么另外一方可以将其重新变回$0$。同样我们也不考虑SG函数值从$1$变到更大的情况,因为一方将其变大,另一方一定可以将其还原。

第一个条件如果成立,那么必胜是很显然的,因此不讨论。

当第二个条件成立的时候,如果有偶数个游戏的SG函数值为1,则我们将那么SG函数值大于$1$的游戏转换为$1$,否则转换为$0$,因此这样就进入了第一个条件下先手必败的状态。

现在仅考虑存在多于一个游戏的SG函数值大于$1$的情况。如果$SG$函数值为非$0$,先手可以将其转换为$0$,而后手只能将其转换为非$0$。同时可以发现后手操作时,面对的都是所有游戏SG函数值的亦或和为$0$的情况,因此此时至少有两个游戏的SG函数值大于$1$,不可能进入条件$2$逃离。

两端取值问题

题目1:给定一个长度为$n$的序列$a_1,\ldots,a_n$。之后两人轮流操作,每个人在自己的回合可以从队列头部或尾部弹出一个数值(弹出后这个数值就从队列中删除)。如果序列为空则游戏结束。在游戏结束后,如果一方弹出的数的总和比另外一方大,则获得胜利。保证$a_1+\ldots+a_n$是奇数(即不会出现平局)。问先手必胜还是后手必胜。其中$2\leq n\leq 10^5$,且$n$是偶数。

先手必胜,因为先手可以决定自己拿走所有奇数下标的数还是偶数下标的数。

题目2:给定一个长度为$n$的序列$a_1,\ldots,a_n$。之后两人轮流操作,每个人在自己的回合可以从队列头部或尾部弹出一个数值(弹出后这个数值就从队列中删除)。如果序列只剩下一个元素时游戏结束。先手方希望让剩下的元素尽可能大,而后手方希望让剩下的元素尽可能小,两者都是最优决策。问最后剩下的数为多大。其中$1\leq n\leq 10^6$

考虑先手面对偶数的情况。可以发现先手一定可以取到$\max(x_{n/2},x_{n/2+1})$,因此这是结果的一个下界。而后手只要做与先手相反的操作(先手弹出头部,则后手弹出尾部),就可以保证最终剩下的数是$x_{n/2},x_{n/2+1}$中的一个(这显然对于后手是最优的,即最终值正好等于下界)。因此这时候结果一定是$\max(x_{n/2},x_{n/2+1})$。

可以发现对于后手面的偶数的情况下,最终结果为$\min(x_{n/2},x_{n/2+1})$,证明方式类似。

再考虑先手面对奇数的情况。我们知道如果我们选择弹出头部,则最终结果为$\min(x_{(n+1)/2},x_{(n+1)/2+1})$,对应的如果我们选择弹出尾部,则结果为$\min(x_{(n-1)/2},x_{(n-1)/2+1})$。而由于先手希望结果尽可能大,因此答案为$\max(\min(x_{(n+1)/2},x_{(n+1)/2+1}),\min(x_{(n-1)/2},x_{(n-1)/2+1}))$。

一道题目

参考资料