博弈论
一、内容简介
本文主要介绍算法竞赛中常常出现的博弈论模型,包括:
- 4个经典组合游戏
- SG函数
- SG游戏及拓展
二、前置概念
进一步学习需要了解一些前置概念
- ICG
- 博弈图
- P点、N点
- mex函数
1.ICG
ICG全称为“公平组合游戏”,我们下面讨论的博弈游戏均建立在ICG的基础上,那么什么是ICG呢,它需要满足以下条件:
- 由两名玩家交替行动
- 对任意局面,接下来可执行的行动仅与局面有关(玩家平等)
- 游戏以玩家无法行动为结束,且无平局
那么称此游戏为“
公平组合游戏
”
2.博弈图
我们可以看到,整个过程是各个状态的集合,且状态间可以到达,那么我们可以将这个博弈过程抽象为一张图,称为
博弈图
,这个游戏我们也称之为
有向图游戏
那么这个图是一个有向无环图,图中有
唯一的起点
,可能有多个终点,两名玩家的交替行动可认为是图上的有向边,所有出度为0的节点便是终点
对于这个图,每个节点存储如下信息:{弈盘信息x,先手信息p,…}等
同时有如下结论:
任何一个公平组合游戏均可以转化为有向图游戏
3.P点、N点
P点和N点是博弈里面两个及其重要的概念
-
先手必胜状态
:先手行动后,可以将一个必败状态留给后手 -
先手必败状态
:先手无论如何行动,只能将必胜状态留给后手 -
必败点(P点)
:前一个选手取胜,当前选手将败的节点(previous) -
必胜点(N点)
:下一个选手将败,当前选手取胜的节点(next)
4.mex函数
mex函数是一个建立在集合上的整数函数,即
m
e
x
:
S
N
↦
N
mex: S_N \mapsto N
m
e
x
:
S
N
↦
N
,它的定义域是一个非负整数集,
m
e
x
mex
m
e
x
代表这个集合里最小未出现的非负整数,举几个例子:
m
e
x
(
{
1
,
2
,
3
}
)
=
0
mex(\{1,2,3\})=0
m
e
x
(
{
1
,
2
,
3
}
)
=
0
,
m
e
x
(
{
0
,
1
,
2
}
)
=
3
mex(\{0,1,2\})=3
m
e
x
(
{
0
,
1
,
2
}
)
=
3
,
m
e
x
(
{
0
,
2
,
3
}
)
=
1
mex(\{0,2,3\})=1
m
e
x
(
{
0
,
2
,
3
}
)
=
1
,等等
三、前置定理
定理一:没有后继状态的状态是必败状态
定理二:一个状态是必胜状态
⇔
\Harr
⇔
它至少存在一个向必败状态的转移
定理三:一个状态是必败状态
⇔
\Harr
⇔
它所有后继状态均为必胜状态
四、四大经典组合游戏
1.Nim游戏
给定
NN
N
堆物品,第
ii
i
堆物品有
Ai
A_i
A
i
个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。
取走最后一件物品者获胜。
问先手是否必胜。
Nim博弈是最经典的博弈之一,许多博弈均可转化为Nim博弈,我们给出结论:
先手必胜
⇔
\Harr
⇔
A
1
⊕
A
2
⊕
A
3
.
.
.
⊕
A
n
≠
0
A_1\oplus A_2\oplus A_3…\oplus A_n\ne0
A
1
⊕
A
2
⊕
A
3
.
.
.
⊕
A
n
=
0
由归纳法其实很容易证得,也可以利用三个前置定理进行证明,但这个等价表达式还是给予我们很多震撼~~(也给予出题人很多灵感)~~
但其实我们不应把Nim游戏看成一个独立游戏,而应该把它看成若干个
游戏的和
对每个游戏,
先手是否必胜
⇔
\Harr
⇔
A
i
≠
0
A_i\ne0
A
i
=
0
进而对于这
n
n
n
个游戏的加和为
A
1
⊕
A
2
⊕
A
3
.
.
.
⊕
A
n
A_1\oplus A_2\oplus A_3…\oplus A_n
A
1
⊕
A
2
⊕
A
3
.
.
.
⊕
A
n
游戏和的概念后续还会继续用到,也是用异或的形式给出表达式,这个表达式很重要
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) scanf("%d", &x), ans ^= x;
puts("%s", ans ? "Yes" : "No");
return 0;
}
2.Bash游戏
有 1 堆石子,总个数是
nn
n
。两名玩家轮流在石子堆中拿石子,每次至少取 1 个,至多取
mm
m
个。取走最后一个石子的玩家为胜者。
判定先手和后手谁胜。
给出结论:
先手必胜
⇔
\Harr
⇔
(
m
+
1
)
∤
n
(m+1)\nmid n
(
m
+
1
)
∤
n
考虑三种情形 :
情形一:
n
≤
m
n \le m
n
≤
m
时,显然先手必胜
情形二:
n
=
m
+
1
n=m+1
n
=
m
+
1
时,先手最多拿m个,但无论先手取走几个,后手一定可以拿完,后手胜
情形三:
(
m
+
1
)
∣
n
(m+1)\mid n
(
m
+
1
)
∣
n
时,假设先手每次拿
x
x
x
个,后手可以拿
m
+
1
−
x
m+1-x
m
+
1
−
x
个,最后后手胜
其余情形,先手均可以通过拿走
n
%
(
m
+
1
)
n \% (m+1)
n
%
(
m
+
1
)
个,进而转至情形三,先手胜
int main() {
scanf("%d%d", &n, &m);
puts("%s", n%(m+1) ? "First Win" : "Second Win");
return 0;
}
3.Wythoff游戏
有两堆石子,石子数可以不同。
两人轮流取石子,每次可以在一堆中取,或者从两堆中取走相同个数的石子,数量不限.
取走最后一个石头的人获胜。
判定先手是否必胜。
这个游戏的结论比较复杂,涉及到了平面上的点集,下图便是先手必败节点,
(
x
,
y
)
(x,y)
(
x
,
y
)
代表两堆石子个数
上面这张图粉色区域即为解集,解集是关于
y
=
x
y=x
y
=
x
对称,靠前的解有:
(
0
,
0
)
,
(
1
,
2
)
,
(
3
,
5
)
,
(
4
,
7
)
,
(
6
,
10
)
,
(
8
,
13
)
,
(
9
,
15
)
,
(
11
,
18
)
,
(
12
,
20
)
,
(
13
,
21
)
.
.
.
(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), (11,18), (12,20), (13,21)…
(
0
,
0
)
,
(
1
,
2
)
,
(
3
,
5
)
,
(
4
,
7
)
,
(
6
,
1
0
)
,
(
8
,
1
3
)
,
(
9
,
1
5
)
,
(
1
1
,
1
8
)
,
(
1
2
,
2
0
)
,
(
1
3
,
2
1
)
.
.
.
等
解集
(
a
k
,
b
k
)
(a_k,b_k)
(
a
k
,
b
k
)
满足 :
a
k
a_k
a
k
是之前未出现的最小自然数,
b
k
=
a
k
+
k
b_k=a_k+k
b
k
=
a
k
+
k
这个可以利用题目的性质进行归纳证明,主要利用了如下性质:
-
若
(x
,
y
)
∈
A
n
s
(x,y) \in Ans
(
x
,
y
)
∈
A
n
s
,那么
∀t
∈
N
,
(
x
+
t
,
y
)
∉
A
n
s
,
(
x
,
y
+
t
)
∉
A
n
s
,
(
x
+
t
,
y
+
t
)
∉
A
n
s
\forall t\in \N,(x+t,y)\notin Ans ,(x,y+t)\notin Ans,(x+t,y+t)\notin Ans
∀
t
∈
N
,
(
x
+
t
,
y
)
∈
/
A
n
s
,
(
x
,
y
+
t
)
∈
/
A
n
s
,
(
x
+
t
,
y
+
t
)
∈
/
A
n
s
我们称符合要求的解为奇异节点,奇异节点便是先手必败节点,而非奇异节点显然可以通过一步操作变成奇异节点,通过归纳法也可以证明奇异节点坐标正确性
按照解的定义,我们发现实际上集合
A
=
{
a
k
∣
k
∈
N
}
A=\{a_k|k\in \N\}
A
=
{
a
k
∣
k
∈
N
}
和
B
=
{
b
k
∣
k
∈
N
}
B=\{b_k|k\in \N\}
B
=
{
b
k
∣
k
∈
N
}
实际上是对整数区间的一个划分,即
A
∩
B
=
∅
,
A
∪
B
=
N
+
A\cap B=\varnothing,A\cup B=\N^+
A
∩
B
=
∅
,
A
∪
B
=
N
+
,考虑引入
Beatty定理
:
如果两个无理数
α,
β
\alpha,\beta
α
,
β
满足:
1α
+
1
β
=
1
\frac{1}{\alpha}+\frac{1}{\beta}=1
α
1
+
β
1
=
1
考虑两个正整数集
A,
B
A,B
A
,
B
:
A=
{
⌊
n
α
⌋
}
,
B
=
{
⌊
n
β
⌋
}
A=\{\lfloor n\alpha \rfloor\},B=\{\lfloor n\beta \rfloor\}
A
=
{
⌊
n
α
⌋
}
,
B
=
{
⌊
n
β
⌋
}
(1
)
(1)
(
1
)
以及两个结论:
A∩
B
=
∅
,
A
∪
B
=
N
+
A\cap B=\varnothing,A\cup B=\N^+
A
∩
B
=
∅
,
A
∪
B
=
N
+
(2
)
(2)
(
2
)
那么我们断言:
(1
)
⇔
(
2
)
(1)\Harr(2)
(
1
)
⇔
(
2
)
,可利用取整函数的上下界进行证明
将
Beatty定理
代入我们的解集,利用
β
=
α
+
1
\beta = \alpha +1
β
=
α
+
1
解出:
α
=
5
+
1
2
,
β
=
3
−
5
2
\alpha = \frac{\sqrt{5}+1}{2} ,\beta=\frac{3-\sqrt{5}}{2}
α
=
2
5
+
1
,
β
=
2
3
−
5
假设两堆石子为
(
a
k
,
b
k
)
,
a
k
<
b
k
(a_k,b_k),a_k \lt b_k
(
a
k
,
b
k
)
,
a
k
<
b
k
,那么
先手必败
⇔
\Harr
⇔
(
b
k
−
a
k
)
×
α
=
k
α
=
a
k
(b_k-a_k)\times \alpha =k \alpha = a_k
(
b
k
−
a
k
)
×
α
=
k
α
=
a
k
int main() {
scanf("%d%d", &n, &m);
if (a > b) swap(a, b);
int ans = (b - a) * ((1.0 + sqrt(5.0)) / 2.0);
puts("%s", ans==a ? "Second Success" : "First Success");
return 0;
}
4.Fibonacci游戏
有 1 堆石子,总个数是
nn
n
(n
≥
2
)
(n\ge 2)
(
n
≥
2
)
。游戏双方轮流取石子,规则如下:
先手不能在第一次把所有的石子取完,至少取 1 颗;
之后每次可以取的石子数至少为 1 ,至多为对手刚取的石子数的 2 倍。
取走最后一个石子的人为赢家,求必败态。
结论:
先手必败
⇔
\Harr
⇔
石子数为斐波那契数
必要性可由归纳法简要证出,充分性建立在
Zeckendorf定理
:
任何正整数均可以表示为若干个不连续的 Fibonacci 数之和
进而先手可以将石子划分成多堆不连续的斐波那契数的加和,先手先取走最小堆,然后可以通过操作,让后手来面临这些斐波那契堆,且每次后手不能取完,而先手可以取完,最后先手取完最后的石子,先手胜
int f[N], x;
map<int,bool>mp;
int main(){
fib[1] = 1, fib[2] = 1;
for(int i = 3;i <= 50; ++ i) f[i] = f[i-1] + f[i-2], mp[f[i]] = 1;
while(scanf("%d", &x) && x != 0)
puts(mp[x] == 1 ? "Second win" : "First win");
return 0;
}
五、SG函数
1.SG函数
SG函数是对博弈图中每一个节点或者说状态的评估函数,
S
G
:
s
t
a
t
e
↦
N
SG: state \mapsto N
S
G
:
s
t
a
t
e
↦
N
规定游戏终点的 SG 函数值为 0 ,即
S
G
(
e
n
d
)
=
0
SG(end)=0
S
G
(
e
n
d
)
=
0
,同时扩展规定一个游戏图的 SG 值为起点的 SG 值,即
S
G
(
G
r
a
p
h
)
=
S
G
(
s
t
a
r
t
)
SG(Graph)=SG(start)
S
G
(
G
r
a
p
h
)
=
S
G
(
s
t
a
r
t
)
在有向图游戏中,对每个节点
xx
x
,设从
xx
x
出发有
kk
k
个状态转移,分别到达节点
y1
,
y
2
,
.
.
.
,
y
k
y_1,y_2,…,y_k
y
1
,
y
2
,
.
.
.
,
y
k
,那么定义
SG
(
x
)
SG(x)
S
G
(
x
)
为
xx
x
的后继节点的
SG
SG
S
G
值集合取
me
x
mex
m
e
x
即:
SG
(
x
)
=
m
e
x
(
{
S
G
(
y
1
)
,
S
G
(
y
2
)
,
.
.
.
,
S
G
(
y
k
)
}
)
SG(x) = mex(\{SG(y_1),SG(y_2),…,SG(y_k)\})
S
G
(
x
)
=
m
e
x
(
{
S
G
(
y
1
)
,
S
G
(
y
2
)
,
.
.
.
,
S
G
(
y
k
)
}
)
那么由前置定理,推出以下结论:
-
若
SG
(
x
)
=
0
SG(x)=0
S
G
(
x
)
=
0
,则为必败状态 -
若
SG
(
x
)
≠
0
SG(x)\not=0
S
G
(
x
)
=
0
,则为必胜状态
2.SG定理
SG 定理 :
对于游戏
XX
X
,它可以拆分成若干个子游戏
x1
,
x
2
,
.
.
.
,
x
n
x_1,x_2,…,x_n
x
1
,
x
2
,
.
.
.
,
x
n
,
X=
⋃
i
=
1
n
x
i
X = \bigcup_{i=1}^{n}x_i
X
=
⋃
i
=
1
n
x
i
那么,
SG
(
X
)
=
⊕
i
=
1
n
S
G
(
x
i
)
=
S
G
(
x
1
)
⊕
S
G
(
x
2
)
⊕
.
.
.
⊕
S
G
(
x
n
)
SG(X)=\oplus_{i=1}^{n}SG(x_i)=SG(x_1)\oplus SG(x_2)\oplus…\oplus SG(x_n)
S
G
(
X
)
=
⊕
i
=
1
n
S
G
(
x
i
)
=
S
G
(
x
1
)
⊕
S
G
(
x
2
)
⊕
.
.
.
⊕
S
G
(
x
n
)
换句话说,对于由
n
n
n
个有向图组成的组合游戏,设它们的起点为
s
1
,
s
2
,
.
.
.
,
s
n
s_1,s_2,…,s_n
s
1
,
s
2
,
.
.
.
,
s
n
当且仅当
S
G
(
s
1
)
⊕
S
G
(
s
2
)
⊕
.
.
.
⊕
S
G
(
s
n
)
≠
0
SG(s_1)\oplus SG(s_2)\oplus…\oplus SG(s_n) \not=0
S
G
(
s
1
)
⊕
S
G
(
s
2
)
⊕
.
.
.
⊕
S
G
(
s
n
)
=
0
时,这个游戏为先手必胜
证明方法与 Nim 游戏的证明类似
事实上,每一个简单
SG-组合游戏
都可以完全等效成一堆数目为
K
K
K
的石子,其中
K
K
K
为该简单游戏的 SG函数值。
定义
游戏的和
:考虑任意多个同时进行的 SG-组合游戏,这些 SG-组合
游戏的和
是这样一个SG-组合游戏:在它进行的过程中,游戏者可以任意挑选其中的一个
单一游戏
进行决策,最终,没有办法进行决策的人输。
易见,SG定理是对 游戏的和的SG值 和 单一游戏的SG值 间关系的一座桥梁,揭示了两者间的关系
3.简单应用
#include <unordered_set> // AcWing 893
int n, m, x, res;
int a[N], s[N], ans[M];
int sg(int x){//记忆化搜索
if(ans[x] != -1) return ans[x];
unordered_set<int>St;
for(int i = 1; i <= m; i++) if(x >= s[i]) St.insert(sg(x - s[i]));
for(int i = 0; ; i++) if(!St.count(i)) return ans[x] = i; // 求 mex
}
int main(){
scanf("%d", &m);
for(int i = 1; i <= m; i++) scanf("%d", &s[i]);// m 个起点
scanf("%d", &n);
memset(ans, -1, sizeof ans);
for(int i = 1; i <= n; i++) scanf("%d", &x), res ^= sg(x);
puts("%s", res ? "Yes" : "No");
return 0;
}
六、SG游戏及拓展
这一章节我们讲述 SG 游戏以及一些常见的扩展和应用,包括以下内容:
-
An
t
i
−
S
G
Anti-SG
A
n
t
i
−
S
G
游戏 -
Mu
l
t
i
−
S
G
Multi-SG
M
u
l
t
i
−
S
G
游戏 -
Ev
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏 - 翻硬币游戏
- 无向图删边游戏
1.
A
n
t
i
−
S
G
Anti-SG
A
n
t
i
−
S
G
游戏
有
nn
n
堆石子两个人可以从任意一堆石子中拿任意多个石子,不能不拿,
拿走最后一个石子的人失败
求必胜策略
这个似乎与
S
G
SG
S
G
定理是相反的,
S
G
SG
S
G
函数建立在可执行决策上,它认为当可执行决策为空时(终点态)
S
G
SG
S
G
为 0 ,但这个游戏无法通过可执行决策来确切判断胜负,那我们是否要建立新的
S
G
SG
S
G
定理了呢
先给出结论:
先手必胜等价于
-
∀i
,
A
i
≤
1
&
S
G
(
X
)
=
0
\forall i,A_i \le 1 \space \& \space SG(X)=0
∀
i
,
A
i
≤
1
&
S
G
(
X
)
=
0
-
∃i
,
A
i
>
1
&
S
G
(
X
)
≠
0
\exist i,A_i \gt 1 \space \& \space SG(X)\not=0
∃
i
,
A
i
>
1
&
S
G
(
X
)
=
0
简证:第一点显然,对于第二点,若
S
G
(
X
)
≠
0
SG(X)\not=0
S
G
(
X
)
=
0
,先手每次操作使得其为 0 ,一直下去,使得最终只有一堆的石子数大于 1 ,此时,轮到先手操作,先手可以让局面变成只有奇数个 1 ,先手胜
其实除了全为 1 的情况,剩下情况还是符合常规
S
G
SG
S
G
定理的,我们分析一下
A
n
t
i
−
N
i
m
Anti-Nim
A
n
t
i
−
N
i
m
与常规
N
i
m
Nim
N
i
m
的区别,主要区别在于
S
G
(
X
)
=
0
SG(X)=0
S
G
(
X
)
=
0
时,我们无法判负,为解决这个几乎与常规
N
i
m
Nim
N
i
m
颠倒的博弈,我们引出下面的
S
J
SJ
S
J
定理
首先给出
A
n
t
i
−
S
G
Anti-SG
A
n
t
i
−
S
G
游戏的具体定义:
决策集合为空的游戏者获胜,生成终止局面的游戏者判负
其余规则与普通的
SG
SG
S
G
游戏相同。
再给出
S
J
SJ
S
J
定理:
对于任意一个
An
t
i
−
S
G
Anti-SG
A
n
t
i
−
S
G
游戏如果我们规定当局面中所有的单一游戏(不可再分割游戏)的
SG
SG
S
G
值为 0 时,游戏结束那么
先手必胜
等价于:(1)
∀i
,
S
G
(
x
i
)
≤
1
&
S
G
(
X
)
=
0
\forall i,SG(x_i)\le 1\space \& \space SG(X)=0
∀
i
,
S
G
(
x
i
)
≤
1
&
S
G
(
X
)
=
0
(2)
∃i
,
S
G
(
x
i
)
>
1
&
S
G
(
X
)
≠
0
\exist i,SG(x_i)\gt 1\space \& \space SG(X)\not=0
∃
i
,
S
G
(
x
i
)
>
1
&
S
G
(
X
)
=
0
证明与上述
A
n
t
i
−
N
i
m
Anti-Nim
A
n
t
i
−
N
i
m
类似
// Luogu P4279 Anti-Nim 模板题
int n, m, t, k;
int a[N];
int main(){
scanf("%d", &t);
while(t -- ) {
scanf("%d", &n);
int sg = 0, flag = 0;
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]), sg ^= a[i];
if(a[i] > 1) flag = 1;
}
if((flag == 0 && sg == 0) || (flag == 1 && sg != 0)) puts("John");
else puts("Brother");
}
return 0;
}
2.
M
u
l
t
i
−
S
G
Multi-SG
M
u
l
t
i
−
S
G
游戏
有
nn
n
堆石子两个人可以从任意一堆石子中拿任意多个石子,不能不拿
或者可以把一堆数量不少于
22
2
石子堆分为两堆不为空的石子堆无法操作的人失败
问谁有必胜策略
给出结论:
S
G
(
x
)
=
{
x
−
1
,
x
≡
0
(
m
o
d
4
)
x
,
x
≡
1
&
2
(
m
o
d
4
)
x
+
1
,
x
≡
3
(
m
o
d
4
)
SG(x)=\begin{cases} x-1 ,& x \equiv 0 \pmod 4 \\ x, & x \equiv 1 \&2 \pmod 4 \\ x+1, &x\equiv 3 \pmod 4 \end{cases}
S
G
(
x
)
=
⎩
⎪
⎨
⎪
⎧
x
−
1
,
x
,
x
+
1
,
x
≡
0
(
m
o
d
4
)
x
≡
1
&
2
(
m
o
d
4
)
x
≡
3
(
m
o
d
4
)
S
G
(
X
)
=
⊕
i
=
1
n
S
G
(
x
i
)
SG(X)=\oplus_{i=1}^n SG(x_i)
S
G
(
X
)
=
⊕
i
=
1
n
S
G
(
x
i
)
具体怎么来的,是依靠
独特的智慧
打表 来的,不过事实上,打表也确实是很重要 博弈类游戏 结论发现来源,不是所有人都有着拉马努金那种高超的直觉和经验
我们再来给出
M
u
l
t
i
−
S
G
Multi-SG
M
u
l
t
i
−
S
G
的准确定义:
Mu
l
t
i
−
S
G
Multi-SG
M
u
l
t
i
−
S
G
游戏规定,在符合拓扑原则的前提下,一个单一游戏的后继可以为 多个单一游戏 。
Mu
l
t
i
−
S
G
Multi-SG
M
u
l
t
i
−
S
G
其他规则与
SG
SG
S
G
游戏相同。
那么它有如下性质:
-
一个后继状态的SG值 为 后继状态中所能衍生出的所有独立游戏的异或和
举个简单的例子:
S
G
(
3
)
SG(3)
S
G
(
3
)
的后继状态有
{
(
0
)
,
(
1
)
,
(
2
)
,
(
1
,
2
)
}
\{(0),(1),(2),(1,2)\}
{
(
0
)
,
(
1
)
,
(
2
)
,
(
1
,
2
)
}
也就是这堆有
3
3
3
个石子的石子堆,可以拿走或者分开等四种情况,他们的
S
G
SG
S
G
值分别为 $ { 0 , m e x { 0 } = 1 , m e x { 0 , 1 } = 2 , m e x { 0 , 1 , 2 } = 3 }$,因此 $SG(3)=mex{0,1,2,3}=4 $
int n, a[N], sg[N]; // hdu 3032 Multi-Nim 模板
int main(){
int t, scanf("%d", &t);
while(t -- ) {
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i) {
if(a[i] % 4 == 0) sg[i] = a[i] - 1;
else if(a[i] % 4 == 3) sg[i] = a[i] + 1;
else sg[i] = a[i];
ans ^= sg[i];
}
puts("%s", ans ? "Alice" : "Bob")
}
return 0;
}
int sg[M], vis[M]; // hdu 3032 打表代码
int main(){ // 对于一堆石子,数量为 M ,打表出 SG[M]
sg[0] = 0, sg[1] = 1;
for (int i = 2; i < M; ++ i){
memset(vis, 0, sizeof(vis));
//操作一,至少取一个
for (int j = 1; j <= i; ++ j) vis[sg[i - j]] = 1;
//操作二,分成两堆,不为空
for (int j = 1; j < i; ++ j) vis[sg[j] ^ sg[i - j]] = 1;
int j = 0; while (vis[j]) j ++ ;
sg[i] = j;
}
for (int i = 1; i <= M; ++ i) printf("sg[%d] : %d\n", i, sg[i]);
return 0;
}
3.
E
v
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏
给定一张无向图,上面有一些“棋子”
每人每次必须将所有可以移动的棋子都进行移动
最后不能移动的人输
求是否有必胜策略
还有一道 杭电OJ (HDU-3595) 的题:
GG和MM喜欢玩游戏。在游戏开始时,有两堆石头。
MM首先选择一堆石头,里面有
xx
x
块石头,然后选择一个正数k,从另一堆有
yy
y
块石头的堆中取走
kx
kx
k
x
块石头
(y
≥
k
x
)
(y\ge kx)
(
y
≥
k
x
)
。然后是轮到了GG,也遵循上述规则选择石头。
当有人不能移除任何石头时,他就输掉了比赛,这个游戏就结束了。
很多年后,GG和MM发现这个游戏太简单了,所以他们决定一次同时玩
NN
N
个上述游戏。MM先手,当进入他的回合时,他必须对每个未完成的游戏进行操作。
取石头规则与上述相同,如果有人无法取走任何石头(即输掉最后一场结束游戏),那么他就输了
对于每个测试用例,输出获胜者的姓名
给出
E
v
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏的具体定义:
Ev
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏规定,对于还没有结束的单一游戏,玩家必须对该游戏进行一步决策
Ev
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏的其他规则与普通
SG
SG
S
G
游戏相同
E
v
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏与普通
S
G
SG
S
G
游戏最大的不同就是它多了一维:时间
对于
S
G
SG
S
G
值为0的点,我们需要知道最少需要多少步才能走到结束,
对于
S
G
SG
S
G
值不为0的点,我们需要知道最多需要多少步结束
所有游戏都是独立的,并且我们发现无法操作者输,而同时又在进行多个游戏。因此,我们知道胜负情况最终由最后结束的游戏的胜负情况觉定。
既然只与最后结束的游戏相关,那么我们便不会太在意除最后一个游戏外其他游戏的胜负。
而且又由于我们得同时操作所有柚子,所以,对于我们必胜的游戏,我们一定会想办法将其尽可能的向后拖,尽可能完的结束;反过来,对于我们必败的游戏,我们一定会让他尽可能早的结束。
那么,我们首先可以判定出所有位置是
N
N
N
点还是
P
P
P
点,然后按照判定决策我们按拖延方案走还是加速方案走。
这样我们用
s
t
e
p
step
s
t
e
p
变量来记录每个单一游戏的这个步数,有点像关键路径算法
s
t
e
p
(
u
)
=
{
0
,
u
∈
E
n
d
max
{
s
t
e
p
(
v
)
}
+
1
,
<
u
,
v
>
∈
E
,
u
∈
N
,
v
∈
P
min
{
s
t
e
p
(
v
)
}
+
1
,
<
u
,
v
>
∈
E
,
u
∈
P
step(u)=\begin{cases} 0 ,& u \in End \\ \max \{step(v)\}+1, & <u,v>\in E,u\in N,v\in P \\ \min\{step(v)\}+1, &<u,v>\in E,u\in P \end{cases}
s
t
e
p
(
u
)
=
⎩
⎪
⎨
⎪
⎧
0
,
max
{
s
t
e
p
(
v
)
}
+
1
,
min
{
s
t
e
p
(
v
)
}
+
1
,
u
∈
E
n
d
<
u
,
v
>
∈
E
,
u
∈
N
,
v
∈
P
<
u
,
v
>
∈
E
,
u
∈
P
给出必胜结论:
对于
Ev
e
r
y
−
S
G
Every-SG
E
v
e
r
y
−
S
G
游戏,
先手必胜
⇔\Harr
⇔
单一游戏中最大的
st
e
p
step
s
t
e
p
为奇数
结论建立在以下三条性质上,可以归纳地证明,或者显然地感觉出它们是对的:
-
对于所有的单一游戏,先手必胜状态的
st
e
p
step
s
t
e
p
值为奇数,先手必败状态的
st
e
p
step
s
t
e
p
值为偶数 -
设最大的
st
e
p
step
s
t
e
p
为
ma
x
s
max_s
m
a
x
s
,那么胜手可以保证该单一游戏最少会在
ma
x
s
max_s
m
a
x
s
步结束 -
设最大的
st
e
p
step
s
t
e
p
为
ma
x
s
max_s
m
a
x
s
,那么胜手可以保证他所有必败的游戏最多在
ma
x
s
max_s
m
a
x
s
步结束
然后下面解决 HDU-3595 的题目,不过最好先看下 HDU-1525
浅要说下 HDU-3595 中单一游戏
N
/
P
N/P
N
/
P
判定的结论,这个单一游戏的背景来源于
E
u
c
l
i
d
Euclid
E
u
c
l
i
d
游戏
,
假设
a≥
b
a\ge b
a
≥
b
,那么如果
a=
b
a=b
a
=
b
,先手必胜,如果
a%
b
=
0
a\%b=0
a
%
b
=
0
,先手必胜,而如果
b<
a
<
2
b
b<a<2b
b
<
a
<
2
b
的话,怎么取就已经定了,进而如果
a>
2
∗
b
a>2*b
a
>
2
∗
b
,那么先手可以决定谁先取到
b<
a
<
2
b
b<a<2b
b
<
a
<
2
b
这个状态,所以当
a>
2
∗
b
a>2*b
a
>
2
∗
b
时,先手必胜,只用讨论当
b<
a
<
2
b
b<a<2b
b
<
a
<
2
b
时最后谁胜
int n,m,sg[MAX][MAX],step[MAX][MAX]; // hdu 3595
int SG(int x,int y){
if(x > y) swap(x, y);
if(~sg[x][y]) return sg[x][y];
if(!x || !y) return sg[x][y] = 0;
int r = y%x, d = y/x;
if(d == 1){ // 此时操作唯一
sg[x][y] = SG(r,x) ^ 1;
step[x][y] = step[r][x] + 1;
return sg[x][y];
}else{ // 由上述说明知必胜
step[x][y] = SG(r,x) + 1 + step[r][x]; // (r,x)先手胜的话,需多一步决策
return sg[x][y] = 1;
}
}
int main(){
memset(sg, -1, sizeof(sg));
while(cin >> n){
int mx = 0, a, b;
while(n--){
cin >> a >> b; // 每个单一游戏的两堆石头数
SG(a, b);
mx = max(mx, step[a][b]);
}
puts("%s", mx&1 ? "MM" : "GG");
}
return 0;
}
4.翻硬币游戏
有
nn
n
枚硬币排成一排,依次编号
11
1
到
NN
N
,有的正面朝上,有的反面朝上,现在按照一定的规则翻硬币,
比如每次只能翻一枚或者两枚,或者每次只能翻动连续的几枚,
但是要求最靠右的硬币必须从正面被翻到了反面,
操作集合为空者负,
求必胜策略
给出结论:
当前局面的
S
G
SG
S
G
值是所有正面朝上的硬币单独存在时的
S
G
SG
S
G
值的异或和
结论的来源估计也是打表猜结论和归纳大法
不过这个结论可以直接用,配合状压或者别的算法可以出很多题目
5.无向图删边游戏
给定一个
nn
n
个节点的有根树,两人轮流删边,删去边之后,不和根节点联通的部分都会被移除
不能操作者输,
求必胜策略
给出结论:
叶子节点的
S
G
SG
S
G
值为
0
0
0
,其他所有节点的
S
G
SG
S
G
值为它所有儿子的
S
G
SG
S
G
值加
1
1
1
后的异或和
可以参考
克朗原理
的证明,配合归纳法,假设
n
n
n
节点树成立,那么
n
+
1
n+1
n
+
1
节点树也成立
同时,树的删边游戏可以进一步扩展,感兴趣的同学可以参考
F
u
s
i
o
n
P
r
i
n
c
i
p
l
e
Fusion \space Principle
F
u
s
i
o
n
P
r
i
n
c
i
p
l
e
七、致谢与感悟
忙活了一整天,终于完结撒花了
学到了很多东西,对其内在数学模型有了更深的了解,也熟悉了一些常见处理手段(打表、归纳)
同时也收集了许多关于
S
G
SG
S
G
函数应用的代码模板和应用模型,真的收获颇丰
下面给出一些有用的链接,在写作时参考了很多
- 《组合游戏略述——浅谈SG游戏的若干拓展及变形》贾志豪 本文参考了许多许多
-
博弈论ACM / OI_繁凡さん的博客
里面总结的特别全面 -
博弈论知识汇总 solvit
里面介绍了本文未提到的
Ni
m
K
NimK
N
i
m
K
和
St
a
i
r
N
i
m
StairNim
S
t
a
i
r
N
i
m
-
博弈论题目总结(一)
和
博弈论题目总结(二)
分别介绍了经典博弈和
SG
SG
S
G
函数应用的大量例题 -
博弈论总结_Ethan-Walker的博客
里面包含了 80 余道博弈习题,涉及了博弈的方方面面 -
ACM-ICPC中博弈论的一些小小总结_phython96的博客
也介绍了一些本文未出现的思想方法和模型