2

プレイヤーAとプレイヤーBはゲームを最適にプレイし、交互に動きます。それらは 1 から始まります。自分のターンの各プレイヤーは、現在の数字に [2,9] の任意の整数を掛けます。プレーヤーのターンの後、その数がn以上の場合、そのプレーヤーが勝ちます。

Aがスタート。nが与えられた場合、誰が勝ちますか?

例えば、

数字の 2、3、..、9 が当たりの数字です (プレイヤー A が勝ちます)。

数字 10、11、..、18 は負け数字です (プレイヤー A が負けます)

数字 19、20、..、162 は当選番号です。

勝つための戦略とは？これを解決するために Sprague-Grundy の定理をどのように適用できますか?

4

2 に答える 2

3

Sprague-Grundy の定理によれば、公平なゲームの各状態には、 Grundy 数と呼ばれる非負の整数を割り当てることができます。この状態で移動するプレーヤーは、この数が 0 の場合は負け、この数が 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の 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 にとって、負けた初期状態はすべて

n \in \left( 9\cdot18^k .. 18^{k+1} \right ]: \textup{for} : k=0,1,2,...

言い換えれば、プレイヤー A の初期状態は iff に負けています。

\left\lfloor{\log_{18}{\frac{n-1}{9}}}\right\rfloor > \left\lfloor{\log_{18}{\frac{n}{18}}}\右\r床

于 2015-01-23T03:33:30.197 に答える
1

基本的に、配列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)ソリューションがあるかもしれませんが、私はそれを知りません。

于 2015-01-23T00:34:27.100 に答える