博弈论进阶之Anti-SG游戏与SJ定理

前言

在之前,我们初步了解了一下SG函数与SG定理。

今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理

首先从最基本的Anti-Nim游戏开始

Anti-Nim游戏是这样的

有两个顶尖聪明的人在玩游戏,游戏规则是这样的: 有n堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),拿走最后一个石子的人失败。问谁会胜利

博弈分析

Anti-Nim游戏与Nim游戏唯一的不同就是两人的胜利条件发生了改变,不过这并不影响我们对结论的推导

对于这个游戏,先手必胜有两种情况

  • 堆石子都只有一个,且游戏的SG值0
  • 至少一堆石子多于一个,且游戏的SG值不为0

粗略的证明一下

游戏大概可以被分为3种情况

  • 每堆只有一个石子
  • 当异或值为0时,先手必胜
  • 当异或值不为0时,先手必败
  • 只有一堆石子数大于1,先手必胜

经过分析不难发现,先手可以对数量大于1的那堆石子下手脚,从而构造出后手必败的状态

  • 存在至少两堆石子数大于1
  • 当异或和为0时,先手必败
  • 当异或和不为0时,先手必败

这一步的结论与Nim游戏非常相似,同时它们的证明也非常相似,大概就是从异或和为\(0\)的状态无论怎样都会变为异或和不为0的状态,反过来从异或和不为0的状态总有一步能到达异或和为\(0\)的状态

推广

按照我们学习SG函数的思路,我们是否可以把Anti-Nim游戏推广开来呢?

答案是肯定的

定义Anti-SG游戏

  • Anti-SG游戏规定:决策集合为空的游戏者赢
  • 其余规则与SG游戏相同

同时我们定义SJ定理

对于Anti-SG游戏,如果我们规定当局面中所有单一游戏的SG值为0时,游戏结束,则先手必胜当且仅当

  • 游戏的SG函数不为0且游戏中某个单一游戏的SG函数值大于1

  • 游戏的SG函数为0且没有某个单一游戏的SG函数大于1

证明与SG函数类似,

不追求完美的可以从DAG上归纳

追求完美的可以用模仿棋证明出该游戏的等价性然后推出该游戏是可数集合然后通过计算推出在模2意义下线性空间的基可以为nim(0),nim(1)最后归纳证明一个后继是若干Anti-nim游戏的游戏等价于mex(S)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

杯子倒水问题自动求解程序(Javascript实现)

智力测试题经常遇到类似的逻辑题,给几个容量不等的杯子,让你倒出多少的水。 安卓上有一款专门玩这个题的游戏叫做Water Logic. ? 我安装这个游戏把几十个...

33430
来自专栏PPV课数据科学社区

【学习】50+数据科学与机器学习速查表

关于Python、R和Numpy、Scipy以及Pandas的速查表 有了这些和R语言、python、Django、MySQL、SQL、Hadoop、Apach...

39350
来自专栏全栈工程师成长之路

2017计算机系书单推荐

我是一名iOS开发工程师,我想成为一名优秀的程序员,我虽然不是计算机系的学生,但我不能落后,我要努力成为优秀程序员的一员。我觉得每个人都有自己的想法和规划,一个...

718100
来自专栏程序员笔记

我的第一个游戏:GetMessage

17340
来自专栏ACM算法日常

Facebook面试官:如何突围大厂算法面试?

“给你a、b两个文件,他们各存放50亿条URL,其中每条URL各占用64字节,内存限制是4G,请你编写代码找出a、b文件中相同的URL”。这是某家大公司在201...

24720
来自专栏灯塔大数据

深度|Python股票数据分析

最近在学习基于python的股票数据分析,其中主要用到了tushare和seaborn。 python版本:3.4 tushare是一款财经类数据接口包,国...

75060
来自专栏大数据文摘

用Python也能进军金融领域?这有一份股票交易策略开发指南

60440
来自专栏数据科学与人工智能

【数据科学】50+数据科学与机器学习速查表

关于Python、R和Numpy、Scipy以及Pandas的速查表 有了这些和R语言、python、Django、MySQL、SQL、Hadoop、Apach...

25270
来自专栏大数据挖掘DT机器学习

Python股票数据分析

python版本:3.4 最近在学习基于python的股票数据分析,其中主要用到了tushare和seaborn。tushare是一款财经类数据接口包,国内的...

79180
来自专栏灯塔大数据

每周学点大数据 | No.44 MapReduce 图算法概述

No.43期 MapReduce 图算法概述 Mr. 王:MapReduce 作为一种经典的并行编程框架,可以用于解决很多问题,包括一些图论问题。在客观世界...

38550

扫码关注云+社区

领取腾讯云代金券