Day 152-Q2 | アルファベータ枝刈り（Alpha-Beta Pruning）

問題

深さ $D$ の完全二分木で表されたゲーム木が与えられる。根（深さ0）は最大化(MAX)プレイヤーの手番で、1手進むごとに手番が最小化(MIN)⇔最大化(MAX)と交互に入れ替わる。深さ $D$ のノード（葉）には評価値が与えられており、それ以外のノードの値は「自分の手番なら子の値の最大、相手の手番なら子の値の最小」として再帰的に決まる。

アルファベータ枝刈りを用いてこのゲーム木を探索し、根のミニマックス値を出力せよ。

入力形式

D
v_1 v_2 ... v_{2^D}

$v_1,\dots,v_{2^D}$ は深さ $D$ の葉を左から順に並べたもの。

制約

$1 \le D \le 15$

$|v_i| \le 10^9$

入出力例

入力例1

2
3 5 2 9

出力例1

入力例2

3
3 5 6 9 1 2 0 -1

出力例2

概念図：入力例2で実際に枝刈りされる葉

ヒント（段階的開示）

ヒント1（方向性）

ミニマックス法そのものは全ノードを評価すれば求まる。アルファベータ枝刈りは「その計算結果を変えずに、評価するノード数を減らす」ための工夫である。

ヒント2（アプローチ）

再帰関数に「これまでに確定したMAX側の下限$\alpha$」と「MIN側の上限$\beta$」を引数として持たせる。左の子を評価した後、$\alpha \ge \beta$ になった時点で「右の子をどう評価しても親の選択には影響しない」と分かるので、右の子は評価せずに打ち切ってよい。

ヒント3（誘導）

def alphabeta(depth, node_index, alpha, beta, maximizing):
    if depth == D:
        return leaves[node_index]
    left = alphabeta(depth + 1, node_index * 2, alpha, beta, not maximizing)
    if maximizing:
        alpha = max(alpha, left)
    else:
        beta = min(beta, left)
    if alpha >= beta:
        return left   # 枝刈り：右の子は評価不要
    right = alphabeta(depth + 1, node_index * 2 + 1, alpha, beta, not maximizing)
    return max(left, right) if maximizing else min(left, right)

模範解答 (Python)

import sys


def main():
    data = sys.stdin.read().split()
    d = int(data[0])
    n = 1 << d
    leaves = list(map(int, data[1:1 + n]))

    neg_inf = float('-inf')
    pos_inf = float('inf')

    def alphabeta(depth, node_index, alpha, beta, maximizing):
        if depth == d:
            return leaves[node_index]
        left = alphabeta(depth + 1, node_index * 2, alpha, beta, not maximizing)
        if maximizing:
            alpha = max(alpha, left)
        else:
            beta = min(beta, left)
        if alpha >= beta:
            return left
        right = alphabeta(depth + 1, node_index * 2 + 1, alpha, beta, not maximizing)
        return max(left, right) if maximizing else min(left, right)

    print(alphabeta(0, 0, neg_inf, pos_inf, True))


main()

Step-by-Step 解説

1$D=2$の例を手計算
MINノード0の子は葉3,5→$\min=3$。MINノード1の子は葉2,9→$\min=2$。根$=\max(3,2)=3$。

2$D=3$の例で枝刈り発生箇所を実測
評価される葉は3,5,6,1,2の5枚だけ。9,0,-1の3枚は一度も評価されない。深さ2の2番目MAXノード（子は葉6,9）は親から$\beta=5$を受け取り、葉6評価後$\alpha=6\ge\beta=5$となり葉9を評価せず打ち切る。

3打ち切られたノードの返り値は「真の値」でなくてよい理由
本来$\max(6,9)=9$だが枝刈りにより6を返す。しかし親のMINノードは$\min(5,6)=5$も$\min(5,9)=5$も同じ結果。このMAXノードの真の値が$\ge\beta=5$と分かった時点で親がこの子を選ばないことは確定しているため。

4全体の削減率
葉8枚のうち評価されたのは5枚。約37.5%が不要と判定された。葉の並び順によって効率は変わり、最良順序では$O(b^{d/2})$まで落ちることが知られる。

よくあるミス

ミス	原因	正しい書き方
$\alpha,\beta$の更新をMAX/MINで取り違える	手番による更新先を混同	MAXノードは$\alpha$、MINノードは$\beta$を更新
打ち切り条件を`alpha > beta`にする	等号の要否を誤解	等号を含む`alpha >= beta`で打ち切ってよい
打ち切られたノードの返り値を特別扱いしようとする	枝刈りの正しさの理解不足	打ち切り時に返す値をそのまま使ってよい。親の判断には影響しない
全葉を評価しないと根の値が出せないと思い込む	ミニマックスとアルファベータの違いの理解不足	同じ根の値を、少ないノード評価で求められる
ルートを常にMAXと決め打ちし深さの偶奇を無視	`maximizing`の受け渡し忘れ	再帰呼び出しのたびに`not maximizing`を渡し手番を反転

次のステップ

発展: 葉の並び順をソート/逆順にして、実際に評価される葉の枚数がどう変わるか実測してみる。
次回予告: モノトニックスタックによる部分配列の最小値の総和

自己評価

完全理解おおむね理解要復習

Day 152-Q2 — アルファベータ枝刈り（Alpha-Beta Pruning）

問題