[关闭]
@xzyxzy 2018-08-04T09:36:16.000000Z 字数 2923 阅读 1035

博弈

数学

作业部落

评论地址


前言

本博文分三部分,第一部分简单介绍SG函数,第二部分简单介绍博主所理解的一些博弈模型,第三部分推荐题目以及分享做题心得,本文基本不适合初学者食用,初学者请移步下方链接

论文:2009贾志豪(百度文库可搜)
自为风月马前卒的总结
自为风月马前卒的题目

Part1 SG函数

优势:可以实现对多个游戏进行加和
计算方式,其中指集合中最小没有出现过的自然数,的后继状态
游戏加和
意义表示先手必败,为P状态,否则为N状态,先手必胜
理解:化为游戏,对于每个不为的状态总有一种方案使得成为

Part2 平等博弈模型

1.巴什博弈(Bash Game)

问题:只有一堆个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取个。最后取光者得胜
结论先手必败否则必胜

2.威佐夫博弈(Wythoff Game)

问题:有两堆各若干个物品,两个人轮流同时从一到两堆中取同样多的物品,规定每次至少取一个,最后取光者得胜
结论
先手必败态的两堆石子之差依次递增,且每个自然数仅出现一次,先手必败态为
如果必败态为,则

3.尼姆博弈(Nim Game)

问题堆石子两人轮流在任意一堆中取任意石子,不能不取,最多取完,取到最后一颗石子者胜
结论堆石子数量异或和为则先手必败否则必胜
Nim游戏代表了所有平等博弈问题!!

4.Nim 游戏扩展

问题:每次最多丢个石子,其余规则同
结论:每堆石子数量后再求异或和

5.Nim k 博弈

问题:一次最多在堆中取,其余规则同
结论:把石子数二进制拆开,每位求和后,若最后每位都为则先手必败,否则先手必胜

6.阶梯博弈

问题:有堆石子放在层阶梯上,两人轮流选择一层的若干石子,放入下一层(特别地,选择层的石子就被扔掉),无法操作者输
结论:奇数层石子的数量异或和为则先手必败否则必胜

7.Anti-SG(反Nim游戏)

问题:取走最后一颗石子者败,其余规则同
结论
当且仅当以下情况先手必胜
1.整个游戏并且没有单一游戏
2.整个游戏并且至少一个单一游戏
通过下图来理解(QAQ之前画错了,更严谨证明请见贾志豪的论文)

8.Multi-SG

问题
结论

9.Every-SG

问题
结论

10.翻硬币游戏

问题:正反硬币排成一排,每次可以翻转一段区间,要求左端点必须由反面翻成正面,不能操作者输,求是否先手必胜
结论:每个位置上的硬币独立,分别算后异或起来

11.树上删边游戏

问题:一个有根树,一次操作是选择一条边,删除此边以及删掉边后和根不连通的部分,不能操作者输
结论
表示为的子树内所有点的值的集合
或者是,等价为链再化为游戏即可证明

12.无向图删边游戏

问题
结论

13.动态减法问题

问题:有一个整数,双方轮流减去一个正整数值,第一次不能减完,之后每次减的数不超过表示为上一次减的值(保证单调不降)
结论
表示第个先手必败的状态,找到最小的使得,则
通过这个结论可以快速解决必败状态是必败状态是斐波那契数列
证明看下我的草稿本哈:

14.匹配的应用

问题:无向图中棋子在,双方轮流操作,选一条边走出去并且把之前的结点删去,不能行动者输
结论:先手必胜要求在图中的任意最大匹配中

Part3 做题心得

1.一排石子两头取的问题

描述1

CodeForces 794E Choosing Carrot
一行数依次选择左边或右边的数丢掉,先手想要留下的数最大,后手反之,求最终留下的数

结论1

如果为偶数,留下的是正中间两个数的
如果是奇数(),假设正中间三个数为,则留下的为

附录:题单

论文:2009贾志豪
自为风月马前卒总结:http://www.cnblogs.com/zwfymqz/tag/%E5%8D%9A%E5%BC%88%E8%AE%BA/
自为风月马前卒题目:http://www.cnblogs.com/zwfymqz/category/1019908.html

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注