启示

博弈是一个熟悉而又陌生的词汇，我一直没有去深入思考过关于博弈的本质及其原理。最近ACMer的训练，我选择了专攻博弈方向，看了很多博文，查了很多资料，想了很长时间，终于推理出了一套“王氏”博弈理论。

思考

三种经典博弈

懒得写了。
TIPS: 第二种威佐夫博弈有一个神奇的推理公式
若(a,b)是必败态，满足 a < b && a == (int) (b - 1)*(sqrt(5)+1)/2
那坨常数还等价于

1+黄金分割率

POJ 1067 算法验证题

其它游戏

其实，我们可以把一个游戏所有状态标号，形成一个有向图。从游戏的初始状态作为root，最终的输赢状态作为叶节点，这就神奇地把博弈变成了图论的题目了……先手的肯定想走过奇数条边到达胜利的叶节点，后手也是这么想的，然后在双方都不能满足胜利的条件时，都会退而求其次努力去完成和局的条件。差不过所有的博弈都是这么回事。

思路

Gurndy

这个又有人称作sg值，它记录的是，当前状态所能推出所有的子状态的值中，没出现过的最小自然数。
这个函数非常有用，他就实现了我刚才把博弈变成一张图的过程，并且给每个节点都标上了一定的唯一的sg值。

代码实现

我实现取石子游戏的写法，其它博弈根据题意自己推了，类似于DP，能意会，不可言传。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//模拟取石子的游戏
const int NX=100;
int sg[NX];
int move[NX];//游戏规则的，每一步可以移动的步数
int origin;//初始状态
void grundy(){
	sg[0]=0;
	//遍历所有状态
	for(int i=1;i<=origin;i++){
		set <int > st;
		for(int j=0;j<NX;j++){
			//当前可移动且不会走出游戏边界
			if(move[j] < i){
				st.insert(i-move[j]);
			}
		}
		int cnt=0;//记录之状态中未出现的最小自然数
		while(st.count(cnt) != 0)cnt++;
		sg[i] = cnt;
	}
}

练习

POJ博弈水题
POJ 2311
AC代码

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
28
29
30
31
32
33
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
int sg[205][205];
int grundy(int n,int m){
	if(sg[n][m]!=-1)return sg[n][m];
	set<int> st;
	for(int i=2;n-i>=2;i++) st.insert(grundy(n-i,m)^grundy(i,m));
	for(int j=2;m-j>=2;j++) st.insert(grundy(n,m-j)^grundy(n,j));
	int cnt=0;
	while(st.count(cnt))cnt++;
	return sg[n][m]=sg[m][n]=cnt;
}
void init(){
	for(int i=0;i<205;i++)
		for(int j=0;j<205;j++){
			sg[i][j]=-1;
		}
	//grundy(202,202);如果这样写的话回t，在这题里，还是测试一组跑一组比较快……
}
int main(){
	init();
	int w,h;
	while(~scanf("%d%d",&w,&h)){
		if(grundy(w,h)!=0)puts("WIN");
		else puts("LOSE");
	}return 0;
}

POJ 1704

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
28
29
30
31
32
#include <iostream>  
#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f  
const int MAXN=100005;
int main(){
    long long t;cin>>t;
    while(t--){
      bool stan=1;
      int n,i=1,ans=0;int tt[1005];
      cin>>n;
      for(i=1;i<=n;i++){
        scanf("%d",tt+i);
      }
      sort(tt+1,tt+n+1);
      i=1;
      if(n&1){
        i=2;
        ans=ans^(tt[1]-1);
      }
      for(;i+1<=n;i+=2){
        ans=ans^(tt[i+1]-tt[i]-1);
      }
      //cout<<"ans= "<<ans<<endl;
      if(!ans)puts("Bob will win");
      else puts("Georgia will win");
    }
    return 0;
}

POJ 2348

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 <iostream>  
#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f  
const int MAXN=100005;
int main(){
    long long a,b;
    while(cin>>a>>b){
      if(a==0&&b==0)break;
      bool stan=1;
      if(a!=0&&b!=0){
          while(1){
            if(a<b)swap(a,b);
            if(a%b==0)break;
            if(a>2*b)break;
            stan=!stan;
            a-=b;
          }
      }
      if(stan)puts("Stan wins");
      else puts("Ollie wins");
    }
    return 0;
}