博弈论小结byxaphoenix_巴什博弈

需积分: 45 200 浏览量更新于2023-05-30 评论收藏 350KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

博弈论小结

by xaphoenix

写在前面

第一次写一个专题的总结，由于笔者水平有限，所以里面肯定会有很多不恰当之处，

希望读者不吝赐教。此外，这个小结中，有大约 2000 字的直接复制粘贴的知识介绍，有几

道题的题目分析或者题意概括来源于网上各位大牛的博客，所以笔者不具有著作权，具体

的参考资料在本文最后列出。另外，为了节省页数（准备把这个带到现场），所以排版比

较凌乱，字体基本都是五号字，仅仅是在标题处用加粗作为标记，希望读者能理解。本文

几乎囊括了所有笔者知道的 ACM 中有关博弈论的知识内容，如有疏漏之处，希望能在

csdn 博客上私信我。例如本文由于笔者没有接触到关于纳什均衡和混合纳什均衡

（ WC2014 上介绍过）相应的题目，所以没有深入的学习。例题部分包括了

hdu、poj、zoj、bzoj 中大多数经典的题目，当然主要的题目列表来源于 cxlove 的博弈论总

结。笔者也会在之后的学习中不断添加例题。由于博弈论是一个需要经验和严谨证明的领

域，所以希望能列出较为丰富的题目，能够从中学习掌握到大部分的博弈论知识和技巧。

洋洋洒洒 23000 字，用时两周多完成，笔者也希望能借助此文，和更多对博弈论题目有兴

趣的朋友相互交流、学习。

思路清晰的题目

例题 poj1678 I Love this Game!

题意：给你一个有 n 个元素的集合。给定一个区间[a,b] (0<a<b)。两个玩家轮流选取

一系列递增的数，其中每个数都在区间[a,b]内，除了第一个玩家选取的第一个数应为集合

中的元素，其他被选出来的数还要满足：被选出来的数与前一个数之差在 [a,b]内。每个玩

家的得分为这个玩家选出的所有数之和，求问玩家 1 能够获得的最大分差是多少。

分析：很显然的动态规划思路。

例题 hdu3863 No Gambling

题意：

先手连接蓝色的点，从左向右要连出一个桥，如 FigureB 所示，后手连接红色的点，

目的是不然先手完成任务，且红色边与蓝色边不能有任何接触。

分析：显然，先手必胜。先手的初始思路是沿一条不是底端直线的直线连过去，如果

后手选择用两边的红点阻挡，显然先手可以选择连接出这条红边其下的一条蓝边。之后再

把这些“脱离队伍”的边用纵向的蓝边连起来即可，因为这些边已有一个蓝点，所以后手无

法占领或阻挡。

分析决策前后的不变量

（一）考虑奇偶性的变化

例题 hdu1079 Calendar Game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1079

题意：从当前日期开始，玩家可以选择移动到下一天或者下一个月的同一天（如果月

份加 1 超过 12，则进入新的一年；如果移动使得新的日期不合法，则不能移动）。如果一

个玩家移动到 2001 年 11 月 4 日，则该玩家胜利；如果一个玩家移动到 2001 年 11 月 4 日以

后，则该玩家失败，问先手必胜还是后手必胜。

分析：我们发现，进行一次移动后，日期与月份之和的奇偶性总发生改变（除了 9 月

30 日和 11 月 30 日）。那么，如果不考虑这两天的情况下，如果初始日期月份与日期之和

为偶数，则先手必胜。如果初始日期为 9 月 30 日或者 11 月 30 日，先手可以选择奇偶性不

变的一次日期变化。这样就又成了先手必胜的情况。下面我们考虑是否中间会遇到这两个

特殊点。如果初始状态为先手必胜，则先手总存在办法，不到达这个两个特殊点，即（ 8

月 30 日和 10 月 30 日时不选择增加月份，9 月 29 日和 11 月 29 日时不选择日期）。如果初

始状态为先手必败，同样，后手总有办法不到达这两个特殊点。所以只可能在初始时除于

这两个特殊点。即，读入日期后，我们判断日期与月份之和为偶数或为 9 月 30 日或为 11

月 30 日，先手必胜；否则，后手必胜。

例题 hdu1564 Play a game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1564

题意：给你一个 n*n 的棋盘，游戏开始时有一块在拐角处的石子。两个玩家轮流移动

该石子，移动时只能移动到相邻且未访问过的点，问先手必胜还是后手必胜。

分析：我们对该棋盘用 1*2 的长方形进行覆盖。若 n 为偶数，那么必存在一个覆盖方

案。此时先手选择走向与当前状态同处一个长方形内的另一点。这样，无论先手怎么移动

先手必存在一种移动方法。由于这个游戏无平局，所以先手必胜。若 n 为奇数，我们考虑

同样的方法，将 n*n 的棋盘除去起点的 n*n-1 格进行覆盖。之后无论先手怎么走，后手都

存在一种移动方案，所以先手必败。

例题 hdu4203 Doubloon Game

题意：有 n 枚硬币，再给你一个数 k，每次只能拿 k^m 枚（m 为自然数），两人轮流

拿，先拿完者胜。如果先手必败，输出 0，否则输出先手保证必胜的情况下第一步最少拿

的硬币数。

分析：先考虑 k 为奇数的情况，此时 k 的 m 次方一定为奇数。也就是说，如果 n 为奇

数，那么最后一枚硬币一定是先手拿的，且第一轮只用拿 1 枚即可。若 n 为偶数，则先手

必败。然后再考虑 k 为偶数的情况，首先我们可以手算出 n=0,1,0,1,```,0,1,k。之后接下来用

数学归纳法证明其周期为(k+1)。

例题 bzoj2927 多边形之战

题目：给定一个凸多边形的三角剖分，其中一个三角形被涂成了黑色，每次可以一刀

割下一个三角形，割下黑色三角形的人胜利。

分析：建立其对偶图，问题转化为一颗树上有一个黑色节点，每次删去一个叶节点，

删去黑色叶节点的人胜利。如果一开始黑色节点就是叶节点，那么先手必胜。其他情况，

黑色点必须剩两个白点连在其旁边保证它不为叶节点，否则对方必胜。由于每次只能删去

一个叶节点，这种情况下，胜负就只与 n 的奇偶性相关了。

例题 bzoj1443 游戏 Game

题意：给定一个矩阵，一些位置由障碍，先手放置在某个位置，后手移动，先手再移

动，一个格子只能经过一次，问是否先手必胜。

分析：在格子上移动，我们很容易想到黑白二染色。这样就转化为了经典的二分图博

弈问题。接下来我们考虑移动的方法：对于任意一个点，如果存在一个最大匹配中这个点

没有被匹配，则先手从这个点开始存在必胜策略。先手放置后，后手无论走到哪个点，先

手一定能沿着匹配边走回去。如果不存在这样的一条边，说明找到了一条增广路，矛盾！

所以一定存在匹配边。同理，当二分图存在完备匹配时，先手必败。题目还要求输出所有

先手选择后必胜的点，枚举每个未匹配的点，沿着出边、匹配边、出边······这样的顺序深

搜，深搜到的所有左侧的点就是左侧的可选点集。

（二）考虑总量的不变性

例题 hdu3544 Alice’s Game

题意：给 n 块的巧克力，每一块分别是 x

的，先手只能竖着切一刀，后手只能横着

切一刀。谁不能切谁输，问先手是否有必胜策略。

分析：我们知道，如果一块巧克力被彻底切开，无论切的方式怎样，横切的总长度一

定为(x-1)*y，竖切的总长度一定为 x*(y-1)。而为了让对方切的次数变少，我们应该尽量让

对方每次切的长度长，所以我们采用从中间切开的策略，使得对方每次切的都比较长。相

应的，对方每次都选择切长度最小的。

对称构造

例题 hdu3951 Coin Game

题意：n 个硬币围成一个圆，每次可以取连续的 1~k 个硬币，问先手是否有必胜策略。

分析：我们很容易能想到利用对称构造的思路来进行对抗。但是对称构造需要的是两

个不相干且完全相同的子问题。本题是一个环，所以我们需要破环为两条相同长度的链。

首先我们很容易发现，如果 n<=k 的话，先手可以一次取完。那么其他情况下，先手取完后

会留下一条链。如果该链的长度为奇数，那么后手选取最中间的那一点即可，之后与先手

进行对称构造；如果该链的长度为偶数，那么后手应该选取最中间的两点，但是注意 k=1

的情况需要特殊讨论，之后进行对称构造即可。

例题 poj2484 A Funny Game

题意：有 N 个硬币围成一圈，两个玩家轮流从中拿 1 个或者相邻的两个。先拿完者胜

利，问是否先手必胜。

分析：如果 n<2，显然先手必胜。如果 n>=3，一定后手必胜：若 n 为偶数，则先手取

完 1 个或两个后，后手选取同样的个数，所拿的硬币需要与先手拿的呈中心对称，这样就

变成了两条完全相同的链，后手必胜。如果 n 为奇数，则先手取完 1 个或两个后，后手选

取不同的个数，所拿的硬币同样需要与先手所拿的硬币呈中心对称。同样后手必胜。

从特殊情况入手

（一）从最简单的必胜态入手

例题 hdu1525 Euclid’s Game

题意：给定两个正整数 a，b。每次操作，可以将大的数减掉小的数的整数倍（减去

后不能为负数）。如果一个操作者，将 a，b 中一个数变成 0 时游戏结束，并且该玩家胜利。

求先手必胜还是后手必胜。

分析：不妨设 a>=b，我们很容易发现，当 a%b=0 时，当前操作者必胜。如果 a>=2*b

时，当前操作者依然有必胜策略：如果 a%b ， b 是必胜态，则先手将 a ， b 变成 a

%b+b，b，这样后手只能将其变成 a%b，b，然后先手必胜；如果 a%b，b 是必败态，则先

手将 a，b 变成 a%b，b，然后后手会输掉比赛。如果 b<a<2*b 时，只能选择变成 a%b，b，

一直这样操作下去，看谁先到达上述的必胜态即可。

例题 poj1740 A New Stone Game / bzoj1982 Moving Pebbles

题意：有 n 堆石子，两个人轮流操作，每次操作分两步，第一步从某堆中去掉至少一

个，第二步，可以把该堆剩余石子的一部分分给其它的某些堆（可省略）。问是否先手必

胜。

分析：1 堆显然是一个必胜点。考虑两堆的状况，双方的目的都是逼对方至两堆都是

1 的情况。如果一开始两堆的状况相同，那么后手可以模仿先手的做法，这样后手必胜。

其他情况下，先手可以将两堆的情况传化为两堆相同，此时先手必胜。3 堆时，先手可以

通过对石子数最多的那一堆进行操作，使得情况传化为两堆相同的情况。此时先手必胜。

猜想对于 n 堆石子，当且仅当 n 为偶数，且 n 对石子可以分成 n/2 对两两相同的堆时先手必

败。对于必胜态：n 为奇数时，选最大和最小的两堆，易知可以对最大堆操作，使得剩下

的偶数堆两两相等。n 为偶数且不满足 n/2 对两两相同时，根据同样的做法，同样可以转移

到必败态上。对于必败态：无论取哪堆都不能使得剩下的石子变成 n/2 对两两相同的状态。

（二）从最简单的必败态入手

例题 hdu2147 kiki’s game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2147

题意：在一个 n*m 的矩阵中起始位置(1,m)，走到终止位置(n,1)；游戏规则是只能向

左，向下，左下方向走，想走到终点的为获胜者。

分析：最容易想到的必败态就是 1*1 的矩阵，此时先手必败。那么 1*2，2*1,2*2 都为

先手必胜。假设先手当且仅当面对 n 和 m 全为奇数的矩阵时必败，利用数学归纳进行考虑。

如果当前状态为两偶，则其沿对角线走，对手面对的将是两奇，此时先手必胜；如果当前

状态为一奇一偶，则其沿偶的那个方向走，对手面对的仍然是两奇，此时先手必胜；如果

当前状态为两奇，无论其怎么走，也不能给对手留下两奇的状态，此时先手必败。

（三）从固定参数的情况进行讨论

例题 hdu1538 A Puzzle for Pirates

题意：有 n 个海盗，分 m 块金子，其中他们会按一定的顺序提出自己的分配方案，

如果 50%以上的人赞成，则方案通过，开始分金子，如果不通过，则把提出方案的扔到海

里，下一个人继续。

分析：经典的海盗分金问题。看了 cxlove 大神的博客才会的。我们先考虑 n<=2*m 的

情况：如果只有 1 号和 2 号，那么根据 50%的规则，无论 2 号提出什么条件都能通过，所

以 2 号可以 100:0 分配。如果有 1 号 2 号 3 号三人，3 号为了获得 1 号的支持，只用给 1 号

一枚金币即可，剩下金币都给自己。同理，4 号存在时，会贿赂 2 号一枚金币，剩下全留

给自己。 5 号存在时会贿赂 1 号 3 号各一枚金币，其余留给自己。以此类推。如果

n=2*m+1：那么 n 号海盗为了让其他人支持来保命，会选择把 m 个金币，给前面 2m 个人

中的 m 个人，这样就能获得 50%以上的支持。下来考虑 n>2*m+1 的情况。首先，第

2*m+1 号人的做法同上，第 2*m+2 号人为了获得支持，将给第 2*m+1 号人的分配方案中没

分配到的 m 个人金币，这样就能拥有 50%的支持。第 2*m+3 号人无法获得支持，所以他提

出的方案一定无法通过，只能选择支持后面的人。2*m+4 号有了前 2*m 个人中 m 个人的支

持，和 2*m+3 号的支持，他的方案也能通过。第 2*m+4、2*m+5、2*m+6、2*m+7 同样获

得不了足够的支持，而 2*m+8 的人拥有了 50%的支持率，他的方案可以通过。以此类推。

我们可以发现，2*m+2^k 号海盗的方案可以通过，处在这样两个特殊海盗中间的其他海盗

的方案无法通过。

（四）分析参数之间的大小关系

例题 bzoj4147 Euclidean Nim

题意：Euclid 和 Pythagoras 在玩取石子游戏，一开始有 n 颗石子。Euclid 为先手，他

们按如下规则轮流操作：若为 Euclid 操作，如果 n<p，则他只能新放入 p 颗石子，否则他

可以拿走 p 的倍数颗石子。若为 Pythagoras 操作，如果 n<q，则他只能新放入 q 颗石子，否

则他可以拿走 q 的倍数颗石子。拿光所有石子者胜利。假设他们都以最优策略操作，那么

获胜者是谁，或者游戏永远不会停止。

分析：首先我们会发现，如果 p 和 q 有最大公约数 d，那么当 n 不是 d 的倍数时，游

戏永远不会停止，反之，我们可以把这个公约数消去，使得 p 和 q 互质，并且这种情况下，

游戏一定能结束。下面我们分情况讨论：

1、p=q。此时 p 只能为 1，则先手必胜。

2、p>q,n<p。此时先手只能新放入 p 颗石子，而后手操作后，n 一定会再次小于

p，所以先手永远只能进行放石子的操作，先手必败。

3、p>q,n>=p。如果先手操作后 x>=q,那么后手可以将石子数变成 x mod q，就转化

为了状态 2，先手必败。所以先手只能取成 n mod p，然后后手+q，先手-p，这样不停

进行下去。所以当(p-q)|(n mod p)且 n mod p>q 时先手必胜。

4、若 p<q,n<p，那么先手第一次操作只能是+p，如果 n+p<q，后手只能+q，先手

mod p 后转化为了状态 2，先手必胜，否则转为状态 3.

5、若 p<q,n>=p,那么先手取子，石子数变为 n mod p，转为状态 2，先手必胜。

博弈树

（一）博弈树基础

用搜索去处理一个点的后继状态，如果后继态中有一个必败态，则该点为必胜态，否

则为必败态。

例题 hdu1760 A New Tetris Game

题意：给定一个 n*m 的棋盘(n,m<=50)，棋盘的每一格用 0,1 表示，0 表示未占用，1

表示已占用，其中 0 的个数不超过 40。现在两个玩家，轮流放置一个 2*2 的俄罗斯方块，

剩余26页未读，继续阅读

xaphoenix

粉丝: 17
资源: 1

会员权益专享

博弈论小结by xaphoenix

评论0

会员权益专享

最新资源

博弈论小结by xaphoenix

评论0

你了解博弈论在控制领域的应用吗

博弈论与无线通信系统中各种优化问题的关系

认知无线电中基于博弈论频谱分配

博弈论与信息经济学ppt课件

说说“演化博弈论”。

Python写一段演化博弈论代码

请写一段关于博弈论的MATLAB代码

博弈论：开放获取教科书（Giacomo Bonanno）Game Theory: An Open Access Textbook (Giacomo Bonanno)

博弈论与无线通信系统中各种优化问题的对应关系

请利用博弈论、垄断竞争等相关理论解释为何中央要持续加强互联网平台的反垄断，并给出你的对策

20篇2021-2022年发表的关于强化学习的高质量论文

帮我写一份1000字以上的运筹学收获与体会报告。

写一个基于纳什均衡的多无人机任务分配的C代码

考虑风险管理下的金融服务供应链多参与者协同机制的演化博弈分析，应该包含哪些内容

shap是怎么定义可解释特征的

centos7-mysql-5.7.40.tar

会员权益专享

最新资源