置換表付きアルファ・ベータ法

ウィキペディア小見出し辞書

置換表付きアルファ・ベータ法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/11/07 08:47 UTC 版)

「MTD-f」の記事における「置換表付きアルファ・ベータ法」の解説

MTD(f)はその性質上、何度も同じノードを展開するので、効率改善のために置換表付きアルファ・ベータ法が用いられる。 置換表に前回の計算結果（探索窓の上限値や下限値）を保持しておく事で再探索時の計算を削減する事ができる。 以下に置換表付きアルファ・ベータ法の擬似コードを示す。 node：探索ノード α：探索ノード評価値の下限値 β：探索ノード評価値の上限値 depth：探索の最大深さ function AlphaBetaWithMemory( node, α, β, depth ){ /* 置換表に前回の計算結果があれば利用する。 */ if ( table.Contains( node ) ) { lowerBound = table.GetLowerBound( node ); if ( β <= lowerBound ) /* fail-high */ return lowerBound; /* カット */ upperBound = table.GetUpperBound( node ); if ( upperBound <= α ) /* fail-low */ return upperBound; /* カット */ /* 探索窓を狭められる事がある。 */ α = Max( α, lowerBound ); β = Min( β, upperBound ); } if ( depth == 0 || node.IsLeafNode ) { /* 現在のノードを評価する。 */ g = Evaluate( node ); } else { node.ExpandChildNodes(); if ( node.IsMyNode ) { /* node が自分のノード。子ノードを探索し最大値を得る。*/ g = -∞; a = α; while ( ( child = node.GetNextChild() ) != null ) { g = Max( g, AlphaBetaWithMemory( child, a, β, depth - 1 ) ); if ( β <= g ) { // fail high /* ミニマックス値は g 以上なので g を下限値として置換表に登録する。 */ table.StoreLowerBound( node, g ); return g; /* カット */ } a = Max( a, g ); } } else { /* node が相手のノード。子ノードを探索し最小値を得る。 */ g = +∞; b = β; while ( ( child = node.GetNextChild() ) != null ) { g = Min( g, AlphaBetaWithMemory( child, α, b, depth - 1 ) ); if ( g <= α ){ /* fail low */ /* ミニマックス値は g 以下なので g を上限値として置換表に登録する。 */ table.StoreUpperBound( node, g ); return g; /* カット */ } b = Min( b, g ); } } } /* α < g < β の場合。 Null Window Search の場合にここが実行される事は無い。 */ table.StoreUpperBound( node, g ); table.StoreLowerBound( node, g ); return g; }