组合博弈。如果两个玩家都发挥最佳，谁会赢

Question

Players A and B play a game optimally and move alternately. They start with 1. Each player in his turn multiplies the current number with any integer from [2,9]. If after a player's turn, the number is more than or equal to n, he wins.

A starts. Given n, who wins?

例如，

数字 2,3..,9 是中奖号码（玩家 A 将获胜）

数字 10,11,..,18 正在输（玩家 A 将输）

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

获胜的策略是什么？如何应用 Sprague-Grundy 定理来解决这个问题？

Answer 1

基本上你创建一个数组 A[] 其中 A[i] 存储数字 i 是相对于开始 game.Let 的玩家的获胜或失败位置，它是玩家 A。基本规则，从一个失败的位置你只能进入一个获胜的位置，并且一个获胜的位置总是可以从 it.Following 代码到达一个失败的位置是解释性的（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 那他就赢了，否则他就输了。
这是一个 O(n) 的解决方案，既及时又 memory.You 可以减少内存，但是时间我想不出更好的解决方案。可能有 O(1) 解决方案，但我不知道。

Answer 2

根据Sprague-Grundy theorem，公平游戏的每个状态都可以分配一个non-negative整数，称为Grundy数，这样在这个游戏中移动的玩家如果此数字为 0，则状态将输，如果此数字为 non-zero.

，则状态将获胜

如果各州的 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是最小排他函数。一组 non-negative 整数中的 MEX 等于不属于该集合的最小 non-negative 整数。

例如：

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

Python3 中此游戏的算法的简单实现可能如下所示：

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

组合博弈。如果两个玩家都发挥最佳，谁会赢

Combinatorial Game. Who wins if both players play optimally

algorithm

game-theory