- 博弈论
- 一、内容简介
- 二、前置概念
- 1.ICG
- 2.博弈图
- 3.P点、N点
- 4.mex函数
- 三、前置定理
- 四、四大经典组合游戏
- 1.Nim游戏
- 2.Bash游戏
- 3.Wythoff游戏
- 4.Fibonacci游戏
- 五、SG函数
- 1.SG函数
- 2.SG定理
- 3.简单应用
- 六、SG游戏及拓展
- 1. A n t i − S G Anti-SG Anti−SG 游戏
- 2. M u l t i − S G Multi-SG Multi−SG 游戏
- 3. E v e r y − S G Every-SG Every−SG 游戏
- 4.翻硬币游戏
- 5.无向图删边游戏
- 七、致谢与感悟
本文主要介绍算法竞赛中常常出现的博弈论模型，包括：
- 4个经典组合游戏
- SG函数
- SG游戏及拓展
进一步学习需要了解一些前置概念
- ICG
- 博弈图
- P点、N点
- mex函数
ICG全称为“公平组合游戏”，我们下面讨论的博弈游戏均建立在ICG的基础上，那么什么是ICG呢，它需要满足以下条件：
- 由两名玩家交替行动
- 对任意局面，接下来可执行的行动仅与局面有关（玩家平等）
- 游戏以玩家无法行动为结束，且无平局
那么称此游戏为“公平组合游戏”
2.博弈图我们可以看到，整个过程是各个状态的集合，且状态间可以到达，那么我们可以将这个博弈过程抽象为一张图，称为博弈图，这个游戏我们也称之为有向图游戏
那么这个图是一个有向无环图，图中有唯一的起点，可能有多个终点，两名玩家的交替行动可认为是图上的有向边，所有出度为0的节点便是终点
对于这个图，每个节点存储如下信息：{弈盘信息x，先手信息p，…}等
同时有如下结论：任何一个公平组合游戏均可以转化为有向图游戏
3.P点、N点P点和N点是博弈里面两个及其重要的概念
- 先手必胜状态：先手行动后，可以将一个必败状态留给后手
- 先手必败状态：先手无论如何行动，只能将必胜状态留给后手
- 必败点（P点）：前一个选手取胜，当前选手将败的节点（previous）
- 必胜点（N点）：下一个选手将败，当前选手取胜的节点（next）
mex函数是一个建立在集合上的整数函数，即 m e x : S N ↦ N mex: S_N \mapsto N mex:SN↦N ，它的定义域是一个非负整数集， m e x mex mex代表这个集合里最小未出现的非负整数，举几个例子： m e x ( { 1 , 2 , 3 } ) = 0 mex(\{1,2,3\})=0 mex({1,2,3})=0， m e x ( { 0 , 1 , 2 } ) = 3 mex(\{0,1,2\})=3 mex({0,1,2})=3， m e x ( { 0 , 2 , 3 } ) = 1 mex(\{0,2,3\})=1 mex({0,2,3})=1，等等
三、前置定理定理一：没有后继状态的状态是必败状态
定理二：一个状态是必胜状态 ⇔ \Harr ⇔ 它至少存在一个向必败状态的转移
定理三：一个状态是必败状态 ⇔ \Harr ⇔ 它所有后继状态均为必胜状态
四、四大经典组合游戏 1.Nim游戏给定 N N N 堆物品，第 i i i堆物品有 A i A_i Ai 个。
两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。
取走最后一件物品者获胜。
问先手是否必胜。
Nim博弈是最经典的博弈之一，许多博弈均可转化为Nim博弈，我们给出结论：
先手必胜 ⇔ \Harr ⇔ A 1 ⊕ A 2 ⊕ A 3 . . . ⊕ A n ≠ 0 A_1\oplus A_2\oplus A_3...\oplus A_n\ne0 A1⊕A2⊕A3...⊕An=0
由归纳法其实很容易证得，也可以利用三个前置定理进行证明，但这个等价表达式还是给予我们很多震撼~~（也给予出题人很多灵感）~~
但其实我们不应把Nim游戏看成一个独立游戏，而应该把它看成若干个游戏的和
对每个游戏，先手是否必胜 ⇔ \Harr ⇔ A i ≠ 0 A_i\ne0 Ai=0
进而对于这 n n n 个游戏的加和为 A 1 ⊕ A 2 ⊕ A 3 . . . ⊕ A n A_1\oplus A_2\oplus A_3...\oplus A_n A1⊕A2⊕A3...⊕An
游戏和的概念后续还会继续用到，也是用异或的形式给出表达式，这个表达式很重要
int main(){
scanf("%d", &n);
for(int i = 1; i 1 & SG(X)=0
证明与上述
A
n
t
i
−
N
i
m
Anti-Nim
Anti−Nim 类似
// 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 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
Multi−SG 游戏
有
n
n
n 堆石子
两个人可以从任意一堆石子中拿任意多个石子，不能不拿
或者可以把一堆数量不少于
2
2
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}
SG(x)=⎩⎪⎨⎪⎧x−1,x,x+1,x≡0(mod4)x≡1&2(mod4)x≡3(mod4)
S
G
(
X
)
=
⊕
i
=
1
n
S
G
(
x
i
)
SG(X)=\oplus_{i=1}^n SG(x_i)
SG(X)=⊕i=1nSG(xi)
具体怎么来的，是依靠 独特的智慧 打表 来的，不过事实上，打表也确实是很重要 博弈类游戏 结论发现来源，不是所有人都有着拉马努金那种高超的直觉和经验
我们再来给出
M
u
l
t
i
−
S
G
Multi-SG
Multi−SG 的准确定义：
M
u
l
t
i
−
S
G
Multi-SG
Multi−SG 游戏规定，在符合拓扑原则的前提下，一个单一游戏的后继可以为 多个单一游戏 。
M
u
l
t
i
−
S
G
Multi-SG
Multi−SG 其他规则与
S
G
SG
SG 游戏相同。
那么它有如下性质：
- 一个后继状态的SG值 为 后继状态中所能衍生出的所有独立游戏的异或和
举个简单的例子：
S
G
(
3
)
SG(3)
SG(3) 的后继状态有
{
(
0
)
,
(
1
)
,
(
2
)
,
(
1
,
2
)
}
\{(0),(1),(2),(1,2)\}
{(0),(1),(2),(1,2)} 也就是这堆有
3
3
3 个石子的石子堆，可以拿走或者分开等四种情况，他们的
S
G
SG
SG 值分别为 $ { 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
关注
打赏
![]()
1688896170
查看更多评论
