【Python 電脳闘技場編 #3】未来の分岐点！ゲーム木の複雑性（O(bd)）と再帰関数の基礎

2026年8月1日

Contents

1. 第1章：爆発する未来の選択肢
2. 第2章：再帰関数によるダイブ（潜行）
3. 第3章：未来探索ツリーの基礎構造
- 3.1. 🛠️ Stoneの愛用ギア（ハッカーの開発環境）

第1章：爆発する未来の選択肢

さて、前回で「盤面（State）」と「打てる手（合法手）」の生成が完了した。これによって僕たちは、現在の世界から派生する「すぐ次の未来」をメモリ上に展開できるようになったわけだ。

だが、たった1手先を読んだだけで勝てるほど、電脳闘技場は甘くない。勝利を掴むためには、さらにその先、未来の果てまで見通す必要がある。
ここで立ちはだかるのが、計算量「O(b^d)」の壁だ。

b は1ターンあたりの平均的な選択肢の数（Branching factor）、d は先読みするターンの深さ（Depth）を表す。
Ultimate Tic-Tac-Toe において、フリーターンを含めない通常時でも b は平均して約9ある。
もし10手先（d=10）まで完全に読み切ろうとすると、9¹⁰ = 約34億8千万もの盤面（パラレルワールド）を評価しなければならない計算になる。

さらに恐ろしいフリーターンが発生すれば、b は最大81に跳ね上がる。これをCodinGameの制限時間「50ms（0.05秒）」以内にすべて計算するなど、どんなスーパーコンピュータでも不可能だ。

第2章：再帰関数によるダイブ（潜行）

すべてを読み切るのが不可能なら、どうする？答えはシンプルだ。「時間（50ms）が許す限界の深さまで潜り、そこで計算を打ち切って盤面を点数化する」のさ。

この「限界まで潜る」という動作をプログラムで実装するために不可欠なのが再帰関数（Recursive Function）だ。
関数の中で自分自身の関数を呼び出すことで、ゲーム木（Game Tree）と呼ばれる未来の分岐ツリーを、深く深く降りていくことができる。ループ処理（forやwhile）だけでは、このような複雑に枝分かれする未来を辿ることは極めて困難だ。

第3章：未来探索ツリーの基礎構造

それでは、今後「Minimax法」や「Alpha-Beta枝刈り」のベースとなる、再帰探索のコア・テンプレートを書いてみよう。
前回作成した State クラスと get_legal_moves() メソッドがここで生きてくる。

def explore_future(state, depth):
# 限界の深さに達したか、ゲームが終了（勝敗決定）した場合
if depth == 0 or state.is_game_over():
# この盤面が自分にとってどれくらい有利か（評価値）を数値化して返す
return evaluate_board(state)
<pre><code># 探索を続ける場合：今の盤面から打てるすべての手を調べる
for move in state.get_legal_moves():
    # パラレルワールド（新しい盤面）を生成
    next_state = state.clone()
    next_state.apply(move) # 手を適用

    # 生成した未来の世界へ、さらに1段深くダイブする（再帰呼び出し）
    explore_future(next_state, depth - 1)

これが未来探索の骨格だ。explore_future の中で再び explore_future を呼び出しているのがわかるだろう？これにより、指定した depth の深さまで、あらゆる分岐を自動で這い回ってくれるんだ。

ただし、このコードはまだ不完全だ。「無数にある未来のスコアをどう比較し、最善手を選ぶのか」というロジックがすっぽり抜け落ちている。

次回、第4回：「未来の果てから逆算せよ！Minimax法のコア・アーキテクチャ」。
この再帰関数の骨格に、敵の悪意と自分の最善をぶつけ合う「悲観的かつ最強の思考エンジン」を組み込んでいこう。