Mini-Max 法

局面の有利さを1つの数で表す評価関数

Mini-Max 法で手を比べるには、まず盤面がどちらにどれだけ有利かを1つの数で表す必要があります。この数を返す関数を評価関数と呼びます。クロード・E・シャノン(Claude E. Shannon)は1950年の論文 Programming a Computer for Playing Chess で、チェスの局面 P に対する評価関数 f(P) の例を示しました。

シャノンの例では、まず駒の数の差に駒ごとの重みをかけて足し合わせます。重みはクイーンが9、ルークが5、ビショップとナイトが3、ポーンが1です。そこから、形の悪い弱い歩の数の差に0.5をかけた値を差し引き、動かせる手の数(機動力)の差に0.1をかけた値を足します。シャノン自身は、この0.5と0.1を粗い見積もりだと断っています。

f(P) の値は、正なら白が有利、負なら黒が有利と読みます。値が大きいほど白にとってよい局面で、小さいほど黒にとってよい局面です。

白は最大を選び、黒は最小を選ぶ

評価関数が1つの数を返すので、白はこの数をできるだけ大きくしたい側、黒はできるだけ小さくしたい側になります。Mini-Max 法はこの対立をそのまま手の選び方にします。

白が今指せる手を M1、M2、M3 のように書き、白が Mi を指したあとに黒が返せる応手を Mij と書きます。白の手と黒の応手の2手先まで読むとき、白が選ぶ手の値は次の式で表せます。

max(i) min(j) f(Mij Mi P)

この式は内側から読みます。内側の min(j) は、白の手 Mi を固定したうえで、黒がその局面を最も小さい値にする応手を選ぶことを表します。外側の max(i) は、そうして求めた値のうち最も大きいものを白が選ぶことを表します。さらに深く読むときは、手番が替わるたびに max と min を交互に重ねていきます。シャノンはこの式を論文の式(1)として示しました。

3つの候補手で計算をたどる

シャノンの論文の Fig.2 は、白に3つの候補手があり、それぞれに黒の応手が3つずつある例です。終端にある9つの局面に評価関数を当て、次の順で白の手を決めます。

まず候補手ごとに、黒が選ぶ最小の値を求めます。候補手1では黒の3つの応手のうち最小の値が +1、候補手2では -7、候補手3では -6 になります。

次に、この3つの値から白が最大を選びます。max(+1, -7, -6) = +1 なので、白は候補手1を指します。

この例で大切なのは、白が終端の値だけを見て一番大きい数に向かうのではない点です。仮に候補手2の先に白にとって大きな値の局面が含まれていたとしても、黒はその応手を選ばず -7 になる応手を返すと考えます。候補手1は、黒がどう応じても +1 を下回りません。Mini-Max 法が選ぶのは、相手の最善の応手を前提にして最も悪い場合がいちばんましになる手です。

求めた値の読み方

根元で得られた値は、その深さまで読んだとき、相手が評価関数の上で最善の応手を返しても確保できる評価値です。Fig.2 の例なら、白は候補手1を指せば少なくとも +1 の局面にたどり着けると読みます。相手が最善でない応手を返せば、得られる値は +1 以上になります。

シャノンは、このように読む深さまですべての手を調べて max と min を交互に当てる方式を Type A strategy と呼びました。

評価関数と読む深さに左右される

Mini-Max 法の計算そのものは機械的ですが、選ばれる手の良し悪しは評価関数に依存します。シャノンが係数を粗い見積もりとしたように、評価関数が局面の本当の有利さからずれていれば、正しく計算しても良い手を選べるとは限りません。

また、調べる局面の数は候補手の数と応手の数の積で増えます。Fig.2 のように各局面から3つずつ枝が出る場合、2手先で 3 × 3 = 9 局面です。同じ枝分かれが続くと仮定すると、3手先では 3 × 3 × 3 = 27 局面になります(この27という数はFig.2の図そのものには無く、同じ枝分かれの数を仮定して延長した見積もりです)。読む深さを1つ増やすたびに枝の数だけ倍率がかかるので、深く読むほど計算量が大きくなります。