αβ法（アルファベータ枝刈り）

αβ法について

αβ法（Alpha-Beta Pruning）は、1958年頃にジョン・マッカーシーらによって開発されたミニマックス法の最適化技術です。 ゲームツリーの探索において、「この先を調べても最終結果に影響しない」と判断できる部分を省略（枝刈り）することで、 計算量を大幅に削減します。

αβ法では、α（アルファ）とβ（ベータ）という2つの値を使って探索の範囲を管理します。 αはMAX側（自分）が「少なくともこれだけは確保できる」という下限値、 βはMIN側（相手）が「これ以上は渡さない」という上限値を表します。 α ≥ β となった時点で、その先の探索は結果に影響しないため打ち切ります。

枝刈りの仕組み

1. α値の更新（MAX層）: 自分のターンでは、子ノードの評価値のうち最大のものを選びます。 より良い手が見つかるたびにα値を更新し、「少なくともこの値は確保できる」という下限を記録します。
2. β値の更新（MIN層）: 相手のターンでは、子ノードの評価値のうち最小のものを選びます。 より悪い（相手にとって良い）手が見つかるたびにβ値を更新し、「これ以上は渡さない」という上限を記録します。
3. 枝刈り条件（α ≥ β）: もしα ≥ β となったら、この先の探索は無意味です。 MAX側は既にα以上を確保でき、MIN側はβ以下に抑えようとしますが、α ≥ β ならMIN側がこの分岐を選ぶことはありません。
4. 効率の向上: 最良のケース（完璧な手順で探索）では、計算量をO(b^d)からO(b^(d/2))まで削減できます。 つまり、同じ時間で約2倍の深さまで探索できるようになります。

効果と応用

• 計算量削減: 理想的な場合、探索ノード数を平方根まで削減可能
• 結果は同一: ミニマックス法と全く同じ最善手を見つけます
• 順序依存性: 良い手から先に探索すると、より多くの枝刈りが発生します
• 実用的なAI: チェス、将棋、オセロなどの実用的なゲームAIの基盤技術
• さらなる最適化: 反復深化、トランスポジションテーブルと組み合わせて使用されます

擬似コード

function alphabeta(node, depth, α, β, isMaximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if isMaximizing:
        value = -∞
        for each child of node:
            value = max(value, alphabeta(child, depth-1, α, β, false))
            α = max(α, value)
            if α >= β:
                break  // β枝刈り
        return value
    else:
        value = +∞
        for each child of node:
            value = min(value, alphabeta(child, depth-1, α, β, true))
            β = min(β, value)
            if α >= β:
                break  // α枝刈り
        return value

// 初期呼び出し
alphabeta(root, depth, -∞, +∞, true)

よくある質問