αβアルゴリズム(1) Minimaxアルゴリズム

　さて、予告通りαβの記事でも書く。まずは、基本のMinimaxアルゴリズムから。

ゲーム木

ノードは局面を表す
エッジは指し手による局面の遷移を表す
リーフノードには数値(評価値)が与えられる

　ゲーム木のリーフノードは究極的には終局面(勝ち負けが決定した局面)となるのが理想である。その場合、リーフノードの評価値は勝ちなら+1、負けなら-1、引き分けなら0とかすればいい。

　しかし、○×ゲームならまだしも将棋などでは終局面まで探索するのは現実的に不可能である。実際には適当なところで打ち切ってリーフノードとする。このとき、局面からその局面の良し悪しを何らかの方法で推定して数値化したものを、リーフノードの評価値とする。局面を入力とし、評価値を出力する関数を評価関数と呼ぶ。このように、局面の情報だけから得られた評価値を静的評価値と呼ぶ。評価関数が局面の優劣を完全に判断できるならば、先読みなんて必要ないわけであるが、実際にはそのような評価関数はないので、ゲーム木探索を実行して、もっと正確な判断を行うことになる。

ゲーム木探索の問題設定

ルートノードにおいて、どのエッジを選択するのが最善か?

ここで問題となるのが、「何を持って最善とするか?」であって、これを決める方法に、子ノードのうち、自分は評価値が最も大きいもの、相手は評価値が最も小さいものを選ぶというものがあって、この方策を用いてゲーム木探索を行うアルゴリズムがMinimaxアルゴリズムである。

Minimaxアルゴリズム

説明は不要だと思う。

negamax形式

Minimaxアルゴリズムを単純に実装しようとすると、自分の手番を表すノードと相手の手番を表すノードを区別しなければならず、面倒である。そこで、相手の手番では評価値に負号を付けることにより、常に最大のものを選ぶようにする。具体的には子ノードの評価値にマイナスをつけてから、最大となる子ノードを選ぶ。これをnegamax形式と言ったりする。今後はずっとnegamax形式で考える。図にすると下のような感じ。リーフノードの評価関数の値のプラスマイナスを、自分の手番か相手の手番かで、決めなければいけない。かなりややこしく、自分は紙に書いて考えても間違えることが多いw

擬似コード

こんな感じ。negamax形式。コードにすると簡単。

int minimax(Node n, int depth){
  if(depth == 0) return eval(n); //静的評価値を返す
  int score = -INF;
  for(nの子ノードcそれぞれについて){
    int g = -minimax(c, depth-1);
    score = max(score, g);
  }
  return score;
}