ネガマックスの説明がどこもおかしい件 - やねうらおブログ(移転しました)

αβ探索は簡単なコードではあるが直感的には理解しづらい。熟練したプログラマでも慣れていなければ理解しにくい。

「αβ探索ってなんぞや？」って言う人はこの時点でブラウザを閉じてお戻りください。ここから先に腹がよじれるような面白いことは何一つ書いてませんので。

さて、αβ探索が理解できないならMinMax法から勉強しなおすべきで、MinMax法の基本的なコードが次のコードである。

「ミニマックス法」(Wikipedia)
http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95

上のMinMax法のコードは自分は局面評価が最大になるものを選び、相手は局面評価が最小になるものを選ぶ。簡単明瞭なコードである。つまり、ここで言う局面評価関数(上記コードの STATIC_VALUE )は常にこちら(探索開始局面の手番側)から見たスコアである。こちらが有利であればプラスの値、こちらが不利であれば負の値を返す関数だろう。だからこそ相手はこのスコアが最小になるものを選ぶのが相手にとっては一番得なのである。

ところで上のソースコードは次のように書き換えられる。
Wikipediaの「ミニマックス法」の上のコードのすぐ次に以下のコードが掲載されている。

これは、いわゆるNegaMax法である。自分と相手とで場合分けするのではなく一本化したわけである。そのためのトリックが

 score = -NEGA_MAX( children[i], depth-1);

のマイナス符号の部分である。最大を探すコードだけしかなくとも、scoreを受け取るときにマイナス符号をつけておけば最小を探すことが出来るというコードのリサイクルの精神に基づくものである。

いやまぁ、そんな説明はどうでも良くて、たぶん上のコードはアルゴリズムの教科書にはNegaMax法としていたるところで散々既出。いまさら取り上げるほどのことじゃないよね、うん。

だけど、この前者と後者のコード、よーく見比べると前者と後者とは等価じゃないことに気づく。

例えば、depth(残り探索深さ) を 1にして呼び出すと…
・前者のコードは、(探索開始局面は「自分の局面」のはずで)、STATIC_VALUEが最大になる値を返す。
・後者のコードは、-NEGA_MAXという形で呼び出すので、STATIC_VALUEが最小になる値を返す。

おやおや？

つまり、前者のコードと後者のコードが等価になるためには、後者のコードのSTATIC_VALUEは、相手の手番においては符号を反転させて返す(そのときの手番から見たスコアを返す)関数でなければならない。前者のコードのSTATIC_VALUE関数は、つねに自分(探索開始局面の手番)から見たスコアを返すというのに…。

それで、このように前者のコードのSTATIC_VALUEと後者のコードのSTATIC_VALUEが異なる仕様になっているのに、同じ関数名のままにしておいて、しかもこの部分に言及がなくて、「前者と後者のコードは等価ですよ」みたいな紹介の仕方は非常にまずいと思う。

あまりに気になったもので、Web上のNegaMaxの説明を見て回ったのだが、見たところほぼすべてのNegaMaxの擬似コードが上記の後者のコードと同等のコードであり、そして同時に前者のコードと同等のコードが掲載してあって、その両者が等価であるかのように書いてあるサイトが多数あって、この部分についてきちんと言及しているサイトは私は一つも見つけられなかった。

たぶんこれらの擬似コードはNegaMaxアルゴリズムを最初に書かれた本か何かからの引用なのだと思うのだが、このような状態で広く普及してしまっている。

どこのサイトがどこのサイトをパクってどう伝播して行ったのかを調べると非常に面白いことになると思うのだが、まあ、それは私は興味がないのでどうでもいいや。

以前、私が「αβ探索」や「MinMax法」を調べたときは、Wikipediaには項目すらなかったと思うのだけど、こうやっていろんな本からコードをパクり、いや引用して、Wikipediaのような情報集合体を作るのって、本当に権利的な問題がないのだろうか。現行法では問題ないんだろうけど、これが本当に許されていいんだろうかと少し疑問ではあるのだが。