组合游戏。 如果两位球员都打得最好，谁将获胜
玩家A和B以最佳方式进行游戏并交替移动。 他们从1开始。每个玩家轮流将当前数字与[2,9]中的任意整数相乘。 如果在轮到玩家之后，该数字大于或等于n ，他就获胜。
A开始。 鉴于n ，谁赢了？
例如，
数字2,3 ..，9是获胜数字（玩家A将获胜）
数字10,11，...，18都在输球（球员A输球）
数字19,20，..，162是中奖号码
获胜策略是什么？ Sprague-Grundy定理如何应用于解决这个问题？
根据Sprague-Grundy定理，每个公正游戏的状态都可以被分配一个称为Grundy数的非负整数，这样如果这个数字为0，那么在这个状态下移动的玩家将会失败，并且如果这个数字是非零。
如果状态的格兰迪数已知，则获胜策略总是转移到格兰迪数为0的状态。
用于计算一般游戏的某种状态的格伦迪数的算法如下：
if current player can't make a valid move:
Grundy number := 0 (this player has lost)
else:
for each move in this state:
for each sub-game the game splits into after that move:
compute Grundy number of the sub-game
compute XOR of Grundy numbers of the sub-games
Grundy number := MEX of those XORs
MEX是最小排除功能。 一组非负整数的MEX等于最小的非负整数，它不属于这个集合。
例如：
MEX(0) = 1
MEX(0, 1) = 2
MEX(0, 2) = 1
MEX(0, 1, 2) = 3
MEX(0, 1, 3) = 2
MEX(1, 2, 3) = 0
MEX(10, 100, 1000) = 0
在Python 3中这个游戏的这个算法的朴素实现可能如下所示：
import functools
from itertools import count
def mex(s):
for i in count():
if i not in s:
return i
@functools.lru_cache(10000)
def sprague_grundy(n, cur=1):
if cur >= n:
return 0
move_results = {sprague_grundy(n, cur*move) for move in range(2, 9+1)}
return mex(move_results)
for i in count(1):
print(sprague_grundy(i))
通常理解Grundy数的一般公式的最简单方法是看看序列并尝试注意关系。 在这个游戏中，您可以通过简单地查看玩家A在初始状态中获胜的游戏的n个数字来计算出一般公式，而无需实际计算格兰迪数字。
但是我们仍然可以看到连续n的游戏初始状态的格兰迪数的计数（0表示玩家A在初始状态下输，1,2,3,4代表玩家A获胜）：
$ python3 sprague_grundy.py | uniq -c
1 0
1 1
2 2
4 3
1 4
9 0
18 1
36 2
72 3
18 4
162 0
324 1
648 2
1296 3
324 4
2916 0
有可能注意到，对于玩家A来说，所有失败的初始状态都是为了
换句话说，如果玩家A的初始状态正在失败
基本上，你可以创建一个数组A [A] ，其中A [i]存储数字i是获胜位置还是失败，相对于开始游戏的玩家。让它成为玩家A. 基本规则，从失败的位置，你只能去赢得一个胜利的位置，总是有一个失去的位置可达。下面的代码是解释性的（ 1意味着获胜与A和0意味着失败）。
for each i from 1 to 9
A[i]=1
for each i from 10 to n
flag=0
A[i]=0
for each j from 2 to 9
if i is divisible j and A[i/j] is 0
flag=1
if flag is 1
A[i]=1
现在，如果A [n]是1，那么他为他赢得胜利。
这是一个在时间和内存方面都是O（n）的解决方案。您可以减少内存，但是我无法想出更好的解决方案。 可能有O（1）解决方案，但我不知道它。
上一篇: Combinatorial Game. Who wins if both players play optimally