博弈论基础入门

时间:2022-09-07 23:20:41

博弈论入门

有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干,规定最后取光物体者取胜。这是我国民间很古老的一个游戏,别看这游戏极其简单,却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。

(一)巴什博奕(Bash Game)

定义:

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

首先分析子局面,当剩下m+1个时,无论先取者拿走多少个物品,后取者一定能一次取走所有物品,所以在剩下m+1个物品时,后取者一定能够获胜。

因此局面可分为两种情况:n=(m+1)r+s

  • 0< s <= m : 只要先取者取走s个石子。当后取者取走k个石子的时候,先取者只要取走m+1-k个石子即可。因此,先取者一定获胜
  • s=0 :类似上面的分析方法。先取者一定失败

例题HDU - 4764 Stone

题目大意:Tang和Jiang轮流写数字,Tang先写,每次写的数x满足1<=x<=k,Jiang每次写的数y满足1<=y-x<=k,谁先写到不小于n的数算输。

结论:r=(n-1)%(k+1),r=0时Jiang胜,否则Tang胜。原因在于对于取最后输的情况,可以考虑局面少了一子,然后在这种情况下先取完即赢,也就是说给对方剩下了一子。

代码:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

#define REP(i,n) for(int i=0;i<(n);i++)

int N,k;

int main(){
    while(~scanf("%d %d",&N,&k)){
        if(N==0&&k==0)  break;
        if((N-1)%(k+1)==0){
            printf("Jiang\n");
        }else{
            printf("Tang\n");
        }
    }
    return 0;
}

(二)威佐夫博奕(Wythoff Game)

定义

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

这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是: (0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。

可以看出这样一个规律,a0=b0=0,ak是前面未出现过的最小自然数,而bk = ak + k,奇异局势有如下性质:

  1. 任何自然数都包含在一个且仅有一个奇异局势中。由于ak是未在前面出现过的最小自然数,所以有ak > ak-1 ,而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。

  2. 任意操作都可将奇异局势变为非奇异局势。事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。

  3. 采用适当的方法,可以将非奇异局势变为奇异局势。

假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0);如果a = ak ,b > bk,那么,取走b - bk个物体,即变为奇异局势;如果 a = ak , b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局势( ab - ak , ab - ak+ b - ak);如果a > ak ,b= ak + k,则从第一堆中拿走多余的数量a - ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k),从第二堆里面拿走 b - bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b - aj 即可。

从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。 那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式: ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...,n 方括号表示取整函数) 奇妙的是其中出现了黄金分割数(1+√5)/2 = 1。618...,因此,由ak,bk组成的矩形近似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若 a=[j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1+ j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异局势。

例题HDU - 1527 取石子游戏

代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

#define REP(i,n) for(int i=0;i<(n);i++)

int N,M;

int main(){
    while(~scanf("%d %d",&N,&M)){
        int a = min(N,M);
        int b = max(N,M);
        double k = b-a;
        int fir = k*(1+sqrt(5))/2;
        if(fir==a){
            printf("0\n");
        }else{
            printf("1\n");
        }
    }
    return 0;
}

(三)尼姆博弈(Nimm Game)

定义

有三堆各若干个物品,两个人轮流从某一堆取任意多的 物品,规定每次至少取一个,多者不限,最后取光者得胜。

从取石子游戏(Bash Game)到多堆的尼姆博弈是一个大进步,尼姆博弈的就是把取石子中的 1 堆变成了多堆。游戏者轮流从某一堆棋子中取走一个或者多个(这里暂时不限定每次最多能取几个),最后不能再取的就是输家。当指定相应数量时,一堆这样的棋子称作一个尼姆堆。

这里假定是 3 堆。
其实现在这个问题的一部分解决了——任意多堆的相同个数的 Nim 堆。而且很容易知道,(0,N,N)一定是必败态,如果有仔细尝试的话,可以发现(1,2,3)也是必败态,那到底有什么规律呢?

命题:(a,b,c) 是必败态等价于 p(a, b, c) = a xor b xor c = 0 ( xor 是异或运算)
如果我们面对的是一个非奇异局势 (a,b,c),要如何变为奇异局势呢?假设 a < b< c,我们只要将 c 变为 a xor b,即可,因为有如下的运算结果: 要将 c 变为 a xor b,只要从 c 中减去 c - (a xor b)即可。

推广到多个堆也是类似的办法。

例题HDU - 1907 John

题意

标准Nim博弈,只是最后取光者输。

思路

除了判断异或和性质以外,还要判断如果堆的石子个数全为1时的情况,所以有两个条件。实际上对于博弈局面来讲,先取胜利或先取失败的主要原因相差多半与1个石子相关。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

const int MAXN = 50;
int A[MAXN];

int main(){
    int T=0,N=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        int flag = 1;
        for(int i=0;i<N;i++){
            scanf("%d",&A[i]);
        }
        for(int i=0;i<N;i++){
            if(A[i]!=1) flag = 0;
        }
        int sav =0;
        for(int i=0;i<N;i++){
            sav^=A[i];
        }
        if(flag==1){
            if(N%2==0){
                printf("John\n");
            }else{
                printf("Brother\n");
            }
        }else{
            if(sav==0){
                printf("Brother\n");
            }else{
                printf("John\n");
            }
        }
    }
    
    return 0;
}