【Python 電脳闘技場編 #8】制限時間ギリギリまで潜れ！「反復深化（Iterative Deepening）」

2026年8月12日

Contents

1. 第0章：50msの死神
2. 第1章：固定深度の罠
3. 第2章：反復深化（Iterative Deepening）のロジック
4. 第3章：Time Outと戦うメインループ実装
- 4.1. 🛠️ Stoneの愛用ギア（ハッカーの開発環境）

第0章：50msの死神

「チッ……チッ……チッ……」
電脳闘技場に、無慈悲なカウントダウンの音が響き渡る。
Stoneの視界の隅で明滅する赤いタイマーが、残された思考時間をミリ秒単位で削り取っていく。

どんなに美しいAlpha-Beta枝刈りを組んでも、時間をオーバーして『Time Out』になれば、その瞬間に敗北（自爆）が確定する。CodinGameが僕たちに与えた猶予は、たったの50ms（0.05秒）だ。

深さ5まで読むべきか？それとも深さ6までいけるか？
盤面の複雑さによって、計算にかかる時間は劇的に変化する。事前に「ここまでは読める」と固定することは不可能なのだ。
ハッカーは、時間が許す限り未来へ潜り、死神の鎌が振り下ろされる直前に「最善手」を握りしめて帰還しなければならない。

時間管理（タイムマネジメント）の極意、「反復深化」の幕が開く！

第1章：固定深度の罠

これまで作ってきた alpha_beta 関数は、引数で depth（深さ）を指定して探索を行っていた。
しかし、実践では「深さ」を固定してしまうと、致命的な2つの問題が発生する。

時間が余る問題: 盤面がシンプルで計算が軽い時、深さ4に設定していると10msで計算が終わってしまう。残りの40msを使えば深さ6まで読めたかもしれないのに、思考を放棄してしまう。
時間が足りない問題: フリーターンなどで計算が爆発した時、深さ4の計算に200msかかってしまう。結果、50msのTime Outで強制敗北となる。

未来の分岐数 O(b^d) は毎ターン変動する。だから、「今回は深さ何段までいけるか」なんて、実際に潜ってみるまで誰にもわからないんだ。

第2章：反復深化（Iterative Deepening）のロジック

この問題を解決するエレガントな手法が「反復深化（Iterative Deepening）」だ。
やり方は非常にシンプルで、ハッカーらしい泥臭いアプローチである。

まず、深さ1 で全力探索する。（一瞬で終わる）
終わったら、次は 深さ2 で全力探索する。
終わったら、次は 深さ3 で……
これを無限ループで繰り返し、「制限時間（50ms）が近づいたら、計算を途中でスッパリと打ち切る」。
打ち切られた直近の計算結果は破棄し、「完全に計算が終わっている1つ前の深さでの最善手」を最終結論として提出する。

「同じ盤面を何度も計算するのは無駄じゃないか？」と思うかもしれない。しかし、O(b^d) という指数関数の爆発においては、「深さ1〜4までの計算時間の合計」は「深さ5の計算時間」の足元にも及ばない。反復することのオーバーヘッド（無駄）は、時間管理の確実性に比べれば無視できるレベルなのだ。

第3章：Time Outと戦うメインループ実装

それでは、Pythonの time モジュールを使って、経過時間を監視しながら反復深化を行うロジックを実装しよう。通信ラグなどを考慮して、50msではなく「45ms（0.045秒）」を限界値として設定するのがコツだ。


import time
from typing import List

def get_best_move(state: 'State', time_limit_ms: int = 45) -> int:
# 思考開始時のタイムスタンプを取得
start_time: float = time.time()
time_limit_sec: float = time_limit_ms / 1000.0
best_move: int = -1
depth: int = 1

# 時間が許す限り、無限に深く潜り続けるループ
while True:
    # 現在の深さで探索し、最善手を取得する（※別途実装）
    # ※ 時間切れの際は例外(Exception)を投げて中断する仕組みがベター
    current_best_move: int = search_root(state, depth, start_time, time_limit_sec)

    # 探索から戻ってきたら、経過時間をチェック
    elapsed_time: float = time.time() - start_time

    # もし制限時間を超えていたら、今回の深さの結果は未完成なので破棄してループを抜ける
    if elapsed_time > time_limit_sec:
        break

    # 時間内に探索が完了したなら、ベストな手を更新し、さらに1段深く潜る準備をする
    best_move = current_best_move
    depth += 1

# 安全に計算が終わった、一番深い探索での最善手を返す
return best_move

これが時間管理のコア・アーキテクチャだ。実際の search_root 関数の中（Alpha-Betaの再帰中）でも定期的に time.time() を監視して、時間が来たら探索を強制終了（ブレイク）させる処理を入れることで、完璧な反復深化が完成するぜ。

次回、第9回：「過去の記憶（ハッシュ）を生成せよ！『Zobrist Hashing』の基礎」。
限られた時間内でさらに深く潜るためには、Phase 5に繋がる「キャッシュ技術」が不可欠になる。盤面の状態を高速に「一意の64ビット整数」へ暗号化する、ビット演算の魔術を伝授しよう。