贾志豪组合游戏论文个人总结（Anti-SG，Every-SG，翻硬币游戏，无向图删边）

曾经终败给现在 2022-06-10 04:00 235阅读 0赞

今天看了一下午贾志豪的《组合游戏略述——浅谈SG游戏的若干拓展及变形》，真的是一篇非常优秀的论文，感觉自己又掌握了很多，给出链接https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html

在这里我只总结一下我不太熟悉的四个点，Anti-SG，Every-SG，翻硬币游戏和无向图删边游戏。

1，Anti-NIM

定义：   1，桌上有N堆石子，游戏者轮流取石子。

2，每次只能从一堆中取出任意数目的石子，但不能不取。

3，取走最后一个石子者败。

结论：   先手必胜当且仅当

1，所有堆的石子数目都为1且游戏的SG值为0。

2，有些堆的石子数目大于1且游戏的SG值不为0。

Anti-SG

定义：    1，Anti-SG游戏规定，决策集合为空的游戏者赢。

2，Anti-SG其他规则与SG游戏相同。

结论：    SJ定理：

对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏

的SG值为0时，游戏结束，则先手必胜当且仅当：

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

2，游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

\*\*\*\*\*\*\*这里的SG值和普通SG游戏的SG值含义相同\*\*\*\*\*\*\*\*\*\*\*

2，Every-SG

定义：    1，Every-SG 游戏规定，对于还没有结束的单一游戏，游戏者必须对该游

戏进行一步决策，也就是每轮操作要对所有单一游戏进行操作。

2，Every-SG 游戏的其他规则与普通SG游戏相同。

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

在通过拓扑关系计算某一个状态点的SG函数时，对于SG值为0的点，我们

需要知道最快几步能将游戏带入终止状态，对于SG值不为0的点，我们需

要知道最慢几步游戏会被带入终止状态，我们用step函数来表示这个值。

![Center][]

3，翻硬币游戏

定义：1，N枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开始对硬币按1                  到N编号。

2，游戏者根据某些约束翻硬币，但他所翻动的硬币中，最右边的必须是从正                        面翻到反面。

3，谁不能翻谁输。

结论：局面的SG值为局面中每个正面朝上的棋子单一存在时的SG值的异或和。

4，树的删边游戏

定义：1，给出一个有N个点的树，有一个点作为树的根节点。

2，游戏者轮流从树中删去边，删去一条边后不与根节点相连的部分被移走。

3，谁无边可删谁输。

结论：叶子节点的SG值为0，中间节点的SG值为它的所有子节点的SG值加1后的异                   或和。

无向图的删边游戏

定义：1，一个无向连通图，有一个点作为图的根。

2，游戏者轮流从图中删去边，删去一条边后不与根节点相连的部分被移走。

3，谁无边可删谁输。

结论：我们可以对无向图做如下改动，将图中任意一个偶环（边数是偶数的环）缩                     成一个新点，任意一个奇环缩成一个新点加一个新边，所有连到原先环上的                     边全部改为与新点相连，这样的改动不会影响到图的SG值。然后无向图就变                   成了一棵树。

[Center]: /images/20220610/1a9d22ef38c84efaada9483013c7fd15.png

发表评论取消回复

表情：

评论列表（有 0 条评论，235人围观）

还没有评论，来说两句吧...

相关阅读

相关翻硬币游戏

[【转】博弈-翻硬币游戏][-] 翻硬币游戏一般的翻硬币游戏的规则是这样的： N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开始对硬币

r囧r小猫/ 2023年10月11日 09:37/ 0 赞/ 44 阅读

相关 08-翻金币游戏

mianscene类：游戏的开始界面 mypushbutton类：为开始按钮和返回按钮封装的无边框的按钮控件 chooselevelscene类：选择游戏关卡的界面 pl

- 日理万妓/ 2022年12月17日 07:14/ 0 赞/ 151 阅读

相关公平组合游戏-巴什游戏、尼姆游戏和SG函数

文章目录公平组合游戏巴什游戏 HDU-1846 尼姆游戏 HDU-1850 HDU-1907 SG函数

绝地灬酷狼/ 2022年12月11日 15:13/ 0 赞/ 197 阅读

相关矩阵翻硬币

问题描述　　小明先把硬币摆成了一个 n 行 m 列的矩阵。　　随后，小明对每一个硬币分别进行一次 Q 操作。　　对第x

ゝ一世哀愁。/ 2022年08月21日 05:44/ 0 赞/ 187 阅读

相关 CSU----E: 删数游戏

ACM小组喜欢上了一个无聊的游戏，游戏的过程是输入一个正整数n，去掉n的任意S个数字后，把剩下的数字看作是一个新的整数（去除前导零）。对给定的N和S，寻找一种删数规则使得剩下的

「爱情、让人受尽委屈。」/ 2022年06月14日 02:37/ 0 赞/ 184 阅读

相关贾志豪组合游戏论文个人总结（Anti-SG，Every-SG，翻硬币游戏，无向图删边）

今天看了一下午贾志豪的《组合游戏略述——浅谈SG游戏的若干拓展及变形》，真的是一篇非常优秀的论文，感觉自己又掌握了很多，给出链接https://wenku.baidu.com/

曾经终败给现在/ 2022年06月10日 04:00/ 0 赞/ 236 阅读

相关无向图的动态规划——硬币问题

> 题目描述： > 硬币找零问题描述：现存在一堆面值为 V1、V2、V3 … 个单位的硬币 > 问最多和最少需要多少个硬币才能找出总值为T个单位的零钱？ > 输入：

以你之姓@/ 2022年05月08日 12:36/ 0 赞/ 254 阅读

相关敏捷游戏：从硬币游戏学习Scrum敏捷方法

![2010082518002249.png][]本文转自 http://www.zhoujingen.cn/blog/6381.html ------------

今天药忘吃喽~/ 2021年12月14日 01:17/ 0 赞/ 411 阅读

相关【题解】删数游戏

题目描述输入一个高精度的正整数n（≤240位），去掉其中任意s个数字后，剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得

川长思鸟来/ 2021年11月11日 03:58/ 0 赞/ 380 阅读

相关博弈-Green Hackenbush(删边游戏,《Game Theory》译文)

转自:[http://blog.sina.com.cn/s/blog\_8f06da990101252l.html][http_blog.sina.com.cn_s_blog_

向右看齐/ 2021年09月15日 21:50/ 0 赞/ 589 阅读