Pythonで解く「平方数取りゲーム」の勝敗判定プログラム

2人で行うビー玉（マーブル）ゲームを考えてみましょう。盤面には n 個のビー玉があり、各ターンでプレイヤーは「正の平方数個」（1、4、9、16…）のビー玉を必ず取らなければなりません。取れる平方数がない場合、そのプレイヤーは負けとなります。

この記事では、与えられた n に対して、先手の自分が最適な手を選んだ場合に勝利できるかどうかを判定するプログラムをPythonで実装します。

問題の例

たとえば入力が 14 の場合、出力は True（勝てる）になります。理由は以下のとおりです。

• 初手で自分が 9個 取る → 残り5個
• 相手は最大でも 4個 しか取れない → 残り1個になる
• 次の自分の番で最後の 1個 を取る → 残り0個となり、相手は指せない

このように相手を行き詰まらせることができるため、勝利が確定します。

アルゴリズムの考え方

この種のゲームはゲーム木探索で解くことができます。「自分の手番で勝てる局面」は、「取れる手の中に、相手が負けるような手が1つでも存在する」局面です。これを再帰的に表現すると次のようになります。

• n ≤ 0 の場合：False を返す（手番のプレイヤーは負け）
• ans = False で初期化する
• i を √n の整数部分から 1 まで降順にループする
  • i × i > n ならループを抜ける
  • ans = ans OR (not solve(n − i × i)) を計算する
    ※ 相手の局面が負け（False）なら、自分は勝ち（True）
  • ans が True になった時点で即座に返す（枝刈り）
• 最後に ans を返す

Pythonでの実装例

from math import sqrt

def solve(n):
    if n <= 0:
        return False
    ans = False
    for i in range(int(sqrt(n)), 0, -1):
        if i * i > n:
            break
        ans = ans | (not solve(n - i * i))
        if ans:
            return ans
    return ans

print(solve(14))

入力

14

出力

True

パフォーマンス改善のヒント：メモ化

上記の素朴な再帰では、同じ n が何度も計算されるため、n が大きくなると計算量が急増します。functools.lru_cache を使って結果をキャッシュすれば、各状態を1回だけ計算するようになり、大幅に高速化できます。

from math import sqrt
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(n):
    if n <= 0:
        return False
    return any(not solve(n - i * i) for i in range(int(sqrt(n)), 0, -1))

print(solve(14))  # True

このように、再帰・メモ化・枝刈りを組み合わせることで、平方数取りゲームのような組み合わせゲームの勝敗を効率よく判定できます。