wordpress 网站地图类,北京朝阳区有哪些小区,杭州市建设工程招标信息网,WordPress立体边框前言
本篇为博弈论总结#xff0c;文章会按题目类型分类。
基础铺垫——必胜点和必败点的介绍
P点#xff1a;必败点#xff0c;换而言之#xff0c;就是谁处于此位置#xff0c;则在双方操作正确的情况下必败。 N点#xff1a;必胜点#xff0c;处于此情况下#x…前言
本篇为博弈论总结文章会按题目类型分类。
基础铺垫——必胜点和必败点的介绍
P点必败点换而言之就是谁处于此位置则在双方操作正确的情况下必败。 N点必胜点处于此情况下双方操作均正确的情况下必胜。 必胜点和必败点的性质 1、所有终结点是 必败点 P 。我们以此为基本前提进行推理换句话说我们以此为假设 2、从任何必胜点N 操作至少有一种方式可以进入必败点 P。 3、无论如何操作必败点P 都只能进入 必胜点 N。 我们研究必胜点和必败点的目的是为题进行简化有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。
思路清晰的题目
分析决策前后的不变量
一考虑奇偶性的变化
二考虑总量的不变性
对称构造
从特殊情况入手
一从最简单的必胜态入手
二从最简单的必败态入手
三从固定参数的情况进行讨论
四分析参数之间的大小关系
博弈树
一博弈树基础
二简单优化
三极大极小搜索和alpha-beta剪枝
经典博弈问题及其拓展问题
一巴什博奕
普通巴什博奕
1.问题模型 只有一堆n个物品两个人轮流从这堆物品中取物规定每次至少取一个最多取m个。最后取光者得胜谁拿了最后一个谁赢。
2.解决 当nm1时由于一次最多只能取m个所以无论先取者拿走多少个后取者都能够一次拿走剩余的物品后者取胜所以当一方面对的局势是n%(m1)0时其面临的是必败的局势。
当nm1)*rs时r为任意自然数0 s ≤ m)时,只要先取者要拿走s个物品局面便变成了n%(m1)0的必败局面所以先取者必胜。总之要保持给对手留下m1的倍数就能最后获胜。
3.变形条件不变改为最后取光的人输。 结论当n-1%m10时后手胜利。
巴什博奕的扩展——k倍动态减法游戏
1.问题模型 有一个整数S(2)先行者在S上减掉一个数x至少是1但小于S。之后双方轮流把S减掉一个正整数但都不能超过先前一回合对方减掉的数的k倍减到0的一方获胜。
2.解决 法一曹钦翔的《从“k倍动态减法游戏”出发探究一类组合游戏问题》中提到了动态规划的优化算法 咕咕咕。。。
法二纯数学方法 k1的时候 必败态是2 ^ i, 因为我们把数按二进制分解后拿掉二进制的最后一个1那么对方必然不能拿走倒数第二位的1因为他不能拿的比你多。你只要按照这个策略对方一直都不可能拿完而且一定会生成新的低位的1。所以你就会赢。而当分解的二进制中只有一个1时因为第一次先手不能全部取完所以后手一定有办法取到最后一个1所以必败
k2的时候 即为斐波那契博弈必败态是斐波那契数列这里用到一个斐波那契数列的性质即任何数都可以表示成若干个“互不相邻的”斐波那契数的和而不相邻的斐波那契数所差的倍数都是大于2的那么我们就可以类比K1的情况把N按这种“斐波那契数列”的数制分解每次仍然是取走最低位的1由于后手无法取走高两位之上的1而前边的不相邻有保证了不会有连续的1出现所以接下来就和K1的时候一样了每次取走最低位的1直到结束。
k2的时候 犹如Fibonacci博弈我们首先要求一个数列将n分解成数列中一些项的和然后就可以按Fibonacci博弈的解决方法来完成也可以按二进制的方法来理解每次取掉最后一个1 还是符合上面的条件。
我们用a数组表示要被求的数列b数组中的b[i]保存 a[0…i] 组合能够构造的最大数字。这儿有点难理解所谓构造就是指n分解为Fib数相加的逆过程。举例说明当k 2 时a[N]{1, 2, 3, 5, 8, 13, 21, 33…} Fibonacci数组那么b[3] 即 1、2、 3 能够构造的最大数字答案是4有点匪夷所思或许你会问为什么不是5、6或者其它的什么其实是这样的 4 能分解成 13 是没有争议的但5能分解成23吗? 不能因为5本身也是Fibonacci数6虽然能分解但不是分解成123而是分解成15。
经过上述我们知道b[i] 是 a[0…i] 能够构造出的最大数字那么a[i 1] b[i]1因为a数组Fib数组所存的数字都是不可构造的取到它本身就是必败态显然a[0…i]构造的最大数字 1 即为下一个不可构造的数字了(a[i 1])。
然后关于b[i]的计算既然是a[0…i]构造最大数字那么 a[i]是一定要选用的这儿需要一定的推理a[i]构造数字时相邻的j个是不能同时用的就像上述的2、3不能构造出5一样推理请自己完成那么要选用的下一项只能递减寻找直到找到 a[t] 满足 a[t] * K a[i] 而b[t]就是a[0…t]所能构造的最大数字再加上a[i], 即为a[0…i]能构造的最大数字于是b[i] b[t] a[i]。
求得数列后之后的工作就简单了跟Fibonacci博弈一样一样的如果n数列中的数则必败否则必胜必胜时还要求输出第一步取法按照上文的理解将n分解之后选择最小的一个a[i]即可类似选择二进制的最小的1。
二威佐夫博弈
1.问题模型 有两堆各若干个物品两个人轮流从某一堆或同时从两堆中取同样多的物品规定每次至少取一个多者不限最后取光者得胜。
2.解决 设(ak,bk)(a_k,b_k)(ak,bk)(ak≤bk,k0,1,2,…,n)(a_k ≤ b_k,k0,1,2,…,n)(ak≤bk,k0,1,2,…,n)表示两堆物品的数量并称其为局势如果甲面对00那么甲已经输了这种局势我们称为奇异局势。前几个奇异局势是00、12、35、47、610、813、915、1118、1220。
如何找出所有的奇异局势? 下面证明根据下面的方法可以构造出所有的必败态 a. (0,0)是必败态。 b.第k个必败态的两个数相差为k记(0,0)为第0个必败态。 c. 已知前k个必败态则最小的没出现过的正整数为第k1个必败态的第一个数。 由构造方法可以推出奇异局势的下述三条性质 a.任何自然数都包含在一个且仅有一个奇异局势中。 由于aka_kak是未在前面出现过的最小自然数所以有akak−1a_k a_{k-1}akak−1 而 bkakkak−1k−1bk−1ak−1b_k a_k k a_{k-1} k-1 b_{k-1} a_{k-1}bkakkak−1k−1bk−1ak−1 。所以性质a成立。 b.任意操作都会将奇异局势变为非奇异局势。 事实上若只改变奇异局势(ak,bk)(a_k,b_k)(ak,bk)的某一个分量那么另一个分量不可能在其他奇异局势中所以必然是非奇异局势。如果使(ak,bk)(a_k,b_k)(ak,bk)的两个分量同时减少则由于其差不变且不可能是其他奇异局势的差因此也是非奇异局势。 c.采用适当的方法可以将非奇异局势变为奇异局势。 1.若ab,则同时从两堆中取走 a 个物体就变为了奇异局势(0,0) 2.若a!b不妨设ab (1)若aak且bbkaa_k且bb_kaak且bbk同时从两堆中取走ak−ab−aka_k-a_{b-a_k}ak−ab−ak个物体就变为了奇异局势(ab−ak,ab−akb−ak)(a_{b-a_k},a_{b-a_k}b-a_k)(ab−ak,ab−akb−ak) (2)若aak且bbkaa_k且bb_kaak且bbk从b堆中取走b−bkb-b_kb−bk个物品就变为了奇异局势(ak,bk)(a_k,b_k)(ak,bk) 求奇异局势的公式 ak⌊k(15)2⌋,bkakka_k\left\lfloor\dfrac{k(1\sqrt5)}{2}\right\rfloor,b_k a_kkak⌊2k(15)⌋,bkakk (k0,1,2,...,n)(k0,1,2,...,n)(k0,1,2,...,n)
结论 若(int)((bk−ak)∗15/2)!ak(int)((b_k-a_k) * 1\sqrt5/2) ! a_k(int)((bk−ak)∗15/2)!ak先手必赢 若(int)((bk−ak)∗15/2)ak(int)((b_k-a_k) * 1\sqrt5/2) ak(int)((bk−ak)∗15/2)ak后手必赢
三尼姆博奕
普通尼姆博弈
1.问题模型 有n堆各若干个物品两个人轮流从某一堆取任意多的物品规定每次至少取一个多者不限最后取光者得胜。
2.解决 结论记各堆物品个数分别为a1,a2,a3,...,ana_1,a_2,a_3,...,a_na1,a2,a3,...,an 若a1xora2xora3...xoran!0a_1\space xor\space a_2\space xor \space a_3...xor\space a_n ! 0a1 xor a2 xor a3...xor an!0先手必胜 若a1xora2xora3...xoran0a_1\space xor\space a_2\space xor \space a_3...xor\space a_n 0a1 xor a2 xor a3...xor an0先手必败
尼姆博弈的拓展
扩展形式1限定每次取物上限
1.问题模型 有n堆物品其中第i堆有pip_ipi个物品两人轮流从某一堆取走一些物品每次最多取走m个物品谁不能继续取谁就输了。
2.解决 结论令S为pip_ipi对m1取模后异或和的结果若S0则为P局面否则为N局面。
证明将pip_ipi分解为rir_iri和kik_iki其中 kik_iki为(m1)的倍数。如果对手在rir_iri内取物则按照Nim游戏的走法若不然假设A取x个那么B就取(m1-x)个使得游戏保持原有必胜态或必败态。
拓展形式2每次允许从k堆中取物Nimk问题
1.问题模型 有n堆物品其中第i堆有pip_ipi个物品两人轮流从k堆中选若干物品取走谁不能继续取谁就输了。
2.解决 结论我们把pip_ipi这n个数转成二进制然后每位分别相加每位和%(k1)即可。如果每一位结果都是0则为P局面否则为N局面。
扩展形式3规定取物方向阶梯Nim
1.问题模型 有 n堆石子每堆石子的数量为 x1,x2,...,xnx_{1},x_{2},...,x_{n}x1,x2,...,xn。A,B轮流操作每次可以选第 k 堆中的任意多个石子放到第 k-1 堆中第 1堆中的石子可以放到第 0堆中最后无法操作的人为输。
2.解决 结论先手必败当且仅当奇数阶梯上的石子数异或和为 0
拓展形式4不能继续取者赢Anti-Nim
1.问题模型 有n堆各若干个物品两个人轮流从某一堆取任意多的物品规定每次至少取一个多者不限最后取光者得输。
2.解决 结论 1.每一堆石子只有一个 且 异或和为0 2.存在至少一堆石子多于一个 且 异或和不为0 满足上述任意一个条件先手必胜
公平组合博弈ICG
1.定义 1两人参与。 2游戏局面的状态集合是有限。 3对于同一个局面两个游戏者的可操作集合完全相同 4游戏者轮流进行游戏。 5当无法进行操作时游戏结束此时不能进行操作的一方算输。 6无论游戏如何进行总可以在有限步数之内结束。
2.模型 给定一个有向无环图和一个起始顶点上的一枚棋子两名选手交替的将这枚棋子沿有向边进行移动无法移动者判负。事实上这个游戏可以认为是所有公平组合游戏Impartial Combinatori Games的抽象模型。其实任何一个ICG都可以通过把每个局势看成一个顶点对每个局势和它的子局势连一条有向边来抽象成这个“有向图游戏”。
SG函数与SG定理
1.SG函数Sprague-Grundy函数
首先定义mex(minimal excludant)运算这是施加于一个集合的运算表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}3、mex{2,3,5}0、mex{}0。
对于一个给定的有向无环图定义关于图的每个顶点的Sprague-Garundy函数SG如下SG(x)mex{SG(y)∣y是x的后继}SG(x)mex\{ SG(y) | y是x的后继\}SG(x)mex{SG(y)∣y是x的后继}。
SG函数性质 1所有的终结点所对应的顶点其SG值为0因为它的后继集合是空集——所有终结点是必败点P点。 2对于一个SG(x)0SG(x)0SG(x)0的顶点x它的所有后继y都满足SG(y)!0SG(y)!0SG(y)!0——无论如何操作从必败点P点都只能进入必胜点N点 3对于一个SG(x)!0SG(x)!0SG(x)!0的顶点必定存在一个后继点y满足SG(y)0SG(y)0SG(y)0——从任何必胜点N点操作至少有一种方法可以进入必败点P点
结论 当SG[x] 0时x为必败态。 当SG[x] 0时x为必胜态。
SG函数的求法
1可选步数为1-m的连续整数直接取模即可SG(x) x % (m1)(eg.Bash game);
2可选步数为任意步SG(x) x(eg.Nim game);
3通法用mex(计算每个节点的值) 。2.SG定理Sprague-Grundy定理
游戏和的SG函数等于各个游戏SG函数的Nim和。 这样就可以将每一个子游戏分而治之从而简化了问题。 而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用因为单堆的Nim游戏 SG函数满足 SG(x)xSG(x) xSG(x)x。
三类特殊的SG游戏
Anti-SG游戏
1.定义 Anti-SG游戏规定决策集合为空的游戏者赢。其他规则与SG游戏相同。
2.SJ定理 对于任意一个Anti-SG游戏如果我们规定当局面中所有的单一游戏的SG值为0时游戏结束则先手必胜当且仅当 1游戏的SG函数不为0 且 游戏中某个单一游戏的SG函数大于1。 2游戏的SG函数为0 且 游戏中没有单一游戏的SG函数大于1。
注意如果所有单一游戏SG值都为0而游戏还未结束的话SJ定理是不适用的。
Multi-SG游戏
1.定义 Multi-SG游戏规定在符合拓扑原则的前提下一个单一游戏的后继可以为多个单一游戏其他规则与SG游戏相同。
2.定理Multi-SG游戏的仍然可以用SG函数来定义局面。
注意区分后继以及多个单一游戏 对于一个状态来讲 不同的划分方法会有多个不同的后继 而在一个后继当中会有多个独立的游戏 该后继状态SG值即为后继状态中独立游戏的异或和 该状态的SG值即为后继状态的mex
Every-SG游戏
1.定义 Every-SG游戏规定对于还没有结束的单一游戏游戏者必须对该游戏进行一步决策其他规则与SG游戏相同。
2.定理 step函数step函数step函数 在通过拓扑关系计算某一个状态点的SG函数时对于SG值为0的点我们需要知道最快几步能将游戏带入终止状态对于SG值不为0的点我们需要知道最慢几步游戏会被带入终止状态我们用step函数表示这个值。
Every−SG定理Every-SG定理Every−SG定理 对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。
经典的SG组合游戏
1“翻硬币”游戏
2图游戏模型
3无向图的删边游戏
4Shannon开关游戏
5其他题目
不平等的组合游戏
