博弈论的翻译是Game…研究各种游戏模型的必败/必胜策略。
证明多为数学归纳法yy,这里只记结论╮(╯▽╰)╭

Bash Game

n个棋子,每次最多取m个,最少取1个,到最后不能取的人失败。

n%(m+1)==0 则先手必败,否则先手必胜
因为无论先手怎么拿,后手总可以让其变成n%(m+1)==0的状态,最后n=m+1时必败

Fibonacci博弈

n个棋子(n > 1),第一次取任意个,但不能取完
以后每次取的个数至多为上一次取的两倍

当石头数目为Fibonacci数时,先手必败

  • Zeckendorf 定理: 任何正整数可以表示为若干个不连续的Fibonacci数之和
  • $fib_{k+1} < 2fib_{k}$
  • 证明

Wythoff Game

2堆棋子,每次从一堆或两堆取相同数目,最后不能取的人失败。
奇异局势先手必败,否则先手必胜
第k个奇异局势(必败态)为(a[k],b[k])
判断(a[k],b[k])是否为奇异局势:
$$\begin{align}
&a_k = [\frac{k(1+\sqrt{5})}{2}] & k \in N \\
&b_k = a_k + k & k \in N
\end{align}
$$

根据$a_k$算出k,然后再根据第二个式子判断。

题目

poj1067

裸的威佐夫博奕

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
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;


int main()
{
int a,b,k;
while(scanf("%d %d",&a,&b)==2)
{
if(a>b) swap(a,b);
k = ((a*2)/(1+sqrt(5)) + 0.5);
if(floor(k*(1+sqrt(5))/2) == a)
{
puts(a+k == b?"0":"1");
continue;
}
else ++k;
if(floor(k*(1+sqrt(5))/2) == a) puts(a+k == b?"0":"1");
else puts("1");
}
return 0;
}

SG函数/定理

我们这样定义SG游戏:

  • 游戏两人参与,轮流做出决策。且默认为对自己最有利的决策。
  • 当有一人无法做出决策时游戏结束,无法做出决策的人输。
  • 游戏可以在有限步内结束,同一状态不可能多次抵达。
  • 游戏不会出现平局。
  • 任意一个游戏者在某一状态做出的决策集合只与当前状态有关,与游戏者无关。

SG函数

对于任意状态$x$,
$$SG(x)=mex(S)$$
S是x后继状态的集合,$mex(S)$表示不在S内的最小非负整数(自然数)
$SG(x) = 0$表示当前局面必败,否则必胜。

SG函数满足如下性质

  • 对于任意局面x,若$SG(x) = 0$,那么它的任何一个后继局面的SG都不为0;
  • 对于任意局面x,若$SG(x) \neq 0$,那么它一定有一个一个后继局面的SG为0;

或者我们换种理解

  • 对于必败状态,所有后继状态都是必胜的
  • 对于必胜状态,至少有一个后继状态是必败的

SG定理

总游戏SG函数的值等于所有子游戏的SG函数值的异或和

Nim Game

nim游戏规则如下:

  • 桌子上有N堆石子,游戏者轮流取石子
  • 每次从一堆中取出任意数目的石子,但不能不取
  • 取走最后一个石子者获胜

对于每堆$SG(x)=x$,然后应用SG定理
先手必胜当且仅当
$$ \sum SG(x_i) \neq 0 $$

Anti-nim

Anti-nim游戏规则只有最后一点与nim不同:

  • 取走最后一个石子着败

即获胜条件与nim恰好相反

先手必胜当且仅当:

  • 所有堆的石子数目都为1,且$\sum SG = 0$
  • 至少有一堆石子数目大于1,且$\sum SG \neq 0$

SJ定理

J代表参考论文作者的姓名(Jia),是他自己提出的一个定理…

我们可以将Anti-nim推广到任意SG游戏即Anti-SG游戏。
先手必胜当且仅当:

  • $\sum SG \neq 0$,且存在单一游戏SG函数大于1
  • $\sum SG = 0$,且没有单一游戏SG函数大于1

Multi-SG

Multi-SG游戏规则如下:

  • 在符合拓扑原则的前提下,一个单一游戏的后继可以为多个单一游戏。
  • 其余规则与SG游戏相同

即可以将一堆石子分成多堆。
我们仍然可以用SG函数定义局面。

Every-SG

Every-SG游戏规则如下:

  • 对于没有结束的单一游戏,游戏者必须对该游戏进行一步决策
  • 其余规则与SG游戏相同

我们考虑让我们必胜的游戏尽可能长地玩下去!
通过拓扑关系计算某一状态的SG函数时候,
对于SG为0的点,我们需要知道最快几步进入终止状态。
对于SG不为0的点,我们需要直到最慢几步进入终止状态。
设当前状态为u,后继状态为v,定义函数step(u)为到终止状态的步数

$$
step(u) =
\begin{cases}
0 &u 为终止状态 \\
max(step(v))+1 & SG(u)>0 且 SG(v)=0 \\
min(step(v))+1 & SG(u)=0
\end{cases}
$$

则先手必胜当且仅当:

  • 单一游戏中最大的step为奇数

Staircase Nim

阶梯博弈规则如下:

  • 从左至右有若干堆石子 (第0堆没有石子
  • 每次可以从当前堆取若干石子移动到前面一堆上
  • 最后不能移动者败

先手必胜当且仅当:

  • 阶梯的所有奇数位置的SG和不为0

因为如果棋子从奇数位拿到了偶数位,相当于将这些棋子移走。
从偶数位置移到奇数位,必胜者可以将这些棋子移到下一个偶数位。

poi2009 Pebbles(bzoj1115)

好吧,bzoj的权限题,交不了…千辛万苦才找到原始连接。
题目意思是有n堆石子,每次可以从一堆移走若干个,但每堆数目要保持从左至右不降,最后不能取的人败
我们对相邻两堆石子进行差分,令b[i] = a[i] - a[i-1];
那么从第i堆移走k个石子即 b[i] -= k,b[i+1] += k;
这样就成了倒着的阶梯nim模型,对奇数堆的b[i]求异或和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>

const int maxn = 1010;
int save[maxn];

int main()
{
int T,n,x;
//freopen("test.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans = 0;
for(int i=1;i<=n;++i) scanf("%d",save+i);
for(int i=n;i>1;i-=2) ans ^= (save[i] - save[i-1]);
if(n&1) ans ^= save[1];
puts(ans?"TAK":"NIE");
}
return 0;
}

poj1704

嗯,我们将每个棋子视为一堆,他们默认满足递增关系。
然后就可以用上面的方法咯。将相邻两个的差值视为一堆。

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<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 1010;
int save[maxn];

int main()
{
int T,n;
//freopen("test.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans = 0;
for(int i=0;i<n;++i)
{
scanf("%d",save+i);
}
if(n&1) save[n++] = 0;
sort(save,save+n);
for(int i=1;i<n;i+=2)
{
ans ^= (save[i] - save[i-1] - 1);
}
printf("%s will win\n",ans?"Georgia":"Bob");
}
return 0;
}

其它游戏

翻硬币游戏

翻硬币游戏规则如下:

  • N枚硬币排成一排,编号为1-N。
  • 一枚硬币有正反两种状态,翻一次改变一次。
  • 游戏者根据某些约束翻硬币(如:每次只能翻一或两枚,或者只能翻连续几枚),但是他所翻动的硬币中,最右边只能从正面翻到反面。
  • 谁不能翻谁输

定理:

  • 局面的SG值为局面中每个正面朝上的棋子单一存在时候的SG值的异或和
    如图
    我们理解为位,正面为1,反面为0
    上面的等式即为 SG(011001) = SG(01) ^ SG(001) ^ SG(000001)

  • 一排硬币,每次选择一个正面的硬币,把它以及其右边的硬币翻转,先把硬币都翻转到反面,的赢: 当且仅当最右边为1,先手必胜。

树的删边游戏

规则如下:

  • 给出一颗N个结点的树,其中一个点为树的根节点
  • 轮流删边,删去一条边后,不与根节点相连的部分被移去
  • 无路可走者败

定理:

  • 叶子结点SG值为0; 中间结点SG值为所有子节点 (SG值+1) 的异或和

无向图删边游戏

规则如下:

  • 给定一个无向联通图,取一个点作为图的根。
  • 轮流删边,删去一条边后,不与根节点相连的部分被移去
  • 无路可走者败

我们可以对无向图做如下改动:
将图中的任意一个偶环缩成一个新点,任意一个奇环缩成一个新点加一个新边;
所有连到原先环上的边全部改为与新点相连。
这样的改动不会影响图的 SG 值,无向图的删边游戏就成了树的删边游戏。

poj3710

PN图

P表示必败位置,N表示必胜位置。
通常通过pn图找规律。。。

这是Wythoff Game的PN图
Wythoff Game

sg搜索

题目

poj3537

著名的画X游戏,这里是一维的
我们知道_XX,XX_,X_X,这样的状态是必败的。
所以我们每画一个X,这个X左边两个到右边两个范围内就不能再画了,游戏被分为 i-3 和 n-i-2 两个阶段

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
34
#include<cstdio>
#include<cstring>

const int maxn = 2010;
int sg[maxn];

int dfs(int n)
{
if(n<=0) return 0;
int &ans = sg[n];
if(ans!=-1) return ans;

bool vis[maxn];
memset(vis,0,sizeof vis);

for(int i=1;i<=n/2 + 1;++i)
{
vis[dfs(i-3)^dfs(n-i-2)] = 1;
}
for(int j=0;;++j)
if(!vis[j]) return sg[n] = j;
}

int main()
{
//freopen("test.txt","r",stdin);
int n;
memset(sg,-1,sizeof sg);
while(scanf("%d",&n)==1)
{
puts(dfs(n)?"1":"2");
}
return 0;
}

poj1082

直接应用sg函数,注意日期的处理。

对抗搜索

又称极大极小搜索,是一种在博弈树上的搜索

参考