复习csp2019的时候稍微看了看博弈论,发现自己对于sg函数的理解完全不到位

有些定义甚至想都没想过

于是就口胡了一篇blog来安慰虚弱的自己

Question 1

对于一个满足拓扑性质的公平组合游戏

若定义一个函数\(f\),\(f(P状态)=0\)

假设当前状态为\(a\),它对局面的定义合法

那么\(f=sg\)

可以发现,它就是\(Muti-sg\)问题的核心,接下来我们希望证明这个问题的正确性

对于后继

  1. 指的是一步转移到的状态
  2. 后继一定不会等于当前状态

对于局面

它满足以下的性质(当然,性质的名字是我自己取的)

  1. 状态性:它本身也可以是一个状态
  2. 后继性:局面本身是状态的后继,或是后继的后继,等等
  3. 异或可行性:即\(f(a)\)是\(a\)所包含的所有局面\(f\)值的异或和
  4. 唯一改变性:后继与状态本身仅改变了一个局面,
  5. 单向变化性:局面只会改变成为它的后继(如果它是一个状态)

证明

\(f=sg\) 等价于任意\(a\)满足,\(f(a)\)是\(mex\{f(a的后继)\}\)

因为状态之间的关系本质上是一个\(DAG\)(即满足拓扑性),所以可以通过归纳法来证明

假设一个状态\(a\),它的所有后继(包括后继的后继)的\(f\)值都等于\(sg\)值

假设\(a\)可以分为局面\(b_1\)~\(b_n\),对应\(f_1\)~\(f_n\),它们等于\(sg_1\)~\(sg_n\)

所以\(f(a)=f_1\oplus f_2\oplus . ..\oplus f_n=sg_1\oplus sg_2\oplus . ..\oplus sg_n\)

如果\(a\)有一个后继\(c\),考虑\(f(c)=f(a)\oplus sg_i \oplus sg_x\),也就是把\(b_i\)这个局面改成了\(x\)局面

考虑\(f(c)\)可以取哪些值?

首先,因为\(sg_i \ne sg_x\),所以\(f(c) \ne f(a)\)

接下来证明\(f(c)\)可以取到\(0\)~\(f(a)-1\)的所有数

对于一个值\(val\in[0,f(a)-1]\)

设\(k\),满足\(val=f(a) \oplus k\)

因为\(val<f(a)\),考虑\(val\)的最高的和\(f(a)\)不同的一位,这一位必然存在并且在这一位上\(f(a)\)是\(1\),\(val\)是\(0\)

这一位同时也是\(k\)的最高位

那么必然存在一个\(sg_i\)满足它的这位是\(1\),而对应的\(sg_x\)必然会小于\(sg_i\),因为它的这位是\(0\)

所以存在满足条件的\(x\)且它是\(b_i\)的后继

所以这样的\(k\)可以通过\(sg_i \oplus sg_x\)构造得到

Question 2

翻硬币游戏

定义,有一些硬币排成一排,两人采用最优策略,每次可以翻动其中一些硬币(正变反,反变正),保证翻的硬币中最右边的硬币只能是从正翻到反,不能翻动者输

结论

每个状态的\(sg\)值等于当前所有为正面的硬币在序列中单独存在的状态的\(sg\)值的异或和

证明

设正面为\(1\),反面为\(0\)

'...'表示状态,...表示局面

把一个状态的\(01\)串倒过来,即'00101'变成\(10100\),把它看成一个二进制数,那么在游戏过程中这个数字递减

所以这个游戏是满足拓扑性质的

接下来我们设一个定义域为\(01\)串的函数\(f\)

  • \(f(00...0)=0\)
  • \(f(00...01)=sg(00...01)\)
  • \(f(一个01串)=\bigoplus_{每一个1} f(000..01)\)
  • 其中对于第\(i\)个\(1\),前面有\(i-1\)个\(0\)

假设当前状态为'011001'

\(f(011001)=f(01)\oplus f(001)\oplus f(000001)\)

'011001'有这样一个后继'010100'

可以说\(f(010100)=f(01)\oplus f(0001)=f(011001)\oplus f(0011)\oplus f(000001)\)

我们把\(01\),\(001\),\(000001\)看成是'011001'的三个特殊的局面

那么'010100'可以分拆成\(01\),\(001\),\(0011\)三个局面,尽管它们显得不那么特殊

这样的局面划分是合法的,因为可以看成是\(000001\)变成了\(0011\)这个局面,它满足异或和的性质

而很显然的是'0011''001100')确实是'000001'的一个后继

因为\(f\)满足这样的性质:

  1. \(状态f(P状态)=0\)
  2. 对于局面的定义合法

在此之前,我们已经证明了,对于这样的\(f\),\(f=sg\)

完结撒花★,°:.☆( ̄▽ ̄)/$:.°★


Blog来自PaperCloud,未经允许,请勿转载,TKS!

05-20 04:33