【Python 電脳闘技場編 #7】枝刈りの刃を研ぎ澄ませ！「Move Ordering（手番の並び替え）」

2026年8月7日2026年8月11日

Contents

1. 第0章：優先順位（オーダー）の支配
2. 第1章：なぜ「探索する順番」が重要なのか？
3. 第2章：良さそうな手とは何か？
4. 第3章：Move Ordering の実装
- 4.1. 🛠️ Stoneの愛用ギア（ハッカーの開発環境）

第0章：優先順位（オーダー）の支配

電脳闘技場の闇の中、Stoneの目の前に展開されたゲーム木は、前回手に入れた光の刃（Alpha-Beta）によって次々と切り落とされていた。
しかし、彼はまだ満足していない。マトリックス・グラスに映る探索速度のメーターは、時折ひどくモタついている。

Alpha-Beta枝刈りは強力な魔術だ。だが、探索する『順番』が悪ければ、その刃は途端にナマクラになる。ゴミみたいな手から順番に調べていたら、枝刈りが発動するまでに無駄な時間を浪費してしまうからね。

Stoneがハサミを弾くと、空中に浮かぶ無数の「次の手（選択肢）」が、一瞬にして再配列された。
有望な未来を先に、無価値な未来を後に。
計算機科学におけるハッカーの小技、「Move Ordering（手番の並び替え）」の真髄を見せてやろう。

第1章：なぜ「探索する順番」が重要なのか？

前回の「Alpha-Beta枝刈り」の仕組みを思い出してほしい。
枝刈りが発動する条件は 「Beta <= Alpha」 になった時だ。つまり、「もっと良い手がすでに見つかっているから、今の悪い手はもう調べなくていい」と判断した瞬間に、未来を切り捨てることができる。

ここが最大のポイントだ。
もし、ループの一番最初に「最高の神の一手」を引き当てていたらどうなるだろうか？
Alpha値（またはBeta値）が一気に更新され、その後の無駄な手（2番目以降の選択肢）は、計算するまでもなくすべて一瞬で枝刈りされることになる。

逆に、最悪の手から順番に調べてしまうと、AlphaやBetaの値がなかなか更新されず、結局すべての未来をバカ正直に計算するハメになる。これではただのMinimaxと同じだ。
Alpha-Beta枝刈りの効率を極限まで高めるには、「良さそうな手から順番に探索する（Move Ordering）」ことが絶対に不可欠なのだ。

第2章：良さそうな手とは何か？

Ultimate Tic-Tac-Toe において「良さそうな手」とは何だろうか？
第5回で作成した「評価関数（ヒューリスティクス）」の重み付けを思い出せば簡単だ。

中央のマス（重み 4）
角のマス（重み 3）
辺のマス（重み 2）

この順番で指し手を並べ替え、中央から優先的に探索するようにしてやればいい。

もちろん、本来なら「ビンゴになりそうな手」や「敵を不利な盤面に送る手」を最優先すべきだが、それを正確に計算しようとすると並び替え自体に時間がかかってしまい、本末転倒になる。Move Ordering の評価は『超軽量』であることが鉄則だ！

第3章：Move Ordering の実装

それでは、Pythonコードで合法手（Legal Moves）をソートするロジックを実装しよう。
第2回で作った get_legal_moves() の結果を、重み順に並び替えるラッパー関数を作成する。型ヒントもバッチリ仕込んでおくぜ。

# 第5回で定義したマスの重み（中央が最強）
CELL_WEIGHTS: List[int] = [
3, 2, 3,
2, 4, 2,
3, 2, 3
]

def get_ordered_moves(state: 'State') -> List[int]:
# まずは通常の合法手リストを取得
legal_moves: List[int] = state.get_legal_moves()
<pre><code># 独自のソートキー（評価基準）を定義する関数
def move_score(move: int) -> int:
    # 1次元インデックス(0~80)から、ミクロ盤面内のインデックス(0~8)を算出
    micro_idx: int = move % 9
    # そのマスの重みを返す
    return CELL_WEIGHTS[micro_idx]

# 重みが大きい（良さそうな手）順に降順(reverse=True)でソート
legal_moves.sort(key=move_score, reverse=True)

return legal_moves

あとは、前回の alpha_beta 関数の中にある for move in state.get_legal_moves(): というループを、この for move in get_ordered_moves(state): に差し替えるだけだ。

たったこれだけのハックで、Alpha-Betaの枝刈り効率は跳ね上がり、同じ50msの制限時間でも、さらに深い O(b^d) の未来まで手を伸ばすことができるようになる。

次回、第8回：「制限時間ギリギリまで潜れ！『反復深化（Iterative Deepening）』」。
いよいよ、Phase 4「Time Out（50ms）との死闘」に突入する。時間が来たらスパッと計算を打ち切り、常に最善手を返し続けるための時間管理アーキテクチャを構築するぜ！