博弈论进阶之Every-SG

Every-SG

给定一张无向图,上面有一些棋子,两个顶尖聪明的人在做游戏,每人每次必须将可以移动的棋子进行移动,不能移动的人输

博弈分析

题目中的要求实际是“不论前面输与否,只要最后一个棋子胜利,那么就算胜利”

这样的话,能赢得游戏必须赢

因为两个人都顶尖聪明,因此当一个人知道某一个游戏一定会输的话,它一定会尽力缩短游戏的时间,当它知道某一个游戏一定会赢的话,一定会尽力延长游戏的时间(毕竟都是为了追求最终的胜利嘛233)

但是!我们怎么来处理时间的?暴力枚举博弈树肯定是不可取的,so我们来研究一下这个问题

定义Every-SG游戏

  • 对于还没有结束的单一游戏,游戏者必须对该游戏进行一步决策;
  • 其他规则与普通SG游戏相同

Every-SG游戏与普通SG游戏最大的不同就是它多了一维时间

对于SG值为0的点,我们需要知道最少需要多少步才能走到结束, 对于SG值不为0的点,我们需要知道最多需要多少步结束

这样我们用step变量来记录这个步数

定理

对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。

定理是显然的:最大的单一游戏步数如果是奇数的话那么肯定是先手取得进行最后一步,否则一定是对手取走最后一个棋子。

例题

这种题目不怎么好找,到现在也就找到一道

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯开源的专栏

腾讯公司副总裁曾宇:技术必须产生价值,开源需要携手发展

共同探讨、交流云计算开源技术及产业化经验,探索开源技术创新的发展途径。

2.9K80
来自专栏架构师小秘圈

电商系统中的商品模型的分析与设计

作者:李平,目前在一家O2O互联网公司从事设计、开发工作。业余时间喜欢跑步、看书、游戏。 来自:cnblogs.com/leefreeman/p/4060227...

67250
来自专栏玩转JavaEE

一个开源的五子棋大战送给各位小伙伴!

有暇,做了个五子棋大战的小游戏送给各位小伙伴! 用到的知识点有: 1.JavaWeb基础知识(懂jsp,servlet足够) 2.JavaScript和jQue...

59150
来自专栏数据结构与算法

08:石头剪刀布

08:石头剪刀布 总时间限制: 1000ms 内存限制: 65536kB描述 石头剪刀布是常见的猜拳游戏。石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,...

52070
来自专栏IT大咖说

Connecting People ---- 独乐乐 不如众乐乐

摘要 io游戏大致是指具有多人对抗+地图限制+死后即刻复活等为特点的休闲moba类竞技游戏,在近几年内发展迅速。 ? io&HTML5 HTML5这个领域在过去...

37570
来自专栏IT大咖说

网科巨力部门经理杨彪:优化游戏体验与托管成本

嘉宾演讲视频 Guest Video ? 温馨提示 本视频时长11分44秒,建议在wifi下观看 手游市场可谓“你方唱罢我登场”, 从2016年9月份上线以来,...

29450
来自专栏数据结构与算法

3145 汉诺塔游戏

3145 汉诺塔游戏  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver  查看运行结果 题目描述 Description...

40170
来自专栏架构师小秘圈

面试官最讨厌的三种求职者

职场人士在职业职业生涯中一定会面临求职和面试,想要面试过关需要三个条件:职业技能达标、问题回答得体、不犯致命错误。前两点很好理解,我们来看看第三个,面试过程中...

37660
来自专栏灯塔大数据

打破比特币!!!

导读:上一期了解了关于区块链技术应用到游戏的相关介绍,今天我们来了解一下关于比特币相关的法律问题的相关内容(文末更多往期译文推荐) 据德国的比特币研究机构称,...

38490
来自专栏数据结构与算法

04:石头剪子布

04:石头剪子布 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 ...

46380

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励