博弈论之威佐夫博弈 算法学习

(Updated: )
oi
, ,

博弈论之威佐夫博弈

威佐夫博弈（Wythoff’s game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
——转自百度百科

就比如洛谷的P2252 取石子游戏就是威佐夫博弈的裸题。。。

威佐夫博弈的性质

首先，由题目可知，当这两堆石子一样多时，先手获胜；当有一堆石子为空时，先手获胜。 现，我们设$(a[i],b[i])$表示先手必败的局势，其中$a[i],b[i]$分别表示两堆石子的个数。我们又称这种局势为奇异局势。 那么，我们就可以推出一些较小的数据的必败局势（奇异局势）： 假如说这两堆石子的初始状态为(1,2)。那么则有如下几种情况： (1)先手从第一堆中取一个，后手从第二堆中取两个，先手输，后手赢。 (2)先手从第二堆中取一个，后手将两堆都取一个，先手输，后手赢。 (3)先手从第二堆中取两个，后手从第一堆中取一个，先手输，后手赢。 (4)先手从两堆中各取一个，后手从第二堆中取一个，先手输，后手赢。 通过推理石子状态为(1,2)的所有可能，我们可以发现石子状态为(1,2)时，先手必输(双方都采用最优策略)。 在此，我就不列举其他奇异局势的推理过程。现将奇异局势的表单贴下来：

个数

状态

1

(0,0)

2

(1,2)

3

(3,5)

4

(4,7)

5

(6,10)

6

(8,13)

7

(9,15)

8

(11,18)

9

(12,20)

威佐夫博弈的结论

仔细观察上表，可以得出以下几个规律。 (1)状态是单调递增的（废话） (2)状态的石子数量的差是个等差数列（公差为1），这个序列为：0,1,2,3,4,5，6,7,8,9,10,11…… (3)状态的第一个数字是之前没有出现过的第一个数字。比如说第二个状态的第一个数字1，就是前几个状态没有出现的数字。 (4)每个状态的第一个数字竟然是这个状态的两堆石子数量的差$*1.618$

关于$1.618$

$1.618$是一个非常神奇的数字，它既是黄金分割率的近似值+1，即$0.618+1$，也是$(\sqrt{5}+1)/2$，即$(\sqrt{5}+1)/2 \approx 1.618$。 有图为证：

——转自百度百科 但是为什么众多OIer在打威佐夫博弈时不直接使用1.618呢，因为C++/Pascal有一个奇妙的东西——精度

解决洛谷的P2252 取石子游戏

这道题就是裸的威佐夫博弈啊。。。 不多说了，上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(){
    a=read();b=read();
    if(a==b){                     //特判，如果两堆石子相等，那么先手直接从两堆取同样多的石子，先手赢，后手输
        puts("1");
        return 0;
    }
    if(a==0b==0){               //特判，如果两堆中有一堆没有石子，那么先手取一堆石子，先手赢，后手输
        puts("1");
        return 0;
    }
    int x=min(a,b),y=max(a,b);    //x,y取最小值和最大值，也就是让两堆石子有序
    double r=(sqrt(5.0)+1.0)/2.0; //根据上述(4)规律
    double c=(double)(y-x);       //根据上述(2)规律
    int tmp=r*c;                  //根据上述(4)规律
    if(tmp==x) puts("0");         //如果计算结果（利用上述规律）刚好等于第一堆石子数量（符合上述规律）那么就一定是奇异局势（先手必败）
    else puts("1");               //不是奇异局势，那么先手一定有可能获胜
    return 0;
}

是不是感觉有点乱。。。QWQ 简洁的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
int a,b;
int main(){
    a=read();b=read();
    if(a==b){
        puts("1");
        return 0;
    }
    if(a==0b==0){
        puts("1");
        return 0;
    }
    int x=min(a,b),y=max(a,b);
    double r=(sqrt(5.0)+1.0)/2.0;
    double c=(double)(y-x);
    int tmp=r*c;
    if(tmp==x) puts("0");
    else puts("1");
    return 0;
}