1. 巴什博奕

定义:只有一堆$n$个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,最多取$m$个。最后取光者得胜。

这个问题很基础。

先说结论:

  • 如果$n\text{ mod }(m+1)=0$,那么后手必胜
  • 否则先手必胜

为什么呢?

首先考虑第一种情况:$n\text{ mod }(m+1)=0$

此时设先手取了$x,x\in [1,m]$个,那么后手只要取$m+1-x$个就行了,这样$n\text{ mod }(m+1)=0$依然成立。

最后必然会出现剩下$m+1$个物品,先手无法一次取完,但Ta必须取一个,这样后手就一定能一次取完剩下的所有的物品了。

对于第二种情况,只要先手先取$n\text{ mod }(m+1)$个物品,这样局势就又满足了$n\text{ mod }(m+1)=0$,而这时后手成先手了。。。因此这种情况下先手必胜啦!

模板:

#include <bits/stdc++.h>
using namespace std;
int m,n,ans;
int main()
{
    scanf("%d%d",&m,&n);//物品数为m,上限为n
    if(!(ans=(m%(n+1)))){printf("none\n");return 0;}//必败
        //以下是从小到大输出第一次取的物品数
    printf("%d",ans);
    for(ans+=n+1;ans<=m&&ans<=n;ans+=n+1)printf(" %d",ans);
    for(ans-=n;ans>m&&ans<=n;ans++)printf(" %d",ans);
    return 0;
}

2. 威佐夫博弈

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

首先分析一波:

设$(a,b)$表示两堆分别有$a$个和$b$个物品。

因为$(a,b)$与$(b,a)$等价,因此不妨设$a\leq b$。

那么:

  • 对于局势$(0,0)$,先手输,先手无必胜策略
  • 对于当前局势,若能经过一次操作得到对手无不胜策略,则此时此人有必胜策略
  • 对于当前局势,若无论如何操作一次,都会得到对手有必胜策略的局势,则此时此人无必胜策略

我们称先手(当前操作的人)无必胜策略的局势为“奇异局势”。

先手动列举一下前几个奇异局势$(a,b),a\leq b$:

$$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20)…$$

观察一下规律,我们欣喜地发现,第$k$个奇异局势的$a_k$为前$k-1$个奇异局势中未出现的最小自然数(即该自然数不等于$a_x$或$b_x,x\in [1,k-1]$,且该自然数最小)。而$b_k=a_k+k$。

这是为什么呢?

不妨把局势放到二维平面中。

对于奇异局势$(a,b)$,$(a,b+k),(a+k,b),(a+k,b+k)$都不是奇异局势。

因此我们先在二维平面中找到第一个奇异局势——$(0,0)$,并把$(0,k),(k,0),(k,k)$都涂黑。

涂黑的都是“非奇异局势”,即有必胜策略的局势。

接着找到$x,y$最小且$x\leq y$且未被涂黑的点,发现是$(1,2)$。那么$(1,2)$为第二个奇异局势。

把$(1,2+k),(1+k,2),(1+k,2+k)$都涂黑。

然后找到$(1,2)$的对称点$(2,1)$,显然它也是个奇异局势,但我们不用管它(因为它的$a>b$)。我们把$(2,1+k),(2+k,1),(2+k,1+k)$涂黑。

接着找到$x,y$最小且$x\leq y$且未被涂黑的点,发现是$(3,5)$。那么$(3,5)$为第二个奇异局势。

还是老规矩,把非奇异局势涂黑,再找到对称点,涂黑非奇异局势。。。

以此类推,就能找出所有的奇异局势了。

显然,若$a_k$等于了$a_x$或$b_x,x\in [1,k-1]$,那么$x=a_k$这一列显然都被涂黑了,与我们的推导相矛盾,所以$a_k$必然是未出现过的最小自然数。

而$b_k=a_k+k$我也不会证,大概是因为$(a+k,b+k)$会被涂黑的缘故。。。(QvQ表打我啊!)

知道了奇异局势,那么就可以轻松解决威佐夫博弈问题啦~

  • 当$a=b$时,只要同时从两堆中取走$a$个物体,就变为了奇异局势$(0,0)$
  • 当$a=a_k,b>b_k$时,只要取走$b-b_k$个物体,就能变为奇异局势
  • 当$a=a_k,b < b_k$时,只要从两堆中拿走$a-a _ {b-a}$个物体就能变为奇异局势
  • 当$a>a_k,b=a_k+k$时,只要从第一堆中拿走若干变成$a_k$即可
  • 当$a < a_k,b=a_k+k$时,只要从第二堆中拿走若干,变成$a$对应的局势即可。

请注意上面的$a$均小于等于$b$。

现在的问题就是如何判断当前局势是不是奇异局势了。

这里有个公式:

$$a_k=\left [ \frac{k(1+\sqrt{5})}{2}\right ] $$

(其中中括号表示取整数部分)

然后$b_k=a_k+k$

因此我们只需要先求出$k=a-b$,再根据$k$判断$a_k$是否满足上面那个公式就行了。

。。。

看了半天还是不知道这个公式是怎么推导的啊!!!

嘤嘤嘤QvQ

算啦,那就死记硬背啦~(≧▽≦)/~啦啦啦

顺带一提,$\frac{1+\sqrt{5}}{2}\approx 1.61803398874989484820$,也就是传说中的黄金分割比。

那么公式我们只要记$a_k=\left [ 1.618k \right ]$即可。

至此,威佐夫博弈也差不多弄完啦~

段错误,作者已放弃。

模板:

#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    scanf("%d%d",&a,&b);//输入两堆物品数
    if(a>b)swap(a,b);
    if(a==floor(1.618*(b-a)))printf("0\n");//后手必胜
    else printf("1\n");//先手必胜
    return 0;
}

3. SG函数

也就是死GAY函数。

它和Nim游戏有莫大的联系。

直接转两篇文章吧,写得很棒~我觉得没必要在重复造轮子了QvQ

好吧我承认我偷懒了QvQ但是我还帮他排版了呀!表打我嘛QvQ

原文地址:

博弈论(一):Nim游戏

重点结论:对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当且仅当a1^a2^...^an=0,其中^表示位异或(xor)运算。(P-position的定义在后文会给出啦QvQ)

Nim游戏是博弈论中最经典的模型(之一?),它又有着十分简单的规则和无比优美的结论,由这个游戏开始了解博弈论恐怕是最合适不过了。

Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。满足以下条件的游戏是ICG(可能不太严谨):

  1. 有两名选手;
  2. 两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动;
  3. 对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素;
  4. 如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手负。

根据这个定义,很多日常的游戏并非ICG。例如象棋就不满足条件3,因为红方只能移动红子,黑方只能移动黑子,合法的移动集合取决于轮到哪名选手操作。

通常的Nim游戏的定义是这样的:

有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

这游戏看上去有点复杂,先从简单情况开始研究吧。

如果轮到你的时候,只剩下一堆石子,那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩,然后对手就输了。

如果剩下两堆不相等的石子,必胜策略是通过取多的一堆的石子将两堆石子变得相等,以后如果对手在某一堆里拿若干颗,你就可以在另一堆中拿同样多的颗数,直至胜利。

如果你面对的是两堆相等的石子,那么此时你是没有任何必胜策略的,反而对手可以遵循上面的策略保证必胜。

如果是三堆石子……好像已经很难分析了,看来我们必须要借助一些其它好用的(最好是程式化的)分析方法了,或者说,我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。

定义P-position和N-position,其中P代表Previous,N代表Next。

直观的说,上一次move的人有必胜策略的局面是P-position,也就是“后手可保证必胜”或者“先手必败”,现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜”。

更严谨的定义是:

  1. 无法进行任何移动的局面(也就是terminal position)是P-position;
  2. 可以移动到P-position的局面是N-position;
  3. 所有移动都导致N-position的局面是P-position。

按照这个定义,如果局面不可能重现,或者说positions的集合可以进行拓扑排序,那么每个position或者是P-position或者是N-position,而且可以通过定义计算出来。

以Nim游戏为例来进行一下计算。

比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略,也就是这是一个P-position,下面我们依靠定义证明一下(3,3)是一个P是一个P是一个P-position。

首先(3,3)的子局面(也就是通过合法移动可以导致的局面)有(0,3)(1,3)(2,3)(显然交换石子堆的位置不影响其性质,所以把(x,y)和(y,x)看成同一种局面),只需要计算出这三种局面的性质就可以了。

(0,3)的子局面有(0,0)、(0,1)、(0,2),其中(0,0)显然是P-position,所以(0,3)是N-position(只要找到一个是P-position的子局面就能说明是N-position)。

(1,3)的后继中(1,1)是P-position(因为(1,1)的唯一子局面(0,1)是N-position),所以(1,3)也是N-position。

同样可以证明(2,3)是N-position。

所以(3,3)的所有子局面都是N-position,它就是P-position。

通过一点简单的数学归纳,可以严格的证明“有两堆石子时的局面是P-position当且仅当这两堆石子的数目相等”。

根据上面这个过程,可以得到一个递归的算法——对于当前的局面,递归计算它的所有子局面的性质,如果存在某个子局面是P-position,那么向这个子局面的移动就是必胜策略。

当然,可能你已经敏锐地看出有大量的重叠子问题,所以可以用DP或者记忆化搜索的方法以提高效率(简单的博弈问题想到这一步就可以了)。

但问题是,利用这个算法,对于某个Nim游戏的局面(a1,a2,...,an)来说,要想判断它的性质以及找出必胜策略,需要计算O(a1a2...an)个局面的性质,不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法。

直接说结论好了。(Bouton’s Theorem)对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当且仅当a1^a2^...^an=0,其中^表示异或(xor)运算。

怎么样,是不是很神奇?我看到它的时候也觉得很神奇,完全没有道理的和异或运算扯上了关系。但这个定理的证明却也不复杂,基本上就是按照两种position的证明来的。

根据定义,证明一种判断position的性质的方法的正确性,只需证明三个命题:

  1. 这个判断将所有terminal position判为P-position;
  2. 根据这个判断被判为N-position的局面一定可以移动到某个P-position;
  3. 根据这个判断被判为P-position的局面无法移动到某个P-position。

第一个命题显然,terminal position只有一个,就是全0,异或仍然是0。

第二个命题,对于某个局面(a1,a2,...,an),若a1^a2^...^an!=0,一定存在某个合法的移动,将ai改变成ai’后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=k,则一定存在某个ai,它的二进制表示在k的最高位上是1(否则k的最高位那个1是怎么得到的)。这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k,此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0

第三个命题,对于某个局面(a1,a2,...,an),若a1^a2^...^an=0,一定不存在某个合法的移动,将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。因为异或运算满足消去率,由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。

根据这个定理,我们可以在O(n)的时间内判断一个Nim的局面的性质,且如果它是N-position,也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。

博弈论(二):Sprague-Grundy函数

上一期的文章里我们仔细研究了Nim游戏,并且了解了找出必胜策略的方法。但如果把Nim的规则略加改变,你还能很快找出必胜策略吗?

比如说:有n堆石子,每次可以从第1堆石子里取1颗、2颗或3颗,可以从第2堆石子里取奇数颗,可以从第3堆及以后石子里取任意颗……这时看上去问题复杂了很多,但相信你如果掌握了本节的内容,类似的千变万化的问题都是不成问题的。

现在我们来研究一个看上去似乎更为一般的游戏:给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。

事实上,这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说,任何一个ICG都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。

下面我们就在有向无环图的顶点上定义Sprague-Garundy函数。

首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0

对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Garundy函数g如下:g(x)=mex{ g(y) | y是x的后继 }

来看一下SG函数的性质。首先,所有的terminal position所对应的顶点,也就是没有出边的顶点,其SG值为0,因为它的后继集合是空集。然后对于一个g(x)=0的顶点x,它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点,必定存在一个后继y满足g(y)=0

以上这三句话表明,顶点x所代表的postion是P-position当且仅当g(x)=0(跟P-positioin/N-position的定义的那三句话是完全对应的)。我们通过计算有向无环图的每个顶点的SG值,就可以对每种局面找到必胜策略了。但SG函数的用途远没有这样简单。如果将有向图游戏变复杂一点,比如说,有向图上并不是只有一枚棋子,而是有n枚棋子,每次可以任选一颗进行移动,这时,怎样找到必胜策略呢?

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时,表明对于任意一个0<=i<k,都存在x的一个后继y满足g(y)=i

也就是说,当某枚棋子的SG值是k时,我们可以把它变成0、变成1、……、变成k-1,但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏,Nim游戏的规则就是:每次选择一堆数量为k的石子,可以把它变成0、变成1、……、变成k-1,但绝对不能保持k不变。这表明,如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子,那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略!

对于n个棋子,设它们对应的顶点的SG值分别为(a1,a2,...,an),再设局面(a1,a2,...,an)时的Nim游戏的一种必胜策略是把ai变成k,那么原游戏的一种必胜策略就是把第i枚棋子移动到一个SG值为k的顶点。这听上去有点过于神奇——怎么绕了一圈又回到Nim游戏上了。

其实我们还是只要证明这种多棋子的有向图游戏的局面是P-position当且仅当所有棋子所在的位置的SG函数的异或为0。这个证明与上节的Bouton’s Theorem几乎是完全相同的,只需要适当的改几个名词就行了。

刚才,我为了使问题看上去更容易一些,认为n枚棋子是在一个有向图上移动。但如果不是在一个有向图上,而是每个棋子在一个有向图上,每次可以任选一个棋子(也就是任选一个有向图)进行移动,这样也不会给结论带来任何变化。

所以我们可以定义有向图游戏的和(Sum of Graph Games):设G1、G2、……、Gn是n个有向图游戏,定义游戏G是G1、G2、……、Gn的和(Sum),游戏G的移动规则是:任选一个子游戏Gi并移动上面的棋子。

Sprague-Grundy Theorem就是:g(G)=g(G1)^g(G2)^...^g(Gn)。也就是说,游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。

再考虑在本文一开头的一句话:任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。

我们给每个ICG的每个position定义SG值,也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时,只需对于每个游戏找出求它的每个局面的SG值的方法,就可以把这些SG值全部看成Nim的石子堆,然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了!

回到本文开头的问题。

有n堆石子,每次可以从第1堆石子里取1颗、2颗或3颗,可以从第2堆石子里取奇数颗,可以从第3堆及以后石子里取任意颗……

我们可以把它看作3个子游戏,第1个子游戏只有一堆石子,每次可以取1、2、3颗,很容易看出x颗石子的局面的SG值是x%4

第2个子游戏也是只有一堆石子,每次可以取奇数颗,经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子,就是一个Nim游戏。

对于原游戏的每个局面,把三个子游戏的SG值异或一下就得到了整个游戏的SG值,然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。

其实看作3个子游戏还是保守了些,干脆看作n个子游戏,其中第1、2个子游戏如上所述,第3个及以后的子游戏都是“1堆石子,每次取几颗都可以”,称为“任取石子游戏”,这个超简单的游戏有x颗石子的SG值显然就是x。

其实,n堆石子的Nim游戏本身不就是n个“任取石子游戏”的和吗?

所以,对于我们来说,SG函数与“游戏的和”的概念不是让我们去组合、制造稀奇古怪的游戏,而是把遇到的看上去有些复杂的游戏试图分成若干个子游戏,对于每个比原游戏简化很多的子游戏找出它的SG函数,然后全部异或起来就得到了原游戏的SG函数,就可以解决原游戏了。


好啦,从这里开始都是我自己写的啦!

对于SG函数,我也总结一下自己的想法吧。

  • 必败点的SG函数值为0
  • 必胜点的SG函数值大于0
  • 一个必败点的后继节点必然全是必胜点
  • 一个必胜点的后继节点中必然有必败点
  • 一个SG值为$k,k>0$的点,必然能转到SG值为$x,x\in [0,k-1]$的点

想清楚了上面这5点,看懂上面那两篇文章也就不难啦~

Nim游戏模板:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,ans;
    cin>>n>>ans;
    for(int i=2;i<=n;i++)cin>>a,ans^=a;
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

SG函数模板(有向无环图博弈SG函数):

/*
题意:给出一个有向无环图,再给出n个棋子所在的点的编号
每次双方可以任选某一颗可移动的棋子移动到它所在的点的某一个后继节点
可移动指的是它所在的点有后继节点
若某方无法移动则该方判输
求先手是否必胜
点数<=1000,有多组游戏
*/

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, deg[NS], sg[NS];

vector<int> g[NS], gi[NS];

queue<int> que;

bool book[NS];

void cal(int a)//计算点a的SG值
{
    for (int i = 0; i < gi[a].size(); i += 1) book[sg[gi[a][i]]] = 1;
    sg[a] = 0; while (book[sg[a]]) sg[a]++;
    for (int i = 0; i < gi[a].size(); i += 1) book[sg[gi[a][i]]] = 0;
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 0; i < n; i += 1)
    {
        IN(deg[i]);
        for (int j = 1, a; j <= deg[i]; j += 1)
            IN(a), g[a].push_back(i), gi[i].push_back(a);
        if (!deg[i]) que.push(i);
    }
    while (!que.empty())//按拓扑序来算SG值
    {
        int F = que.front(); que.pop();
        for (int i = 0, tmp; i < g[F].size(); i += 1)
            if (tmp = g[F][i], --deg[tmp] == 0)
                cal(tmp), que.push(tmp);
    }
    while (IN(m), m)
    {
        int res = 0;
        for (int i = 1, j; i <= m; i += 1) IN(j), res ^= sg[j];
        if (res) puts("WIN"); else puts("LOSE");
    }
    return 0;
}

Finish

至此,博弈论入门知识已经讲得差不多啦QvQ

但貌似还有更多更难的问题等着我们去解决呀!QvQ


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *