Minimax法

ノード評価値(evaluation value)


AND/ORグラフの各ノードに評価値を与える ことを考える．

評価値とは，与えられたノードがエージェントに とってどのくらいの価値があるかを実数で表現したもの．

ゲームの場合は，自分が勝利した局面(ノード)に+∞を与える．
相手が勝利した局面(ノード)に-∞を与える．引き分けの場合は0である．

問題分割の場合は，分解した問題が解決した場合に+∞を与える．
解決不能の場合には-∞を与える．

基本Minimaxアルゴリズム


　

proc minimax(n: node) begin <nの下にある全てのAND/OR木を展開する>; <nの下の全ての終端ノードの評価値を決定する>; repeat p ← <全ての子ノードの評価値が定まっているノードで，まだ評価値 が定まってないもの> if <ノードpからOR分岐がある> then <pの評価値←子ノードの評価値の最大値> else if <ノードpからAND分岐がある> then <pの評価値←子ノードの評価値の最小値> until <評価値の定まっていないノードがない>; end

基本Minimaxアルゴリズムは，与えられたAND/OR木のノードの評価値を木 の終端ノードからボトムアップ(bottom up)に 計算する．



ORノードは最大化ノード(maximizing node)，ANDノードは最小化ノード(minimizing node)と呼ばれる．

巨大なAND/OR木に対しては非現実的な(全てのノードを展開するのには大 きな記憶容量を必要とする)アルゴリズム．

　

ノード評価関数(evaluation function)


AND/ORグラフの全てを展開することなく，途中のノードに対して好ましさ を表す関数．



評価関数fを用いた深さ制限Minimaxアルゴリズム


　

proc depth-bounded-minimax(n: node) begin L ←[n]; while n ≠car(L) ∨<nに値が対応付けられていない> do begin x ←car(L); if <xに値vx が対応付けられている>; then begin x ←pop(L); p ←<xの親>; vp ← <現在pに対応付けられている値>; case <ノードpのタイプ> of 最小化ノード: vp ← min(vp, vx); 最大化ノード: vp ← max(vp, vx); end end else if <xが終端ノードである>∨<深さ限界に達した> then <xにf(x)を対応付ける> else begin case <xのタイプ> of 最大化ノード: vx ← -∞; 最小化ノード: vx ← +∞; end <xの子供をLの先頭に追加する>; end end end



ゲーム木探索演習問題1

...Return

• 講義の詳細