博弈论-SG函数笔记

快来打我* 2022-01-05 09:13 237阅读 0赞

> **例一：**给定n堆物品，第 i 堆物品有 Ai 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采用最优策略，问先手能否获胜。

# 1.概念 #

**1.1 局面：**游戏过程中面临的状态称为局面。

**1.2 先手与后手：**整局游戏第一个行动的称为**先手**，第二个行动称为**后手**。

**1.3 最优策略：**若在某一局面下存在某种行动，使得行动后对手面临**必败局面**，则**优先采取**该行动。同时，这样的局面称为**必胜**。

# 2.NIM博弈 #

**2.1 结论：**NIM博弈不存在平局，只有**先手必胜**和**先手必败**两种情况。

**2.2 定理：**NIM博弈先手必胜，**当且仅当** A1 xor A2 xor A3 xor ... xor An != 0。

**2.3 证明：**待补充

# 3.公平组合游戏ICG #

**3.1 定义：**若一个游戏满足：

1.  由两名玩家交替行动。
2.  在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
3.  不能行动的玩家判负。

**3.2 解法：**公平组合游戏（ICG）可以用构造函数的方法来求解局面。难点在于如何对每种ICG都构造一个合适的函数，有没有一个普适的函数？SG函数解决了这个问题。

# 4.有向图游戏 #

**4.1 定义：**给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为**有向图游戏**。

**4.2 推广：**任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面沿着合法行动能够到达的下一个局面连有向边。

# 5.Mex运算 #

**5.1 定义：**设 S 表示一个非负整数合计。定义mex(S) 为求出**不属于**集合 S 的**最小非负整数**的运算，即

**     mex( S )  = min\{x|x 属于 N，x不属于S\}**

# 6.SG函数 #

**6.1 定义：**在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1,y2 , ... yk ，定义SG(x) 为 x 的后继节点y1,y2,...yk的SG函数值构成的集合再执行mex运算的结果，即：

SG(x) = mex( \{ SG(y1) , SG(y2) , ... , SG(yk) \} )

特别的，整个有向图游戏 G 的 SG 函数值被定义为有向图游戏起点 s 的 SG 函数值，即SG(G) = SG(s)。

**6.2 有向图游戏的和：**设G1 , G2 , ... , Gm是 m 个有向图游戏。定义有向图游戏 G ，它的行动规则是人选某个有向图游戏 Gi，并在 Gi 上行动一步。G 被称为有向图游戏 G1 , G2 , ... ,Gm 的和。

> 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：SG( G ) = SG(G1) xor SG(G2) xor ... xor SG(Gm)。

**6.3 定理：**

*  有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值大于0.
 *  有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0.

**6.4 证明：**[我的能力写不出来，参考别人的吧][Link 1]

转载于:https://www.cnblogs.com/long98/p/10352159.html

[Link 1]: https://fancydreams.ink/2018/11/06/%E9%9A%8F%E4%BE%BF%E6%90%9E%E6%90%9E-icg-%E5%85%AC%E5%B9%B3%E7%BB%84%E5%90%88%E6%B8%B8%E6%88%8F/3/

发表评论取消回复

表情：

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

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

相关阅读

相关初识博弈论(个人笔记)

博弈的基本要素:参与人、策略空间、信息、结果与得失完全信息,指信息对于局中人来说是完全公开的不完全信息,不仅指绝对意义上的不完全,有可能是认识能力的限制均衡:

╰半橙微兮°/ 2024年03月23日 13:33/ 0 赞/ 28 阅读

相关博弈论总结四大博弈模型 SG函数

一、博弈论 1、博弈论是什么博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。 2、平等博弈在我们平时做题碰见的博弈都是平

小鱼儿/ 2022年12月02日 00:56/ 0 赞/ 233 阅读

相关 Acwing 893：集合Nim游戏（博弈论 sg函数）

题目链接传送门：[Acwing 893：集合Nim游戏][Acwing 893_Nim] 题目大意先给定一个集合s，有k个元素。然后有n堆石子，每堆分别有 h

心已赠人/ 2022年09月14日 09:19/ 0 赞/ 138 阅读

相关博弈之sg函数（模板）

组合博弈的通解就是sg函数，学习了sg函数之后一直没有咋用过。学习博弈的可以在nyoj上面做10道取石子题目，作为了对博弈也就有一定理解了。用的时候注意初始的时候只要初

亦凉/ 2022年08月26日 00:41/ 0 赞/ 148 阅读

相关 uva 10561 Treblecross (SG函数)

uva 10561 Treblecross (SG函数) ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=113

灰太狼/ 2022年08月21日 07:47/ 0 赞/ 80 阅读

相关 Game of Hyper Knights （SG函数）

Game of Hyper Knights （SG函数）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112

谁借莪１个温暖的怀抱￠/ 2022年07月29日 11:43/ 0 赞/ 101 阅读

相关 Partitioning Game (SG函数)

Partitioning Game ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\problem

喜欢ヅ旅行/ 2022年07月28日 12:38/ 0 赞/ 134 阅读

相关 SG定理与SG函数(模板)

必胜点和必败点： P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。 N点：必胜点，处于此情况下，双方操作均正确的情况下

妖狐艹你老母/ 2022年06月11日 09:13/ 0 赞/ 153 阅读

相关组合博弈游戏 - SG函数和SG定理

转载来自：http://blog.csdn.net/luomingjun12315/article/details/45555495 在介绍SG函数和SG定理之前我们先介绍介

不念不忘少年蓝@/ 2022年06月08日 03:48/ 0 赞/ 166 阅读

相关博弈论-SG函数笔记

> 例一：给定n堆物品，第 i 堆物品有 Ai 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采用最优策略，

快来打我*/ 2022年01月05日 09:13/ 0 赞/ 238 阅读