Pythonで塔壊しゲームの勝者を見つけるプログラム

高さを表す配列 height が与えられているとします。ここには高さの異なる n 本の塔があり、Amal(アマル)と Bimal(ビマル)の2人が次のルールでゲームを行います。

• 必ず Amal が先手です。
• 各手番で、現在のプレイヤーは高さ X の塔を1本選び、それを高さ Z の塔 Y 本に分解します(ただし Y × Z = X、かつ X と Y はどちらも 1 より大きい整数)。
• 自分の手番で動かせる塔がなくなったプレイヤーの負けとなります。

このゲームの勝者の名前を求めるのが課題です。

例えば入力が height = [3,1,2] の場合、答えは Bimal になります。初期状態は {3, 1, 2} です。Amal が高さ 2 の塔を高さ 1 の塔2本に分解すると、塔の構成は {3, 1, 1, 1} になります。そこで Bimal が高さ 3 の塔を高さ 1 の塔3本に分解すれば、Amal はもう動かせる塔がなくなり、勝者は Bimal となります。

解き方：スプラーグ=グランディの定理

この種のゲームはスプラーグ=グランディ(Sprague–Grundy)の定理を使うと効率的に解けます。各塔の Grundy 数(ニム数)を事前計算しておき、すべての塔の Grundy 数の XOR を取ります。結果が 0 以外なら先手(Amal)の勝ち、0 なら後手(Bimal)の勝ちです。

アルゴリズムの手順

1. util() 関数を定義します。引数 limit の初期値は 10^3 + 5 です。
2. result := サイズ limit の配列を用意し、すべて 0 で初期化します。
3. i を 2 から limit − 1 まで順に処理します。
   • s := 新しい空の集合
   • j を 1 から √i の切り捨て値まで繰り返します。
     • d := i ÷ j の商、r := i ÷ j の余り
     • r が 0 の場合(j が i の約数の場合):
       • j が奇数なら、result[d] を s に追加
       • d が奇数なら、result[j] を s に追加
   • j := 0 とし、j が s に存在する間 j を 1 ずつ増やします。
   • result[i] := j(s に含まれない最小の非負整数:mex)
4. result を返します。
5. g := util() として Grundy 数のテーブルを作成します。
6. メイン処理では以下を実行します。
   • r := 0
   • height の各要素 i について:r := r XOR g[i]
   • r が 0 以外なら "Amal" を返し、そうでなければ "Bimal" を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

def util(limit=10**3+5):
    result = [0] * limit

    for i in range(2, limit):
        s = set()
        for j in range(1, int(i**0.5)+1):
            d, r = divmod(i, j)

            if r == 0:
                if j & 1:
                    s.add(result[d])
                if d & 1:
                    s.add(result[j])

        j = 0
        while j in s: j += 1
        result[i] = j

    return result

g = util()

def solve(height):
    r = 0

    for i in height:
        r ^= g[i]

    if r:
        return "Amal"
    else:
        return "Bimal"

height = [3,1,2]
print(solve(height))

入力

[3,1,2]

出力

Bimal