主题

主题

 
   

SG函数

  • 扯淡

能干啥:

处理一些博弈中的问题。

定义:

一个状态可以推导到的所有后继状态的SG值的mex。

我们知道,一般来说,博弈游戏的状态图是一张DAG。


  • 一个例子

给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。

我们处理出一个点的SG值。也就是说,把一个点视为一个状态。

那么没有出边的点的SG值为0。那么这是一个必败局面。

接下来我们发现:

  1. 如果一个点的SG值不为0,那么其可以推导到一个必败局面,此局面为必胜局面。

  2. 如果一个点的SG值为0,那么其推导到的所有局面都是必胜局面,此局面为必败局面。

于是我们得到结论:

 因此当前状态为必胜态当且仅当棋子在SG函数值不为0的点上。


  • 一个发现

若一个局面x,其sg(x)>0,则一定存在一个后续局面y,sg(y)=0。
若一个局面x,其sg(x)=0,则x的所有后续局面y,sg(y)>0。

这与必胜局面-必败局面的性质是一样的。

也就是说,如果SG=0的时候这个局面必败。那么就可以得到:

如果SG=0,则此局面必败,反则此局面必胜。

而满足上面条件“SG=0的时候这个局面必败”的,一般是“轮流操作,不能操作为败”的博弈游戏。

那么我们得到这种模型的SG函数的一个性质。即“SG=0则必败”。


  • 拓展

 给定一个有向无环图和一些棋子,每个棋子都有一个初始位置。两名选手交替操作,每次操作可以选择一枚棋子并将其沿有向边进行移动,无法移动者判负。

同样,视一个点为状态。

那么,当我们移动的某一枚棋子的SG值是k时,我们可以把它变成0到k-1之间的任意正整数,但绝对不能保持k不变。

那么就是Nim游戏了。把所有SG值处理出来,做异或即可。


  • BZOJ 1874

给定n堆石子,其中第i堆的石子数目为a[i]。两人轮流操作,每次操作可以选择一堆,取走x个石子,其中x必须是集合B中的数,不能操作者判负。问是否有先手必胜策略。

思路:

我们发现建图就是上面的模型了。

其实事实上是不用把图建出来的。

在引入SG定理之后,会有另一种理解。


  • SG定理

对于多个单一游戏,X=x[1..n],每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值等于这些单一游戏的sg值异或和。

          

此证明我们可以看看hihocoder的解释:

 

要证明这一点我们只要证明:

(1) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A,对于任意一个0 <= B < A,总存在一个X的后续局面Y,使得sg(Y) = B。

(2) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A,不存在一个X的后续局面Y,使得sg(Y) = A。

下先证明(1):

假设M = A xor B,设M表示为二进制之后最高位的1为第k位。所以A的第k位为1,B的第k位为0。又因为A的第k位为1,至少存在一个i,sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M < sg(x[i]),即一定通过某个操作使x[i]变为x[i'],且sg(x[i']) = sg(x[i]) xor M。那么:

sg(x[i']) xor Other = sg(x[i]) xor M xor Other = M xor A = B

下证明(2):

若sg(X) = A,sg(Y) = A。不妨设我们改变的游戏为x[i],则X=x[1..n], Y=x[1…i'…n]。有sg(x[i]) = sg(x[i']),产生矛盾,所以sg(Y)不可能等于A。

这也很类似于Nim游戏的证明方法。


  • Nim游戏

局面上一共有N堆石子,每一次我们只能改变一堆石子。那么我们可以将每一堆石子看作一个单一游戏。

对于一堆数量为x的石子的SG函数值,等于其后继状态的SG函数值的mex。即SG(x)=mex{SG(x-1),SG(x-2)...SG(1),SG(0)}。注意这里不能再把一堆石子视为总状态用SG定理,因为一次会改变多个石子(子状态),不满足SG定理的条件。

我们预处理数量为x的SG函数值,发现SG(x)=x。

于是总状态的SG函数值=每一堆石子的SG函数值的异或和=每一堆石子的个数的异或和。

由于这个游戏是“轮流操作,不能操作者必败”的模型,所以得到了Nim游戏的结论:

如果石子堆的个数的异或和为0,那么此局面必败。


  • hihocoder#1173

在Nim游戏中新增一条规则:

可以选择把一个石子堆分裂为两堆非空的石子堆。

思路:

这是一样的模型,于是我们得到:如果SG=0,则必败,反则必胜。

接下来,我们来讨论SG函数值。

发现一次只会改变一个石子堆,那么把石子堆当做子局面再好不过了。

即:最终局面是总局面,一堆石子是子局面。一次只会改变一个子局面,所以根据SG定理,有:

SG(最终局面)=SG(每一堆石子)的异或和

接下来考虑求一堆石子的SG值。

这一堆石子有两种后继状态:

  1. 分堆

  2. 不分堆

假设这一堆石子有x个。

对于不分堆的,这一堆石子会变为0,1...x-1。

对于分堆的,假设其分为了一堆大小为i与一堆大小为x-i的石子堆。那么这一个状态的SG函数值为SG(i) xor SG(x-i)。

至于原因,我们可以参考总局面的分析。这个状态只是一个规模较小的总局面而已。

所以对于一堆大小为x的石子,我们可以得到

SG(x)=mex{SG(0),SG(i),SG(i) xor SG(x-i)|1<=i<=x-1}

这就是此题的公式。


  • BZOJ 1188

 给定n堆石子从左到右排列,每次你可以选择一堆石子,从中取出一个石子,然后在它右边任选两堆(可以相同),并往这两堆中各放一个石子。不能操作者判负。

求先手是否有必胜策略。如果有必胜策略,要求输出字典序最小的第一步操作。

思路:

在这里只讨论第一问。

首先我们发现一次操作会对多堆石子造成影响。那么不能直接上SG定理。

 我们把游戏视为一个石子分裂开来,变为两枚石子坐落到右边的石子堆

这样一次操作就只会对一枚石子造成影响了。(当然对于一堆石子同样可以这样考虑,只是那样的话SG值不好计算),即

SG(总局面)=SG(石子的移动(分裂))

接下来我们发现,一个石子的移动(分裂)是通过位置来体现的,而不是像上题中,“一堆石子的改变通过石子的个数来体现”。

所以我们也可以这样表示:

SG(总局面)=SG(石子的位置)

接下来,对于一个在位置p的石子,假设分裂之后,到了位置i与位置j,那么我们可以得到这个状态的SG值是SG(i) xor SG(j)。

至于原因,我们同样可以参考上题中最后一部分的推导。类比对总局面的分析,这个状态只是一个规模比较小的总局面而已。

所以对于一枚位置在p的石子,我们可以得到

SG(p)=mex{SG(i) xor SG(j)|i,j>p}

这就是此题的公式。


  • BZOJ 1457

给定一张100*100的棋盘,在上面有一些“皇后”(可能有多个皇后在同一位置),两人轮流操作。

每次操作可以选择一个皇后进行移动,但不能使其横或纵坐标变大,也不能原地不动。

先将任意一个皇后移动至(0,0)者判胜。求先手是否有必胜策略。

思路:

此题不是无法操作者为败。

关键在于转换。我们发现如果走到了禁区,也就是下一步就可以胜利的,那么本方玩家就输了。

所以问题转换为:不走到禁区,无法操作者为败。

发现状态的转移是一张有向无环图。

当然,由于一次只会移动一枚棋子,我们可以把一个皇后单独拿出来考虑。之后变为处理每一个位置的SG函数值,最后xor即可。

 
 
评论
 
 
热度(1)