玩家A和B以最佳方式玩游戏并交替移动。它们从 1 开始。轮到每个玩家将当前数字与 [2,9] 中的任何整数相乘。如果在轮到玩家之后,数字大于或等于n,则他获胜。
A 开始。给定n,谁赢了?
例如,
数字 2,3..,9 是中奖号码(玩家 A 将获胜)
数字 10,11,..,18 正在输号(玩家 A 会输)
数字 19,20,..,162 是中奖号码
获胜的策略是什么?如何应用 Sprague-Grundy 定理来解决这个问题?
玩家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 时输,如果该数为非零则为赢.
如果状态的 Grundy 数已知,那么获胜的策略是始终移动到 Grundy 数为 0 的状态。
为一般博弈的某些状态计算 Grundy 数的算法如下:
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 个数字来计算出一般公式,而无需实际计算 Grundy 数字。
但是我们仍然可以查看游戏初始状态连续n的 Grundy 数的计数(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 的初始状态是失败 iff
基本上,您创建一个数组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)解决方案,但我不知道。