アルファベータ法 (RunRunDietOnline)

アルファベータ法

アルファベータ法（αβ法、alpha-beta prunning）は不必要な枝の評価を省略（枝刈り）することで、
ミニマックス法と同じ値を高速に返すアルゴリズム
よい手から順に読むほど枝刈りが起こる確率が高くなる → 固定順序付け、動的順序付け参照

int alphaBeta(uint64 black, uint64 white, int alpha, int beta)
{
    if( 末端ノード )
        return eval(black, white);
    if( 黒の手番 ) {
        for(m = すべての黒の着手について) {
            着手を実行;
            int ev = alphaBeta(black, white, alpha, beta);
            if( ev > alpha) alpha = ev;
            着手を元に戻す;
            if( alpha >= beta ) return alpha;   // αβカット
        }
        return alpha;
    } else {
        for(m = すべての白の着手について) {
            着手を実行;
            int ev = alphaBeta(black, white, alpha, beta);
            if( ev < beta) beta = ev;
            着手を元に戻す;
            if( alpha >= beta ) return beta;    // αβカット
        }
        return beta;
    }
}

参考：ネガアルファ法、ネガスカウト法、探索アルゴリズム

このページへのトラックバックURL： http://vivi.dyndns.org/wtb/265
4,319 page views, page owner : びびすけ
2006/09/30 14:23 modified by びびすけ