Sprague–Grundy theorem

算法 2016-04-05

翻译自维基

定义

Sprague-Grundy理论针对信息充分、满足结束条件(所有游戏都有结果:不存在无限循环的游戏)和正常游戏条件(不能移动的玩家失败)的双人游戏。 类似于Nim这样完全公平的游戏,任何时刻每个玩家都有完全一样的可行步骤。而对于tic-tac-toe(井字棋),象棋这些游戏不是完全公平游戏。在象棋里,玩家只能移动自己的棋子,不能移动对方的棋子。而在tic-tac-toe中,一名玩家画X,另一名玩家只能画O。公平游戏只有两类结果:要么先手赢(N-position),要么后手赢(P-position). 在这个证明里,一个状态由当前状态能一步到达的状态集合确定(这些状态称为选项)。例如,状态{}是一个P-position(必败态),在正常游戏里,当前玩家因为不能移动而失败。而状态则相反,是一个N-position(必胜态);当前玩家只有一个选择,而这个转移对于对方是一个必败状态。 一个nimber是一个特殊状态用*n表示序数n.*0是{}。其他nimber类似地由*(n+1)=*n∪{*n};此外,*1={*0},*2={*0,*1}等。因此*n对应一个有n个数的nim堆。 两个状态G和H能够组合成一个新状态G+H在当前玩家能够选择移到状态G或H的组合游戏中。集合G+H用规则G+G={G+h|h∈H}∪{g+H|g∈G}计算, 这个规则表明状态叠加是可交换和可结合的。 两个状态G和G'被认为相等当且仅当,对于每个状态H,状态G+H和G'+H有相同结果,写为G≈G'。

引理一

作为证明主要理论的中间步骤,我们发现,对于每个状态G和每个必败态(P-position)A,总有G≈A+G成立。根据上面等价的定义,这个相当于G+H和A+G+H有同样的结果,对于所有的H来说。 假设G+H是一个必败态(P-position)。那么后手对于状态A+G+H有个必胜策略:根据先手的动作转移到状态A,由于A是个必败态(P-position),所以存在必胜策略。或根据先手的动作转到状态G+H,同样也存在必胜策略。所以A+G+H必然是个必败态(P-position)。 如果G+H是个必胜态(N-position),那么先手有必胜策略:在G+H的转移集合里选择一个必败态(P-position),然后使对手处于必败态。因此当前条件下,A+G+H一定跟G+H一样是个必胜态(N-position)。

引理二

进一步我们发现G≈G',当且仅当G+G'是一个必败态(P-position)。 先假设G≈G',应用等价定义,令H=G,我们发现G'+G和G+G的结果相同。而G+G一定是个必败态(P-position):对于G到每个移动,后手可以做相同的移动在另一个G中,所以总是能达到最后的移动。 反过来,假设A=G+G'是个必败态(P-position),那么根据引理一可得G≈G+A,即G≈G+(G+G')。类似地,因为A=G+G也是个必败态(P-position),根据引理一可得G'≈G'+A,G'≈G'+(G+G)。根据交换律和结合律,等式右边是相等的。通过≈的传递性,我们可以得出G≈G'的结论。

证明

我们通过结构归纳证明了所有状态都等价于一个Nim堆值(nimber)。当结果是确定时,游戏给定的初始状态必然等价于一个Nim堆值(nimber),表明游戏自身也等价于一个Nim堆值。 考虑状态G={G1,G2,...,Gk}.假设所有的这些转移状态都等价于Nim堆值,也就是说Gi≈*ni。即让G'={*n1,*n2,...,*nk}。我们会发现G≈*m,m=mex(n1,n2,...,nk),ni中未出现的最小非负整数。 首先通过引理二,我们注意到G≈G'。当k=0时,该结论成立;当k≠0时,考虑G+G'。如果先手转移到G中Gi,那么后手可以转移到G'中的*ni;当先手转移G'中的某个状态时,则反过来。因此,G+G'是个必败态(P-position)。 再次通过引理二,我们知道G'+*m是个必败态(P-position),即G'≈*m。 假设G'和*m都为空,那么G'+*m也为空,是一个必败态。 否则考虑先手转移到*m中的状态*m',m'<m。因为m是最小排除整数(mex),后手可以再G'中转移到*m'。所以正如之前演示的,任何状态加上本身都是必败态(P-position)。 假设先手转移到G'中的状态*ni。如果ni<m那么后手可以从*m转移到*ni;如果ni>m,则后手从*ni转移到*m;两种结果都是一个状态加上本身。 最后我们得出G≈G'和G'≈*m。通过传递性,我们可以得出G≈*m。

结论

如果G是一个公平游戏的状态,唯一整数m,满足G≈*m,则m称为Grundy值或Grundy数,并且计算这个状态值的函数称为Sprague-Grundy函数。R.L.Sprague和P.M.Grundy独立地给出了这个函数的准确定义,不基于Nim状态关于等价的概念,并展示了有以下几个属性:

  • 大小为m的单个nim堆的Grundy值为m
  • 一个状态对于先手是必败的,当且仅当Grundy值为0
  • 一个有限状态集合的Grundy值为集合中的状态的Grundy值的Nim和。

本文由 mcginn 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

赏个馒头吧