组合游戏。如果两个玩家都发挥最佳状态，谁会赢

Question

玩家A和B以最佳方式玩游戏，交替移动。他们从1开始。每个玩家在他的回合中用[2,9]中的任何整数乘以当前数字。如果在轮到一名球员后，该数字大于或等于n，则他获胜。

A开始。给定n，谁赢了？

举个例子，

数字2,3…，9是中奖数字（玩家A会赢）

数字10，11,..,18是丢失的数字（玩家A将输）

19号，20号，..，162是中奖号码

获胜的策略是什么？如何应用斯普拉格-格伦迪定理来解决这个问题？

Answer 1

基本上，你创建一个数组A[]，其中A[i]存储数字I相对于开始游戏的玩家是赢还是输。假设它是参与人a，基本规则是，从一个失败的位置你只能去一个胜利的位置，而胜利的位置总是有一个失败的位置可以到达。以下代码是解释性的(1表示w.r.t .对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，那么他赢了，否则他输了。< br >这在时间和内存上都是O(n)解决方案。你可以减少内存，但是我一时间想不出更好的解决办法。可能有O(1)解，但我不知道。

Answer 2

根据Sprague-Grundy定理，公平游戏的每个状态都可以分配一个非负整数，称为Grundy数，这样在这种状态下移动的玩家如果这个数是0，就会输，如果这个数不是零，就会赢。

如果已知各州的格兰迪数，那么获胜的策略是总是向格兰迪数为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

< code>MEX是最小排除函数。非负整数集合的< code>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))

通常，理解格兰迪数的一般公式的最简单方法是只看序列并尝试注意它们之间的关系。在这个游戏中，你可以通过简单地查看玩家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