MinMaxとαβ法

MinMax法

先の章で、駒の交換値を計算するプログラムを作ったが、実はあれが「MinMax」（ミニマックス）そのものである。

「MinMax」とは、後手番では評価値が最小（Min）になる（＝もっとも後手にとって有利である）手を選び、先手番では評価値が最大（Max）になる（＝もっとも先手にとって有利である）手を選ぶというアルゴリズムである。

この「MixMax」は、「二人ゼロ和完全情報ゲーム」向けのアルゴリズムである。

「二人」は「プレイヤーの人数」、「ゼロ和」は、「一方が得をすればもう一方が必ず損をすること」（すなわち、二人のプレイヤーの合計得点が０になるゲーム）。

「完全情報ゲーム」とは、たとえばマージャンやトランプのゲームのように、自分から見えない部分（マージャンなら「相手の手牌」や「ツモ山」、トランプでも「これから引いてくるカード」や「相手のカード」）がある「不完全情報ゲーム」ではなく、「そのようなものがない＝完全に相手の情報も自分の情報も得られるゲーム」のことである。

MinMax法は、「二人ゼロ和完全情報ゲーム」で、かつ「有限ゲーム（有限の手数で終わることが保障されているゲーム）」であれば、理論的には完全に解くことのできるアルゴリズムである。

理論上は、後手の勝ちを－１、先手の勝ちを＋１、引き分けを０とおいて、読む深さを無限にすれば結果が必ず得られる。（ただし、膨大な…天文学的な時間がかかる。）

しかし、序盤から先手か後手の勝ち（または引き分け）がはっきりするまでを読むことは、現在のコンピュータではとうていできない。そのため、深さに制限を設け、一定の深さで評価関数を用いて評価し、もっとも良かった結果とその手順を得るというのが普通の使い方になる。

では、普通のMinMaxアルゴリズムを実際に記述してみよう。

// ある深さでの最善手順をしまう配列
Te Best[MAX_DEPTH][MAX_DEPTH];

int Sikou::MinMax(int SorE,const Kyokumen &k,int depth,int depthMax)
{
  Te teBuf[600];
  if (depth==depthMax) {
    // 現在の局面の評価値を返す。
    return value;
  }
  int teNum=GenerateLegalMoves(teBuf);
  if (teNum==0) {
    // 負け
    if (SorE==SELF) {
      return -INFINITE;
    } else {
      return INFINITE;
    }
  }
  int retval;
  if (SorE==SELF) {
    retval=-INFINITE;
  } else {
    retval=+INFINITE;
  }
  for(i=0;i<teNum;i++) {
    Kyokumen kk(k);
    kk.Move(teBuf);
    int v=MinMax(SorE==SELF?ENEMY:SELF,kk,depth+1,depthMax);
    if ((SorE==SELF && v>retval) || (SorE==ENEMY && v<retval)) {
      retval=v;
      Best[depth][depth]=teBuf[i];
      for(int i=depth+1;i<depthMax;i++) {
        Best[depth][i]=Best[depth+1][i];
      }
    }
  }
  return retval;
}

最大深さ「３」でMinMaxを使った場合に、どのようにプログラムが動くのかのイメージを図１、図２に示した。

図１
図２

ここでは、３手先まで、２つの分岐があるので、２３＝８の指し手の進む可能性があることになる。

MinMaxアルゴリズムでは、１手先を読むごとに、その手番のプレイヤーの可能な手をすべて読まないといけないことが分かってもらえるだろうか。

図１では、Ａ→Ｃ→Ｇ→Ｎと進むのがお互いに最善で、その時に評価値は６５となる。

将棋では、１手で平均可能な着手の数が約８０と言われている。つまり、３手先を読むには、平均的には「８０×８０×８０＝５１２０００手」を読む必要がある。本書のプログラムは、かなり高速に作っているつもりだが、５１２０００手を読むとなると、２秒程度はかかるだろう。もし、このまま４手先を読もうとした場合には、さらに８０倍の時間がかかる計算になるので、１手指すのに１６０秒（＝約３分）と耐え切れない遅さになる。

なお、実際には、序盤では着手の数は３０程度と少なく、終盤では２００程度と増えるので、終盤では、「２００×２００×２００＝８００００００手」を読む必要があったり、序盤ではその逆に「３０×３０×３０＝２７０００手」しか読む必要がなかったりする。そのため、序盤では４手の深さまで読んでも高速に動いていても、終盤になってきた途端にとんでもなく遅くなる可能性が高い。

３手先読みでも１０分位、４手先読みでは１時間近くかかる場合があると思われる。

MinMax法の理論上の計算量は、「ｂｄ」で表わされる。ここで、「ｂ」は１手あたりの枝分かれの数（branch factor）、「ｄ」は読みの深さ（depth）である。

αβ法

「αβ法」は、MinMaxと同じ結果を得られるにもかかわらず、理論上の計算量は、もっとも条件の良い場合で約「ｂｄ／２」となり、MinMaxと比較した場合、同じ時間でほぼ二倍の深さまで読めるという素晴らしいアルゴリズムである。

「αβ法」では、探索の際に、「αカットとβカット」という手法を用いる。これは、探索する必要がない枝を探索しないための工夫である。αカット/βカットの様子については、図３を見てほしい。

図３

次の図（図４）は、MinMaxの節の図１と同じ探索木をαβ法で探索した場合の様子である。「αカット」「βカット」により、MinMaxと比べて、どれくらい探索の量が減っているか比べてみてほしい。

図４

残念なことに、Ｋが探索されなかったというだけの成果しか出ていない。それには理由があるのだが、後で詳述する。

「α」「β」という範囲を決めて、範囲外の値がきたら、直ちにその探索を打ち切ってよいというのがαβ法のミソである。

「α」「β」の範囲は、普通は「－∞」「＋∞」からはじめるが、この幅を縮めることで高速に探索が行なわれる。ただし、その場合には、必ずしも最善手順及び最善手順での評価値が得られるとは限らなくなるが、返してくる値は、α以下であれば得られる評価値の上限を示す値、β以上であれば、得られる評価値の下限を示す値になる。（厳密には、αβ関数がSoft-failと言う方法で実装されている必要がある。）

そのため、いったんβの値を「β＝α＋１」として、極限までαβの幅を小さくして高速に探索（NullWindow探索）した後、もともとのαを超え、もともとのβ以下の結果が得られたら、αを返ってきた値とし、βを元のβの値に戻して再探索する、また、元のβを超える結果が返ってきた場合にはそのままCut-offする、という高速化の手法が知られている（Scout）。

以下のプログラムは、普通のαβ法である。

// ある深さでの最善手順をしまう配列
Te Best[MAX_DEPTH][MAX_DEPTH];

int Sikou::AlphaBeta(int SorE,const Kyokumen &k,int alpha,int beta,int depth,int depthMax)
{
  Te teBuf[600];
  if (depth==depthMax) {
    // 現在の局面の評価値を返す。
    return value;
  }
  int teNum=GenerateLegalMoves(teBuf);
  if (teNum==0) {
    // 負け
    if (SorE==SELF) {
      return -INFINITE;
    } else {
      return INFINITE;
    }
  }
  int retval;
  if (SorE==SELF) {
    retval=-INFINITE;
  } else {
    retval=+INFINITE;
  }
  for(i=0;i<teNum;i++) {
    Kyokumen kk(k);
    kk.Move(teBuf);
    int v=AlphaBeta(SorE==SELF?ENEMY:SELF,kk,alpha,beta,depth+1,depthMax);
    if ((SorE==SELF && v>retval) || (SorE==ENEMY && v<retval)) {
      retval=v;
      Best[depth][depth]=teBuf[i];
      for(int i=depth+1;i<depthMax;i++) {
        Best[depth][i]=Best[depth+1][i];
      }
      if (SorE==SELF) {
        alpha=retval;
      }
      if (SorE==ENEMY) {
        beta=retval;
      }
      if ((SorE==SELF && retval>=beta)||(SorE==ENEMY && retval<=alpha)) {
        return retval;
      }
    }
  }
  return retval;
}

αβ法で、理論上の最高速度を得るには、探索の順番が完全に良い評価を返す順にソートされている必要がある。図５に、理論上の最高速度を得られるように人為的に図１の探索木をソートした場合の図、図６に図５をαβによる探索を行った場合の動作を示す。図４の探索の量と比べてみて欲しい。

図５　ソートされた探索木
図６　図５に対する探索の様子
理想的な順序に並んでいるとＬ，Ｅ，Ｋ，Ｊの探索が省略される

図５のように完全にソートされているようなことは、実際上はありえない（そもそも、完全に良い順に並べられるなら、探索する必要もないだろう）が、探索の順番を工夫することで大きな高速化が望めることは確かである。そこで、とりあえず、１手読み＋交換値の結果でソートすることにしてみて、プログラムを書いてみたのが以下である。

int Sikou::AlphaBeta(int SorE,const Kyokumen &k,int alpha,int beta,int depth,int depthMax)
{
:
  // 手の価値を仮に求めてみる
  for(i=0;i<teNum;i++) {
    Kyokumen kk(k);
    kk.Move(SorE,teBuf[i]);
    teBuf[i].value=kk.value+kk.BestEval(SorE==ENEMY?SELF:ENEMY);
  }
  for(i=0;i<teNum;i++) {
    int max=teBuf[i].value;
    int maxindex=i;
    for(int j=i+1;j<teNum;j++) {
      if (teBuf[j].value>max) {
        max=teBuf[j].value;
        maxindex=j;
        swap(teBuf[j],teBuf[maxindex]);
      }
    }
  }
  // αβ本体
  int retval;
  if (SorE==SELF) {
:
}

さて、これで元のαβより早くなるかと言うと…全然早くならない。原因はいくつか考えられるが、

というところだろうか。この辺りは、バランスの問題なので非常に難しい。もっと正確に手の順序付けを行い、さらに手の価値の低い手は先読み自体を行わないことで速度を上げたプログラムは７章で登場する。

その前に、５章と６章では探索そのものの速度を工夫によりもっと上げることを試みてみる。

ここまでのソースコードは、chapter04-02フォルダに収録している。

「MinMax」と「NegaMax」、「αβ」と「Negaαβ」

MinMaxは、

Max(Min(Max(a,b),Max(c,d),...Min(Max(e,f),...),...)
というような式で書けるわけだが、これを以下のように変形できる。 
Max(-Max(-Max(a,b),-Max(c,d),...-Max(-Max(e,f),...),...)
このように書き換えたアルゴリズムを「NegaMax」と呼ぶ。

MinMaxとNegaMaxは全く等価な方法である。また、「αβ法」も「NegaMax」形式に書き換えられる。ここでは、そのように書き換えたαβ法のプログラムを「Negaαβ」と呼ぶことにする。

ただし、一般的にはαβ法と言った場合、この「Negaαβ」を指す事が多い。前述の「Scout」も、通常は「NegaScout」の方が一般的である。

こうすることで、ほんのちょっとだけプログラムが簡潔になるというメリットがある。

では、αβ法をNegaαβに書き換えてみよう。

int Sikou::NegaAlphaBeta(int SorE,const Kyokumen &k,int alpha,int beta,int depth,int depthMax)
{
  Te teBuf[600];
  if (depth==depthMax) {
    // 現在の局面の手番から見た評価値を返す。
    if (SorE==SELF) {
      return value;
    } else {
      return -value;
    }
  }
  int teNum=GenerateLegalMoves(teBuf);
  if (teNum==0) {
    // 負け
    return -INFINITE;
  }
  int retval=-INFINITE-1;
  for(i=0;i<teNum;i++) {
    Kyokumen kk(k);
    kk.Move(teBuf);
    int v=-AlphaBeta(SorE==SELF?ENEMY:SELF,kk,-beta,-alpha,depth+1,depthMax);
    if (v>retval) {
      retval=v;
      Best[depth][depth]=teBuf[i];
      for(int i=depth+1;i<depthMax;i++) {
        Best[depth][i]=Best[depth+1][i];
      }
      if (alpha<retval) {
        alpha=retval;
      }
      if (retval>=beta) {
        return retval;
      }
    }
  }
  return retval;
}

「α」と「β」にプラスマイナスを付けてひっくり返したり、返ってきた結果にマイナスを付けてひっくり返したり、末端の評価を返すときに後手番だったら後手番から見た評価値を返さないとならなかったり（value は先手番から見た評価値なので、それにマイナスをつけて価値をひっくり返したもの）と、アルゴリズムを理解するのは大変だが、アルゴリズムそのものは少し単純化されている。

以降の章では、このNegaαβ形式のプログラムを元に、改良を行なっていく。

この節のソースコードはchapter04-03フォルダに収録している。

前ページ
次ページ
索引ページへ