栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【学习笔记】NIM游戏与SG函数初探

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【学习笔记】NIM游戏与SG函数初探

公平组合游戏ICG 游戏条件介绍:
  1. 由两名玩家交替行动
  2. 游戏进程的任意时刻,可以执行的合法行动与轮到的玩家无关
  3. 若当前玩家无法行动,则判负

则称该组合游戏为公平组合游戏。如NIM游戏等即是经典的公平组合游戏。而许多游戏虽然形式上与公平组合游戏相差较大,但可以等价转为公平组合游戏。而如围棋等不是公平组合游戏。如交战中一方仅可以落白子,而另一方仅可以落黑子,操作与所在身份有关;同时胜负的判定也比较复杂,不满足条件3。因此围棋不是公平组合游戏。

进一步理解

对于第三条,我们有更进一步的定义Position,我们将Position分为两类:

  1. P-position:在当前的局面下,先手必败

  2. N-position:在当前的局面下,先手必胜

它们有如下性质:

  1. 合法操作集合为空的局面是P-position

  2. 可以移动到P-position的局面是N-position

  3. 所有移动都只能到N-position的局面是P-position

按照这个定义,如果局面不能重现,或者说不同局面之间存在着拓扑排序的关系,那么对游戏中的所有局面,要么为P局面,要么为N局面,同时可以使用定义依据拓扑顺序进行计算。

NIM游戏 定义

NIM游戏的经典定义是:给定n个石堆,每一个石堆的数目为 A i A_i Ai​,游戏双方轮流行动,每一个人只能选定一个非空石堆取走一定数目的石子,当某一个人没有石子可取时判定为负。问给定所有石堆数目,是否存在先手必胜局面。

一般思路

由NIM游戏的性质可以发现其满足ICG游戏的要求,因此存在着P局面与N局面。例如存在着三堆石子,则数目为 ( 0 , 0 , 0 ) (0,0,0) (0,0,0)时是必败局面,则当数目为 ( 1 , 0 , 0 ) / ( 0 , 1 , 0 ) / ( 0 , 0 , 1 ) (1,0,0)/(0,1,0)/(0,0,1) (1,0,0)/(0,1,0)/(0,0,1)时,由于可以转移到 ( 0 , 0 , 0 ) (0,0,0) (0,0,0)这个必败局面,因此三者均是必胜局面。

由上述分析可知,对于每一个局面,我们都可以通过枚举其可以转移的局面进行搜索,从而根据每一个局面的后继局面状态得到当前局面是必胜还是必败。

实现代码如下:

bool calc(int a[], int n)
{
    bool flag = false;
    for( int i = 1; i <= n; i++ )
    {
        if(a[i] > 0)
        {
            for( int j = 1; j <= a[i]; j++ )
            {
                a[i] = a[i] - j;
                flag |= !calc(a, n);//当后继局面有必败,则当前局面必胜
                a[i] = a[i] + j;
            }
        }
    }
	return flag;
}

上述搜索使用记忆化搜索时,时间复杂度为 O ( ∏ A i ) O(prod A_i) O(∏Ai​)。

进一步优化

NIM游戏先手必胜,当且仅当 A 1   x o r   A 2   x o r   A 3   x o r . . . A n ≠ 0 A_1 space xor space A_2 space xor space A_3 space xor...A_nne0 A1​ xor A2​ xor A3​ xor...An​​=0。

证明:使用数学归纳法进行证明。

当所有石堆为空,则当前是必败局面,则 A 1   x o r   A 2   x o r   A 3   x o r . . . A n = 0 A_1 space xor space A_2 space xor space A_3 space xor...A_n=0 A1​ xor A2​ xor A3​ xor...An​=0。

当 A 1   x o r   A 2 . . . A n ≠ 0 A_1 space xor space A_2 ...A_nne0 A1​ xor A2​...An​​=0,设 v a l = A 1   x o r   A 2   x o r   A 3 . . . A n val = A_1 space xor space A_2 space xor space A_3...A_n val=A1​ xor A2​ xor A3​...An​,则设 v a l val val不为0的最高位为第 k k k位,则在 A 1 A_1 A1​到 A n A_n An​中必定存在 A i A_i Ai​的第 k k k位为1,且 A i   x o r   v a l < A i A_ispace xorspace val < A_i Ai​ xor val

当 A 1   x o r   A 2   x o r   A 3   x o r . . . A n = 0 A_1space xorspace A_2space xorspace A_3space xor...A_n=0 A1​ xor A2​ xor A3​ xor...An​=0,则无论如何取石子,都不可能使得所有石子异或和为0。不妨使用反证法证明上述观点,若取了第 i i i堆石子之后由 A i A_i Ai​变为 a i a_i ai​且 A 1   x o r   A 2   x o r . . . a i   x o r . . A n = 0 A_1space xorspace A_2space xor...a_ispace xor..A_n=0 A1​ xor A2​ xor...ai​ xor..An​=0,则由异或的消去律可以得到 A i   x o r   a i = 0 A_ispace xorspace a_i=0 Ai​ xor ai​=0。又因为 a i < = A i a_i<=A_i ai​<=Ai​,所以仅可能 a i = A i a_i = A_i ai​=Ai​成立。而这与每一次必须取非0石子数矛盾。

我们不妨把异或和为0视为P局面,异或和不为0视为N局面,则上述关系与NP局面之间的判定关系等价,因此可以认定对于任何一个局面,当异或和不为0,则先手必胜。

根据上述性质,我们不仅可以在 O ( n ) O(n) O(n)时间内判定当前局面是否先手必胜,还可以根据上述转移关系在 O ( n ) O(n) O(n)时间内找到所有先手必胜策略。

有向图游戏

上述NIM游戏仅是较为简单的一类游戏形式,而接下来介绍的有向图游戏形式更为一般。

游戏形式

给定一张有向图,其上有一个唯一起点,在起点上有唯一的一个棋子。交战双方轮流将这个棋子沿着有向边进行移动,每一次移动一步,直到无法移动时判负。

与ICG游戏关联

不妨将有向图中的有向边视为不同局面之间存在的合法转移关系。一次沿一条有向边进行移动,相当于把游戏从一个局面转移到另一个局面,当最后无法移动时,即是对应的玩家无法行动。

由上述分析可以看出,有向图游戏其实就是 I C G ICG ICG游戏的图形化,二者完全等价。

mex运算

设 S S S是一个非空整数集合(可为空),定义 m e x mex mex运算如下:
m e x ( S ) = min ⁡ x ∈ N , x ∉ S { x } mex(S)=min_{xin N,x notin S}{x} mex(S)=x∈N,x∈/​Smin​{x}
即 m e x mex mex运算是取出不属于S的最小非负整数。

SG函数 定义

我们在有向图游戏的每一个节点定义 S G SG SG函数。在有向图游戏中,称 y y y是 x x x的后继,当且仅当存在一条有向边由 x x x指向 y y y。则有
S G ( x ) = m e x ( { S G ( y ) ∣ y 是 x 的 后 继 } ) SG(x)=mex({SG(y)|y是x的后继}) SG(x)=mex({SG(y)∣y是x的后继})
即 x x x的 S G SG SG函数值是对其所有后继点的 S G SG SG函数值所组成的集合进行 m e x mex mex运算得到的结果。

性质

当 x x x不存在后继,则 S G ( x ) = 0 SG(x)=0 SG(x)=0,此时 x x x无法行动,对应P局面。

当 x x x的后继中存在着 y y y使得 S G ( y ) = 0 SG(y)=0 SG(y)=0,则 S G ( x ) ≠ 0 SG(x)ne 0 SG(x)​=0,对应N局面。

当 x x x的后继中不存在 y y y使得 S G ( y ) = 0 SG(y)=0 SG(y)=0,则 S G ( x ) = 0 SG(x)=0 SG(x)=0,对应P局面。

我们将NIM游戏抽象为一张有向图游戏,则双方轮流行动,每一次只能操作一堆石子,对应有向图游戏上只有一个棋子。那有向图中所有点的 S G SG SG函数值恰好对应了当前局面是否必胜。

深化

当有向图游戏中不是仅有一个棋子,而是存在着 n n n个棋子,此时我们考虑 S G SG SG函数的意义。当 S G ( x ) = k SG(x)=k SG(x)=k时,则对于任意 i i i且 0 < = i < k 0<=i k SG(y)>k SG(y)>k,但无论如何不存在 S G ( y ) = k SG(y)=k SG(y)=k。

对比NIM游戏,对于每一个石堆,设当前石子的数目为 k k k,我们可以把数目变为小于 k k k的任意非负整数,但不能保持为 k k k。

如果我们把节点的 S G SG SG函数值看为石堆的石子数,可以发现两者之间存在某种相似。但不同的是,石堆的石子数只能减少不能增加,而有向图中从一个点到其后继,节点的 S G SG SG函数值可能会增加。但利用上述分析NIM游戏先手必胜对应异或和不为0的方法,我们可以完全等价地证明:当所有棋子对应的节点的 S G SG SG函数异或值不为0时,一定存在某种策略,移动其中某一个棋子让所有节点 S G SG SG值异或和为0;当所有棋子对应节点的 S G SG SG函数异或值为0时,移动任一个棋子一定会使 S G SG SG值异或和不为0。因此将n个棋子视为n个石堆,便转化为了一个NIM游戏,NIM游戏的必胜策略即对应着移动棋子的必胜策略。

**注意:**我们对NIM游戏进行分析时,是将NIM游戏转化为了仅有一个棋子的有向图游戏。而对有n个棋子时,我们把n个棋子对应的 S G SG SG函数值抽象为石堆,便可以利用NIM游戏的思想来寻求最优策略。

可以发现,无论n个棋子是否在同一张有向图上,不影响最优策略的选定。因此我们可以定义有向图游戏的和。

有向图游戏的和

设 G 1 、 G 2 . . . G m G_1、G_2...G_m G1​、G2​...Gm​是 m m m个有向图游戏。定义有向图游戏 G G G,它的行动规则是任取一个有向图游戏 G i G_i Gi​,并在 G i G_i Gi​上行动一步。 G G G被称为有向图游戏 G 1 、 G 2 . . . G m G_1、G_2...G_m G1​、G2​...Gm​的和。

有向图游戏的和的 S G SG SG函数值定义如下:
S G ( G ) = S G ( G 1 )   x o r   S G ( G 2 ) . . x o r   S G ( G m ) SG(G)=SG(G_1)space xorspace SG(G_2)..xorspace SG(G_m) SG(G)=SG(G1​) xor SG(G2​)..xor SG(Gm​)
将m个有向图抽象为m个石堆, G G G的 S G SG SG函数值便指明了m个有向图游戏的先手必胜策略。

上述定义给我们指明了一个重要思想:若当前游戏可以分为多个子游戏,我们只需要分别分析并求取子游戏对应的有向图游戏的 S G SG SG函数值,便可以将这些 S G SG SG函数值视为NIM游戏中的石堆,从而得到全局游戏的最优策略。即是**“分而治之“**的思想。

例如:有n个石堆,每一次只能从第 i i i个石堆取 i i i的倍数个(第一个石堆即是任意数目),问是否有必胜策略。

我们可以把游戏分为n个子游戏,第一个游戏仅有一个石堆,可以任意取,第二个游戏也仅有一个石堆,只能取偶数个石子,以此类推。则对于第一个游戏即是最简单的"任取石子游戏",若当前有x个石子,则可以转移到0到x-1的任一个局面,因此当前局面的 S G SG SG函数值为x。对于第二个游戏,可以发现石子数目只能从奇数转移到奇数,从偶数转移到偶数,因此当节点对应石子数为偶数个时,则 S G SG SG函数值为1,反之为0。其他石子同理。于是我们便可以得到每一个子游戏的 S G SG SG函数值,进而得到全局的 S G SG SG函数值。

又如NIM游戏其实就是n个“任取石子游戏”的和。很多ICG游戏都可以按照这种方法进行划分,从而简化计算,方便理解。

SG函数计算方法简述

简洁起见,我们只讨论一堆石子的情形。若当前仅有一堆石子,可选的石子数组成一个序列,则分情况如下:

  1. 当序列为1~m中任意一个数,则设节点x代表当前有x个石子剩余,则 S G ( x ) = x % ( m + 1 ) SG(x)=x%(m+1) SG(x)=x%(m+1),每m个相邻石子数的 S G SG SG函数值形成了一个循环。
  2. 当序列为1到无穷,即可以任意取石子,则是上述的“任取石子游戏”,有 S G ( x ) = x SG(x)=x SG(x)=x。
  3. 当序列没有明显特征时,则可以采用暴力循环或记忆化搜索的方式得到节点的 S G SG SG函数值。具体思路便是枚举当前x节点的所有后继,根据其后继的 S G SG SG函数值得到x的 S G SG SG函数值。

对于有n堆石子时,我们可以直接分为n个子游戏,每一个子游戏都仅有一个石堆,便可沿用上述结论。

小结

给定一个ICG游戏,我们都可以将其抽象为一个有向图游戏,并且通过合理的划分,分为多个容易计算 S G SG SG函数值的子游戏,利用分而治之的思想解决问题。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/985933.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号