我们把动物利用大自然移动的瘾魂,

在决策人期待的空间里,

形成三维均衡的学术理论,

称为博弈论。

社会学领域非常经典的博弈论问题就是囚徒困境,

在算法竞赛领域的博弈论往往归纳为ICG(公平组合游戏),典型表现为取石子游戏。

博弈论初探

博弈论入门之巴什博弈

  • 有n个物品放置一堆,两个人轮流从中取物, 规定每次至少取1个,最多取m个,最后取光者得胜。

我们从最简单的情景开始分析

当石子有1~m个时,毫无疑问,先手必胜

当石子有m+1个时,先手无论拿几个,后手都可以拿干净,先手必败

当石子有m+2~2m时,先手可以拿走几个,剩下m+1个,先手必胜

我们不难发现,面临m+1个石子的人一定失败。

这样的话两个人的最优策略一定是通过拿走石子,使得对方拿石子时还有m+1个

  • 设当前的石子数为n=k∗(m+1)+r

先手会首先拿走r个,接下来假设后手拿走x个,先手会拿走m+1−x个,这样博弈下去后手最终一定失败

  • 设当前的石子数为n=k∗(m+1)

假设先手拿x个,后手一定会拿m+1−x个,这样下去先手一定失败

例题

  1. hdu1846
  • 巴什博弈裸题
#include<cstdio>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if(n%(m+1) !=0) printf("first\n");
        else printf("second\n");
    }
    return  0;
}
  1. hdu4764
  • 唐和江是好朋友。为了决定晚餐谁请客,他们在玩游戏。具体来说,唐和江将轮流在白板上写数字(整数)。唐先写,然后写江,再写唐,等等……此外,假设前一轮中所写的数字是X,下一个玩游戏的人应该写一个数字Y,使1 <= Y - X <= k。第一个写数字不小于N的人将输掉游戏。注意,在第一轮中,Tang只能在[1,k]范围内(包括1和k)写下一个数字。你可以认为唐和江的表现将一直处于最佳状态,因为他们都是非常聪明的学生。

  • 我们可以把模型抽象一下,有n−1个石子,一个人最多拿k个,问最后谁赢

  • ——》裸的巴什博奕

#include<cstdio>
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        if((n-1)%(m+1) !=0) printf("Tang\n");
        else printf("Jiang\n");
    }
    return  0;
}
  1. hdu1847
  • 巴什博弈的一个小变形。第一个必胜态不难推理出来是3。那么再仔细想,其实只需要用到1和2,等同于k值为2的巴什博弈。
#include<cstdio>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n%3!=0) printf("Kiki\n");
        else printf("Cici\n");
    }
    return  0;
}

博弈论入门之斐波那契博弈

  • 有一堆石子,两个顶尖聪明的人玩游戏,先取者可以取走任意多个,但不能全取完,以后每人取的石子数不能超过上个人的两倍

斐波那契博弈有一个非常重要的性质:

先手必败,当且仅当石子数为斐波那契数

是不是很神奇??

证明如下:

  • n=2 先手输

  • n=3 先手输

  • 假设n<=k,且牌数为Fibonacci数时,都是先手必输。

  • 那么n=k+1时,因为F(k+1)=F(k)+F(k−1),即要取完F(k+1)张牌,可以分成两步:先取完F(k−1)张牌,再取完F(k)张牌。对于F(k−1)张牌,先取A者输!意味着对于F(k)张牌,A还得必须先取,所以A输。

那么,牌数为非Fibonacci数时,先取牌者有没有必胜的策略呢?

引用一个定理:当一个数不是Fibonacci数时,这个数必然等于若干个Fibonacci数之和,并且这些Fibonacci数在Fibonacci数列中都不相邻。

  • 对于非Fibonacci数a,a=f(n)+…+f(i)+f(j) ,其中f(j)是式中最小的Fibonacci数,f(i)是第二小的Fibonacci数。

  • 由于f(i)、f(j)在Fibonacci数列中并不是相邻的,所以f(i)>2∗f(j)。所以先取者可以直接取走f(j)张牌,后取者无法一次取走f(i)张牌,f(i)是Fibonacci数,由前面的分析,后取者必败。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<int,int>mp;

void init()
{
    ll a=1,b=2;
    mp[a]=1,mp[b]=1;
    for(int i=3;i<100;i++)
    {
        ll c=a+b;
        a=b;
        b=c;
        mp[a]=1,mp[b]=1;
    }
}

int main()
{
    int n;
    init();
    while(scanf("%d",&n)&&n)
    {
        if(mp[n]) printf("Second win\n");
        else printf("First win\n");
    }
    return  0;
}

博弈论入门之nim游戏

  • 有n堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),没法拿的人失败。问谁会胜利?

面对新的博弈问题,我们按照套路,从简单的情况入手

当只有1堆石子的时候,先手可以全部拿走。先手必胜

当有2堆石子且石子个数相同的时候,先手不论拿多少,后手都可以从另一堆中拿同样多的石子,先手必败,否则先手必胜

当有三堆的时候呢?

当有n堆的时候呢?

这样玩下去确实是很繁琐,不过前辈们总结出了一条非常厉害的规律!

当n堆石子的数量异或和等于0时,先手必胜,否则先手必败

证明如下:

  • 设^表示异或运算

  • nim游戏的必败态我们是知道的,就是当前n堆石子的数量都为零

  • 设a[i]表示第i堆石子的数量,那么当前局面就是

  • 0 ^ 0 ^ 0 ^ … ^ 0 = 0

  • 对于先手来说,如果当前局面是

  • a1 ^ a2 ^ a3 ^ … ^ an = k

  • 那么一定存在某个ai,它的二进制表示在最高位k上一定是1

  • 我们将ai ^ k,这样就变成了

  • a1 ^ a2 ^ a3 ^ … ^ an ^ k = 0

  • 此时先手必胜

  • 对于先手来说,如果当前局面是

  • a1 ^ a2 ^ a3 ^ … ^ an = 0

  • 那么我们不可能将某一个ai异或一个数字后使得

  • a1 ^ a2 ^ a3 ^ … ^ an = 0

  • 此时先手必败

例题

  1. 洛谷P2197
  • Nim裸题
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n,m=0;scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int x;scanf("%d",&x);
            m^=x;
        }
        if(m) printf("Yes\n");
        else printf("No\n");
    }
    return  0;
}
  1. POJ1704
  • 好巧妙的Nim啊!!!

  • 首先我们想到一种必败态:即仅有两个点且相邻

  • 那么我们可以把所有的点排序之后两两捆绑,这样如果A移动第一个,那么B可以把第二个移动相同的步数

  • 这样我们就解决了顺序的问题

  • 那么接下来就考虑如何解决博弈问题

  • 这里有个神仙操作

  • 把两点直接的距离看做一堆石子,然后请Nim来就可以啦

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

int a[1005];

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n,m;scanf("%d",&n);
        for(int i=0;i<n;i++)  scanf("%d",&a[i]);
        sort(a,a+n);
        if(n&1)
        {
            m=a[0]-1;
            for(int i=2;i<n;i+=2)
                m^=(a[i]-a[i-1]-1);
        }
        else
        {
            m=0;
            for(int i=1;i<n;i+=2)
                m^=(a[i]-a[i-1]-1);
        }
        if(m) printf("Georgia will win\n");
        else printf("Bob will win\n");
    }
    return  0;
}

变形

  • Moore’s Nim

    • n堆石子,每次从不超过k堆中取任意多个石子,最后不能取的人失败。

    这是一个nim游戏的变形,结论:把n堆石子的石子数用二进制表示,统计每个二进制位上1的个数,若每一位上1的个数mod(k+1)全部为0,则必败,否则必胜。

    证明:

    • 全为0的局面一定是必败态。
    • 任何一个P状态,经过一次操作以后必然会到达N状态:在某一次移动中,至少有一堆被改变,也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子,所以对于任何一个二进制位,1的个数至多改变k。而由于原先的总数为k+1的整数倍,所以改变之后必然不可能是k+1的整数倍。故在P状态下一次操作的结果必然是N状态。
    • 任何N状态,总有一种操作使其变化成P状态。从高位到低位考虑所有的二进制位。假设用了某种方法,改变了m堆,使i为之前的所有位都回归到k+1的整数倍。现在要证明总有一种方法让第i位也恢复到k+1的整数倍。
    • 有一个比较显然的性质,对于那些已经改变的m堆,当前位可以自由选择1或0.
    • 设除去已经更改的m堆,剩下堆i位上1的总和为sum
    • 分类讨论:
      1. sum<=k-m,此时可以将这些堆上的1全部拿掉,然后让那m堆得i位全部置成0.
      1. sum>k-m 此时我们在之前改变的m堆中选择k+1-sum堆,将他们的第i位设置成1。剩下的设置成0.由于k+1-sum<k+1-(k-m)<m+1,也就是说k+1-sum<=m,故这是可以达到的;
  • anti-nim反nim游戏

    • 正常的nim游戏是取走最后一颗的人获胜,而反nim游戏是取走最后一颗的人输。

    一个状态为必胜态,当且仅当:

    1. 所有堆的石子个数为1,且NIM_sum(xor和)=0
    2. 至少有一堆的石子个数大于1,且 NIM_sum(xor和)≠0

  • 新Nim游戏

    • 在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和Nim游戏一样。
    • 如果你先拿,怎样才能保证获胜?如果可以获胜的话,还要让第一回合拿的火柴总数尽量小。

    为使后手必败,先手留给后手的必然是若干线性无关的数字,否则后手可以留下一个异或和为零的非空子集使得先手必败,故问题转化为拿走和最小的数字使得留下的数线性无关,即留下和最大的线性基,这样拿走的数量显然最少,找到和最大的线性基只需贪心的把数字从大到小加入到基中即可(证明需用到拟阵)

    bzoj3105

    #include<cstdio>
    #include<algorithm>
    #define ll long long
    using namespace std;
    
    int num[1005],d[1005];
    
    bool cmp(int a,int b)
    {
       return a>b;
    }
    
    int Insert(int k)
    {
       for(int i=31;i>=0;i--)
        {
            if(k&(1<<i))
            {
                if(!d[i])
                {
                    d[i]=k;
                    return 1;
                }
                else
                    k^=d[i];
            }
        }
        return 0;
    }
    
    int main()
    {
        int k;ll m=0;
        scanf("%d",&k);
        for(int i=0; i<k; i++)
            scanf("%d",&num[i]);
        sort(num,num+k,cmp);
        for(int i=0; i<k; i++)
        {
            if(!Insert(num[i]))
                m+=num[i];
        }
        printf("%lld",m);
        return  0;
    }
    
  • Nim游戏求方案总数

    • 给定一个Nim状态,求该状态能够到达获胜状态的方案总数。
    • 若该状态为P状态,则Nim和为零,肯定方案总数为0
    • 若Nim和不为零,则表明该状态处于N状态,由于该位置是N位置,所以Nim和不为零,我们要求有多少总方案,改变其状态,使Nim和为零。

    • Nim和的求法为x1,x2,x3…xn的异或和,考察第一堆石头,设a=x1,b=(x2+x3+…+xn),那么:

    • Nim=a^b—————————1
    • 假设改变a即第一堆石头的数目之后,新的Nim和为0,即:
    • Nim’=a’ ^ b=0———————2
    • 由于改变了石头的数目,必有:
    • a’<a———————————3
    • 由方程1,2可以得到b=Nim ^ a = Nim’ ^ a’,又Nim’=0,故:
    • Nim ^ a= a’————————4
    • 将得到的方程4带入方程3,得到关系式:
    • Nim ^ a < a————————5
    • 也就是说,对于每一堆石头来说,只要满足关系式5,则就一定可以通过将这一堆的石头的数目改变从而使新的Nim和为0,也就是从N位置转移到P位置。统计共有多少堆石头满足关系式5,就有多少种转移的方案啦。

poj2975

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

int num[1005];

int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        ll m=0;int ans=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&num[i]);
            m^=num[i];
        }
        for(int i=0; i<n; i++)
        {
            if((num[i]^m)<num[i])
                ans++;
        }
        printf("%d\n",ans);
    }
    return  0;
}

2020 CCPC-Wannafly Winter Camp Day2 C

  • 如何将上一题O(n^2)降为O(nlogn)?当然是位运算啦!

  • 因为 y > x ^ y,所以y的最高位一定高于或等于x的最高位,否则x的最高位不变,不满足

  • 考虑异或和的最高的为 1 的二进制位,所有这一位是 1 的 y 显然都满足条件,这一位是 0 的都不满足条件。

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

int cnt[65];

int main()
{
    int n;
    scanf("%d",&n);
    ll a,b=0;
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&a);
        b^=a;
        ll x=a;
        int k=0;
        for(int j=0;x;j++)
        {
            cnt[j]+=x%2;
            x/=2;
        }
        ll sum=b;
        while(sum)
        {
            sum/=2;
            k++;
        }
        printf("%d\n",cnt[k-1]);
    }
    return  0;
}

博弈论入门之威佐夫博弈

  • 有两堆石子,两个顶尖聪明的人在玩游戏,每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子,不能取得人输,分析谁会获得胜利

  • 定义先手必输的局势为奇异局势,前几个奇异局势为 (0,0),(1,2),(3,5),(4,7),(6,10)…

  • 假设(x,y)为第k个奇异局势

  • 性质:

    1. x为前1…k个奇异局势中没有出现过的最小正整数,y=x+k
    1. 任何一个自热数都包含在一个且仅有一个奇异局势中
  • 证明有需要可以自寻,窝已经绕晕了QWQ

  • 人们通过对上述性质的探索,同时结合Betty定理,给出了威佐夫博弈的重要结论

  • 假设两堆石子为(x,y)(其中x<y)

  • 那么先手必败,当且仅当

  • (y−x)∗(√5+1)/2=x
  • 其中的(√5+1)/2实际就是1.618…,黄金分割数!

POJ1067

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;

int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        if(a>b) swap(a,b);
        int c=(b-a)*(sqrt(5.0)+1.0)/2.0;
        if(c==a) puts("0");
        else puts("1");
    }
    return  0;
}

51NOD 1185 威佐夫游戏 V2

  • 这题本来也是裸题,但是!

  • 可恶的出题人卡精度红红火火恍恍惚惚

  • 然后我尝试了一下python3交

  • python真香~

from decimal import *
from math import sqrt
t=int(input().strip())
for case in range(t):
    a, b = map(int, input().strip().split())
    p=Decimal((Decimal(5).sqrt()+1)/2)
    dif=abs(a-b)
    a=min(a,b)
    if a==int(p*dif):
        print("B")
    else:
        print("A")

小仙女