logo资料库

博弈论小结by xaphoenix.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.34M 资料格式：doc 举报 版权申诉
第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
资料共27页，剩余部分请下载后查看
    博弈论小结 by xaphoenix 写在前面 第一次写一个专题的总结，由于笔者水平有限，所以里面肯定会有很多不恰当之处，希 望读者不吝赐教。此外，这个小结中，有大约 2000 字的直接复制粘贴的知识介绍，有几道 题的题目分析或者题意概括来源于网上各位大牛的博客，所以笔者不具有著作权，具体的参 考资料在本文最后列出。另外，为了节省页数（准备把这个带到现场），所以排版比较凌乱， 字体基本都是五号字，仅仅是在标题处用加粗作为标记，希望读者能理解。本文几乎囊括了 所有笔者知道的 ACM 中有关博弈论的知识内容，如有疏漏之处，希望能在 csdn 博客上私 信我。例如本文由于笔者没有接触到关于纳什均衡和混合纳什均衡（WC2014 上介绍过）相 应的题目，所以没有深入的学习。例题部分包括了 hdu、poj、zoj、bzoj 中大多数经典的题 目，当然主要的题目列表来源于 cxlove 的博弈论总结。笔者也会在之后的学习中不断添加 例题。由于博弈论是一个需要经验和严谨证明的领域，所以希望能列出较为丰富的题目，能 够从中学习掌握到大部分的博弈论知识和技巧。洋洋洒洒 23000 字，用时两周多完成，笔者 也希望能借助此文，和更多对博弈论题目有兴趣的朋友相互交流、学习。 思路清晰的题目 例题 poj1678 I Love this Game! 题意：给你一个有 n 个元素的集合。给定一个区间[a,b] (0
    题目链接：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 块的巧克力，每一块分别是 xi*yi 的，先手只能竖着切一刀，后手只能横 着切一刀。谁不能切谁输，问先手是否有必胜策略。 分析：我们知道，如果一块巧克力被彻底切开，无论切的方式怎样，横切的总长度一 定为(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
    号一枚金币即可，剩下金币都给自己。同理，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 操作，如果 nq,nq,n>=p。如果先手操作后 x>=q,那么后手可以将石子数变成 x mod q，就转化 为了状态 2，先手必败。所以先手只能取成 n mod p，然后后手+q，先手-p，这样不停 进行下去。所以当(p-q)|(n mod p)且 n mod p>q 时先手必胜。 4、若 p=p,那么先手取子，石子数变为 n mod p，转为状态 2，先手必胜。 博弈树 （一）博弈树基础 用搜索去处理一个点的后继状态，如果后继态中有一个必败态，则该点为必胜态，否则 为必败态。 例题 hdu1760 A New Tetris Game 题意：给定一个 n*m 的棋盘(n,m<=50)，棋盘的每一格用 0,1 表示，0 表示未占用，1 表示已占用，其中 0 的个数不超过 40。现在两个玩家，轮流放置一个 2*2 的俄罗斯方块， 放置的方块之间不能有重叠，且不能放到已占用的格子上。问是否先手必胜。 分析：由于 0 的个数很少，我们可以用搜索进行递归处理，在每一层中，遍历整个棋 盘，枚举放下 2*2 俄罗斯方块的位置。返回值为 0 或 1，当且仅当后继状态有一个返回值为
    0 时返回 1，其他情况返回 0 。 例题 hdu4155 The Game of 31 题意：有 24 张牌，最多由 4 张 1,2,3,4,5,6 组成。两个玩家轮流选一张牌，总的牌的 点数不能超过 31，谁不能选牌谁输。 分析：dfs 求解即可。 例题 bzoj3404 Cow Digit Game 又见数字游戏 题意：给你一个数，两个玩家轮流操作，可以给原数减去一个原数各个位上最大的数 字，也可以给原数减去一个原数各个位上最小的非 0 数。问是否先手必胜。 分析：暴力求 PN 表即可。 例题 poj2068 Nim 题意：有 2n 个人，两方各 n 个人，交叉坐，每个人可以取的石子有一个最大限制， 总共有 S 颗石子，哪一方取了最后一颗石子就输了，问是否先手必胜。 分析：记忆化搜索求 PN 态即可。 （二）简单优化 例题 zoj2686 Cycle Game 题意：N 个点形成一个环，相邻点之间有权值。从 0 号点开始，可以选择往两边移动， 前提是权值为正，移动之后，可以将权值减少一个任意的正数。最后无法移动者输，问是否 先手必胜。 分析：对搜索进行优化。我们发现，如果有一个方向上有连续的奇数个非 0 数，那么 先手可以将权值降为 0，后手就无法返回了，如果后手也将权值降为 0，则最终先手必胜， 反之，如果后手不降为 0，那么先手返回一步，将权值降为 0，出现两边都是 0 的情况，后 手无法移动，此时先手必胜。在这个优化下可以搜索出答案。 例题 zoj3057 Beans Game 题意：有三堆石子，每堆石子的个数都不超过 300，两个玩家轮流操作，每次可以从 一堆石子拿任意多石子，也可以从两堆石子拿任意多相同的石子。问是否先手必胜。 分析：同样思路是求 PN 态，但是数据比较大，所以我们需要用 dp 来递推。 例题 zoj1039 Number Game 题意：我们在 2-20 这 19 个数字上进行游戏。两个玩家轮流取数，取完这个数后，这 个数的倍数不能再取，而且某两个不能取的和，也不能再取。 分析：利用状压 dp 来表示每个数字是否被选，然后暴力求 pn 表即可。 （三）极大极小搜索和 alpha-beta 剪枝 极大极小搜索：利用估价函数，考虑每一步行动后对先手的价值。那么每次先手搜索时， 都会从估价最高的行动策略开始搜索。相应地，每次后手搜索时，都会从估价最低的行动策 略开始搜索。 alpha_beta 剪枝：alpha 记录的是博弈树搜索到当前深度时的最大估价值，也就是最好的 情况。beta 记录的是博弈树搜索到当前深度时最小的估价值，最坏的情况，利用这两个信息 进行剪枝，使得搜索加快。
    例题 poj1085 Triangle War 题意：给出 10 个点，总共 18 条边，两个玩家轮流加入一条边，如果形成一个三角形， 则三角形归当前玩家所有，并且可以额外再走一步。最后三角形多的人获胜，问是否先手必 胜。 分析：构建估价函数,利用极大极小搜索和 alpha-beta 剪枝来优化博弈树搜索。 经典博弈问题及其拓展问题 （一）巴什博奕（Bash Game） 游戏情形：n 个物品组成一堆，两个人轮流从这堆物品中取物，规定每次至少取一个， 最多取 m 个，最后取尽物体一方赢。 对抗策略分析：考虑 n 对 m+1 取模的余数。如果为 0，那么如果先手取 k 个(0
    题意：初始 p=1，两位玩家轮流，给 p 乘上一个 2 到 9 的数，谁先使得 p 超过给定的 n 谁胜利。 分析：如果刚开始的数时位于 2-9 之间的，那么先手必胜。如果刚开始的数时位于 10-18 的，那么先手必败，因为无论先手选什么，后手只要乘以 2 就能够到达 10-18 之内的 所有数。如果刚开始的数位于 19-162，那么先手必胜，可以这么想，先手选一个 9，那么后 手乘以一个数后，Num>=18，此时先手再乘以 9，那么就大于 162 之内的任何数了。如果刚 开始的数位于 163-324 时，那么先手必败，可以这么考虑，后手可以控制一个数到达 9-18 之间，那么先手如果乘个 2 的话(乘以大的那就更不用说了)，那么就会到达 18-36 这个区间， 此时后手再乘以 9，那么就可到达 163-324 之间的任何数。以此类推，不断除 2、除 9 循环， 找到其所在区间即可。 （二）威佐夫博弈（Wythoff Game） 游戏情形：有两堆数量各若干的物品，两个人轮流从某一堆或同时从两堆中取同样多的 物品，规定每次至少取一个，多者不限，最后取尽物体一方赢。 对抗策略分析：我们用(ak,bk) (ak<=bk,k=0,1,2,···,n)表示两堆物品的数量并称其为局势。 如果甲面对(0,0)，那么甲已经输了，这样的局势我们称为奇异局势。前几个奇异局势为：(0,0)、 (1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。可以看出，a0=b0=0，ak 是未在 前面出现过的最小的自然数，而 bk=ak+k。奇异局势有如下三个性质： 【性质 1】 任何自然数都包含在一个且仅有一个奇异局势中。 【性质 2】 任意操作都可以将奇异局势变为非奇异局势 【性质 3】 采用适当的方法，可以将非奇异局势变为奇异局势 分析：假设面对的局势是(a,b)。 如果 b=a，则同时从两堆中取走 a 个物体，就变成了奇异局势(0,0)。 如果 a=ak，b>bk，则取走 b-bk 个物体，则变为奇异局势。 如 果 a=ak ， bak，b=ak+k，则从第一堆中拿走多余的数量 a-ak 即可。 如果 a
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料