博弈论详解 2（SG函数 和 SG定理）

传送门博弈论详解 1基本理论定义 和 Nim 游戏什么是 SG 函数接着上次的讲解我们来了解一个更通用的模型。我们把每一个状态变成一个点在 Nim 游戏里就代表a aa数组如果可以从一种状态转移到另一种状态就在它们之间连一条有向边在 Nim 里就是从a 1 , a 2 , . . . , a n a_1,a_2,...,a_na1​,a2​,...,an​到a 1 ′ , a 2 , . . . , a n ( a 1 ′ a 1 ) a_1,a_2,...,a_n(a_1a_1)a1′​,a2​,...,an​(a1′​a1​)根据公平博弈游戏的性质有限步这张图应当是 DAG有向无环图。真的是吗似乎不是在一些游戏里它可能是多个 DAG当然你把 Nim 游戏的每个a i a_iai​的变化看成独立的一张图也不是不可以输的条件就是每个 DAG 都走到了最终局面0 00。不过为了方便我们先考虑一个 DAG 的情况。SG 函数的定义与计算设有向边的集合是E EE那么s g ( x ) M E X ( s g ( x ′ ) ) ( { x , x ′ } ∈ E ) sg(x)MEX(sg(x)) (\{x,x\}\in E)sg(x)MEX(sg(x′))({x,x′}∈E)所以s g sgsg函数需要用拓扑序逆序进行计算。MEX(X) 是指不包含在整数集合 X 中的最小非负整数如果 X 是空集MEX(X)0。举个简单的例子下图中每个点旁边的数字式是s g sgsg函数值。SG 函数与必胜条件 C最终局面即出度为0 00的点图中标蓝的s g sgsg函数值是0 00推测必胜条件C CC是s g ( x ) ≠ 0 sg(x)\ne0sg(x)0。对于C CC需要满足的三个条件进行证明博弈论详解 1 中加粗的那三条第一个条件从一个s g ( x ) ≠ 0 sg(x)\ne0sg(x)0的点x xx必然能走到一个点x ′ xx′使s g ( x ′ ) 0 sg(x)0sg(x′)0否则s g ( x ) 0 sg(x)0sg(x)0。符合。第二个条件从一个s g ( x ) 0 sg(x)0sg(x)0的点x xx必然走不到一个点x ′ xx′使s g ( x ′ ) 0 sg(x)0sg(x′)0否则s g ( x ) 0 sg(x)0sg(x)0。符合。第三个条件最终局面出度为0 00x ′ xx′的集合为空其s g sgsg函数值为0 00。符合。结论在一个 DAG 中某个状态的必胜条件是s g ( x ) ≠ 0 sg(x)\ne0sg(x)0。一个DAG到多个DAG——SG 定理定理对于一个由n nn个 DAG 组成的游戏设第i ii张图当前状态是s g 1 , s g 2 , . . . , s g n sg_1,sg_2,...,sg_nsg1​,sg2​,...,sgn​一开始就是每张图的初始状态全局的状态就是这些s g i sg_isgi​的集合。定义 SG 和s u m s g 1 ⊕ s g 2 ⊕ . . . ⊕ s g n sumsg_1\oplus sg_2\oplus...\oplus sg_nsumsg1​⊕sg2​⊕...⊕sgn​必胜条件C CC是s u m ≠ 0 sum\ne0sum0。这里第一个条件的验证方法和 Nim 游戏的验证方法很像读者可以尝试自己推算要注意 MEX 的性质。第一个条件假设s u m ( s u m ≠ 0 ) sum(sum\ne0)sum(sum0)最高位的1 11表示2 k 2^k2k则存在s g i sg_isgi​的第k kk位是1 11。由于s u m sumsum在比k kk更高的位置上都是0 00所以s g i sg_isgi​在异或s u m sumsum之后第k kk位变成0 00而更高位上的数字不变得到s g i ⊕ s u m s g i sg_i\oplus sumsg_isgi​⊕sumsgi​。根据函数定义从代表s g i sg_isgi​的点连出去的边指向的点中一定有一个点的s g sgsg函数值是s g i ⊕ s u m sg_i\oplus sumsgi​⊕sum用了 MEX只要小于s g i sg_isgi​的非负整数一定出现在了相邻的点上。如果从s g i sg_isgi​的点移到s g i ⊕ s u m sg_i\oplus sumsgi​⊕sum的点那么s u m 新 s u m 原 ⊕ s g i ⊕ ( s g i ⊕ s u m 原 ) 0 sum_{新}sum_{原}\oplus sg_i\oplus(sg_i\oplus sum_{原})0sum新​sum原​⊕sgi​⊕(sgi​⊕sum原​)0。可以从满足C CC的状态走到不满足C CC的状态符合。第二个条件如果此时s u m 0 sum0sum0要使其仍然是0 00必须找到一个s g i sg_isgi​他的边指向的点中有一个点的s g sgsg函数值与s g i sg_isgi​相等此时s u m sumsum不变。而 MEX 的集合里面如果有一个数x xx结果一定不是x xx。从不满足C CC的状态只能走到满足C CC的状态符合。第三个条件当所有s g i sg_isgi​都是最终局面无法进行任何操作的时候所有的s g i sg_isgi​都是0 00此时s u m 0 sum0sum0符合。结论对于多个 DAG 的游戏某个状态的必胜条件是s u m s g 1 ⊕ s g 2 ⊕ . . . ⊕ s g n ≠ 0 sumsg_1\oplus sg_2\oplus...\oplus sg_n\ne0sumsg1​⊕sg2​⊕...⊕sgn​0。基础应用练习题附做法ABC 368 F结语我今天其实也是现学现卖的做个总结前几天的 ABC 和 CSP-S 2019 初赛真题 都考到了博弈论我一脸懵 εεε(#д)所以学了一下。希望读者能看懂本人的讲解如果哪里有错欢迎大佬指正