博弈论进阶之SG函数

SG函数

个人理解:SG函数是人们在研究博弈论的道路上迈出的重要一步,它把许多杂乱无章的博弈游戏通过某种规则结合在了一起,使得一类普遍的博弈问题得到了解决。

从SG函数开始,我们不再是单纯的同过找规律等方法去解决博弈问题,而是需要学习一些博弈论中基本的定理,来找到他们的共同特点

那么就先介绍几个最基本的定理(也可以叫常识)吧

基本定理

ICG游戏

1.游戏有两个人参与,二者轮流做出决策。且这两个人的决策都对自己最有利。

2.当有一人无法做出决策时游戏结束,无法做出决策的人输。无论二者如何做出决策,游戏可以在有限步内结束。

3.游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关。

满足上述条件的问题我们称之为ICG游戏,ICG游戏属于组合游戏

最典型的nim游戏,就是一种ICG游戏

必胜态与必败态

定义P-position与N-position

P-position:必败态(简记为P),即Previous-position,你可以直观的认为处于这种状态的人一定会输

N-position:必胜态(简记为N),即Next-position,你可以直观的理解为处于这种状态的人一定会赢

这仅仅是最直观的定义

更严谨的定义为:

  1. 无法移动的状态(即terminal-position)为P
  2. 可以移动到P的局面为N
  3. 所有移动都会进入N的局面为P

DAG(有向无环图)中的博弈

在正式研究SG函数之前,我们先来研究一下DAG中的博弈

给定一张有向无环图,在起始定点有一枚棋子,两个顶尖聪明的人交替移动这枚棋子,不能移动的人算输

不要小看这个游戏,事实上,所有ICG问题都可以抽象为这种游戏(即把初始局面看做顶点,把从一个状态可以到另一个状态之间连边)

SG函数

下面我们来正式研究一下SG(Sprague-Grundy)函数

首先定义mex运算,这是一种集合中的运算,它表示最小的不属于集合的非负整数

例如mex\{1,2,3\}=0mex\{0,2\}=1mex\{0,1,2,3\}=4mex\{\}=0

对于给定的有向无环图,定义每个点的SG函数为

SG(x)=mex \{\ SG(y)\ |\ x \ can\ go\ to\ y \}

然而单单一个这样的空洞的函数是解决不了问题的,我们需要分析一下它的性质

  • 所有汇点的SG函数为0

这个性质比较显然,因为汇点的所有后继状态都是空集

  • SG(x)=0时,该节点为必败点

由SG函数的性质易知该节点的所有后继节点SG值均不为0

满足必败态的定义

  • SG(x)\neq 0 ,该节点为必胜点

由SG函数的定义可知该节点的后继节点中一定有一个节点SG=0

满足必胜态的定义

这样我们通过最基本的\(SG\)值的定义,我们就可以判断出一个状态是必胜态还是必败态

这个问题实际上就是我们前面讲的巴什博奕

如果这个问题再复杂一点呢?

当这个棋盘上有n个棋子的时候呢?

其实它们的分析思路是一样的

SG(x)=k时,它表明后继状态中含有SG(y)=1 \dots k-1

也就是说,我们从k可以转移到1 \dots k-1中的任何一个状态,而当前共有n个棋子。

这会让你想到什么?

nim取石子游戏!

那我们是不是也可以推出:

如果在nim游戏中的n堆石子的SG值异或和不为0就说明先手必胜呢?

这是肯定的,因为当你打出nim游戏的SG值表时就会发现,SG_{nim}(x)=x

是不是很神奇?

SG定理

SG函数的应用远远不止和巴什博奕与nim游戏有关,我们回过头来考虑能否把SG函数推广开来

类比nim取石子游戏的思路,我们可不可以大胆设想:

游戏的和的SG值是他们的SG值的xor

暂且不管这个结论对不对,我们设想一下,假如这个结论对的话,会有什么后果.

我们可以将ICG问题对应到DAG上,然后直接通过SG函数之间的转移而解决几乎全部的问题

是不是很令人兴奋?

更令人兴奋的是,这个定理是正确的!

什么?证明?

SG定理的应用

SG定理的应用非常的广泛,几乎所有的博弈类问题都有它的影子,本文仅仅是简单的介绍一下这个定理,更深层次的应用以后会补充的

上面提到了SG函数,那么SG函数的值是怎么计算的呢?

很简单,我们直接通过mex运算的定义就可以计算了

int F[MAXN];//可以转移的状态集合,一般题目会给出 
int S[MAXN];//表示该点可以转移到的状态有哪些 
int SG[MAXN];//该点的SG值 
void GetSG()
{
    for(int i=1;i<=N;i++)//枚举DAG中所有点 
    {
        memset(S,0,sizeof(S));//初始化
        for(int j=1;j<=limit&&F[j]<=i;j++)//limit表示转移的集合的大小
            S[SG[i-F[j]]]=1; 
        for(int j=1;;j++)
            if(!S[j])
                {SG[i]=i;break;}//根据定义计算SG函数 
    }
}

来一道裸题

题解

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏后端技术探索

算法之经典背包问题分析与实例

我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,...

951
来自专栏灯塔大数据

每周学点大数据 | No.3算法设计与分析理论

No.3期 算法设计与分析理论 在计算机科学中,研究算法的设计和评价算法“好坏”的分支,称为算法设计与分析理论。它研究如何去设计解决问题的算法,同时给出一个对...

30010
来自专栏racaljk

博弈之最大-最小搜索算法

最近正在做一个人工智能的中国象棋,所以不可避免的接触到了博弈论,因为考虑到以后还会有所涉及 (alpha-beta search),所以写成了一片文章

4412
来自专栏专知

【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

3027
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 群落

说到群落,很难不引用Craig Reynolds和他的"boilds"模拟系统。Reynolds很牛的将一个看似非常恐怖的复杂过程,拆成了几个比较简单的行为。 ...

2248
来自专栏牛客网

微软阿里实习面经(offer)微软三面阿里面试(6面)

8930
来自专栏hadoop学习笔记

Hanlp自然语言处理工具的使用演练

Hanlp是由一系列模型与算法组成的工具包,目标是普及自然语言处理在生产环境中的应用。Hanlp具备功能完善、性能高效、架构清洗、语料时新、可自定义的特点;提供...

1992
来自专栏ACM算法日常

新手ACM算法学习建议

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功。ACM主要是考算法的,主要时间是花在思考算法上,不是花在写程序与debug上。

1723
来自专栏小樱的经验随笔

ECJTUACM16 Winter vacation training #1 题解&源码

//寒假训练赛,第一次拿第一,感觉很爽哦,AC3题! A----------------------------------------------------...

2775
来自专栏新智元

邓侃:谷歌Talk to books引爆搜索方式革命

?---- 【新智元导读】昨天,新智元介绍了谷歌的全新搜索工具“Talk to Books”,基于自然语言文本理解,用户能够凭语义而非关键词来实现搜索功能。谷歌...

2926

扫码关注云+社区

领取腾讯云代金券