ゲーム探索の基本「ミニマックス法」をおさらいしよう

たまたまTwitterで将棋ソフトの探索について話題になったのと、最近暇つぶしにぴょんぴょん将棋のAIなんかを作って遊んでいたので、そういったゲームでの探索(先読み)の基本となるミニマックス法について簡単に説明してみようと思った。
ミニマックス法の原理は非常にシンプルでいながら合理的な方法なので、知っておいて損は無いと思う。

ゲーム木について

下の図のように、現在の局面から1手ずつ進めるときにあり得るすべての局面をツリー構造で示したものをゲーム木という。

上の図は、各局面で指し手が常に3通りずつあるようなゲームの3手先までを想定したゲーム木である(3手後に関しては図のサイズの関係から右側は省略しているが)。
別に難しく考える必要は無くて、単に1手後、2手後、3手後にあり得るあらゆる局面を抽象的に書きだしただけである。

評価関数について

ミニマックス法による探索では、このゲーム木と評価関数を使用する。
コンピュータ将棋に触れたことがある人ならば、評価関数という言葉は聞いたことがあるだろう。
評価関数は、その局面そのものがどのぐらい有利・不利なのかを定量的に判定する。
例えば駒得していればプラスとか、と金を作られているからマイナスとか、そういうのを計算していって最終的に点数を付けてくれる。
(余談だが、最近流行りのニューラルネットワークを用いた評価関数ではそういう人間に分かりやすい点数の付け方はしておらず、局面そのものを評価しに行っている)

局面に点数を付けて評価できるならば、先を読む必要が無いのではないか、と思うかもしれない。
確かに1手先の正確な評価値が分かるならば、その中で最も良い局面になるように指し手を選べばよいという事になる。
ただ現実的には、そんな完璧な評価関数を作ることは難しい。というよりも完全解析がなされているゲームでもない限り事実上不可能である。
だからこそこれから解説する探索と組み合わせることによってより正確に局面を評価するわけである。

ミニマックス法

ではいよいよ本題のミニマックス法についての解説に入る。

まず初めに、ある決まった深さ(手数)分のゲーム木を作成する。今回は先ほども掲載した3手先まで展開したゲーム木を用いることにする。

そしてその末端局面(一番手数が先の局面)に対して評価関数を適用して評価値を算出する。評価値は大きい方が自分にとって有利であることを意味している。
なお大事なことであるが、今回表示する評価関数は全て「自分から見た点数」であることに注意してほしい。

今回は仮に以下のようになったと考える。

さて、今回の末端局面は3手後である。
上の図から分かるように、自分が着手することで2手後から3手後の局面に進むわけである。
ということは、評価値が分かっている自分からすれば、自分にとって最も良い局面を選ぶことが出来るはずである。

例えば上の図で局面A-aの状態で自分の手番が回ってきたならば、局面A-a-1～3を比較して最も評価値が高い局面A-a-1を選ぶはずである。

ということは、そこから逆算するならば、局面A-aの評価値は局面A-a-1と同じと考えてよいはずである。なぜなら局面A-aにたどり着いたなら絶対に局面A-a-1に遷移するのだから、その二つの局面は同一視して良いからである。

つまり、自分の手番である場合には次の局面の中から最も高い評価値がその局面の評価値になるということが出来る。
今回のゲーム木ならば以下のようになる。

さて、同様に1手後の局面の評価値を求めたいわけであるが、1手後から2手後の局面には今度は相手の着手によって移行する。
ということは、今度は相手にとって最も良い局面を選んでくるはずだと考える。

例えば局面Aだったならば、局面A-a～cを比較して最も評価値が低い(相手にとっては最も良い)局面A-cを選んでくるはずである、と想定する。
したがって、先ほどと同じ考え方で局面Aの評価値は局面A-cの評価値である-1に等しいと考えることが出来る。

すなわち、相手の手番である場合には次の局面の中から最も低い(=相手から見れば最も高い)評価値がその局面の評価値になるということが出来る。
今回のゲーム木ならば以下のようになる。

さて、最後である。
現局面から1手先には自分の着手で進むのであるから、1手先の局面の中で最も評価値の高い局面へと進めればよいという事になる。
したがってこの場合では局面Aに進むのが最善で、その結果現局面の評価値は-1である、という事が分かるわけである。

これがミニマックス法の原理に基づいた最善手の探索である。
そしてこの場合で言えば、現局面からは
局面A　→　局面A-c　→　局面A-c-2
と進む、というのが読み筋だという事になる。

相手が最善手を指さない場合について

さて、自分は自分の評価関数で局面を評価するので、最も評価値の高い局面を選ぶというのは理解できると思う。
しかし相手にはこの評価値は見えていないはずである。ソフトならソフトごとに違う評価関数を持っているし、また相手が人間ならばミニマックス法とは違う方法で読んでいるはずである。
すなわち、当然ではあるが相手は自分の読み筋通りの手を選ぶとは限らないわけで、にもかかわらず自分の評価関数の値だけで相手の手を選んでも良いのかという部分に疑問を持つかもしれない。

しかしこれがミニマックス法の特徴であるのだが、ミニマックス法で得られた評価値というのは、実は「自分が最善手を指し続ける限り、最低でもこの評価値の局面にたどり着く」という事を意味している。
つまり上記の例で言えば、探索に用いた3手先の局面を迎えた時点では、その局面自体の評価値は相手の選択に関わらず絶対に-1以上になっているのである。

上の例で試してみよう。
仮に局面Aから相手が局面A-aに進めてきたとする。
すると自分は局面A-a-1に進めることで、評価値6の局面にたどり着くことが出来る。これは最初に読んだ評価値である-1よりも大きな値になっている。
他のパターンも試してみて欲しい。途中で気が付くと思うが、要は2手目の局面として相手にとって最も都合の良い局面を逃した時点で評価値は-1を超えるのである。

今回は3手先までしか読んでいないが、これがもっともっと深くまで読んだ場合でも同じである。
手順の途中で相手が間違えれば必ずミニマックス法で求めた評価値よりも良い局面にたどり着くことが出来る。

これを言い換えれば、現局面でミニマックス法を用いて選んだ手というのは、他の手に比べて「相手が最善手を繰り返してきた時に最もマシな局面にたどり着くことが出来る手である」という事が出来る。
要は上の例で言えば、局面Aを選んでおけばどんなに悪くても評価値は-1で収まるが、局面Cを選んでしまうと相手が最善手を繰り返してきたときには評価値が-4になってしまうので、比較すれば局面Aの方が優れていると考えるわけである。
ミニマックス法に基づく最善手というのはこういう意味である。

最初の方で、完璧な評価関数を作ることは難しいから探索と組み合わせることで精度を上げるのだという話をしたが、これもこのミニマックス法の特徴に関係している。
1手先だけ読んで、評価関数が「これが最善」と示してきても、評価関数の精度が高くなければあまり信用できるものではない。もしかしたら実はマイナスな手なのに誤ってプラスだと言っているのかもしれない。
しかし、はるか先の局面まで読んだうえでミニマックス法を用いて「この手を選んでおけばどんなに悪くてもこの点数になるよ」と示してくれたならば、それが大きく外れている確率は小さくなるはずである。
単発で最高値を示されるよりは大量の局面を探索した結果として最低保証ラインを示してくれた方が、評価関数自体の精度は低くてもより正しい結果である可能性が高まるのである。

それでも指し手が進むと評価値が下がることがあるのは？

さて、ミニマックス法を用いると最低保証ラインを示してくれるという話をしたが、しかし実際はコンピュータの評価値がどんどんと下がっていくというのは普通にあるのもご存知だと思う。これはどういう事だろうか。

ミニマックス法ではある深さまでゲーム木を展開し、そこから現局面まで遡るようにして評価値を決めた。
前述の例なら3手先まで読んでいるわけであるが、ここに落とし穴がある。
つまり4手先以降の局面のことは全く考えていないのである。

例えば4手先である相手の手番に絶妙手が存在していて、評価値が急落するような変化があったとする。
しかし3手先までしか読んでいない場合はその手を見落としてしまうので、3手目の局面が一見よさげだからと高い評価値を付けてしまい、その局面に進んでしまうかもしれない。
そして2手進んで再び自分の手番になってから改めてゲーム木を作って読み直してみると、そこで初めて絶妙手の存在に気が付き評価値が急落するということが起こるわけである。
(先ほどの4手先は今度の2手先なのでゲーム木の中に現れる)

つまり先ほど「最低保証ラインを示してくれる」と言ったのはあくまで「探索に使ったゲーム木に含まれる局面の範囲では」という注釈が付くのである。
上の例なら、3手先までなら確かに評価値が-1を下回ることは無いのであるが、4手先以降の局面ではどうなるか分からないのである。

実際、コンピュータ将棋においてもまだプロと戦っていたころは「プロ的には容易に読める30手以上の詰み」のように(人間的には)一本道だが長手数の読みが力を発揮するような局面ではプロがコンピュータを上回るということもあった。
つまり特定の条件が揃えば、20手先までのありとあらゆる変化のゲーム木を作るコンピュータよりも、指し手を感覚で取捨選択して30手先まで一直線に読み切ってみせるプロの職人技が上回るという事が起こるのである。

こういったことを避けてより強くするためには、1つはより深く読むこと、もう1つは評価関数を改良して大きく外れた評価値を出しにくくすることの2つの方法が主に考えられる。

より深く読むには、持ち時間が決められている以上はより高速で読む必要がある。
しかし、上記の例で示したゲームならば1手進むごとに局面の種類は3倍になっている。つまりn手先の局面は3^nパターン存在するという事である。
指数関数が急激に増えていくのは御存知だと思うが、今現在よりもたった1手深く読めるようにするだけでも相当な改良が必要になる。
なので実際はミニマックス法が素のまま使われることは多くなくて、無駄な探索を省いたり、主要な変化だけ深く読んだりといった様々な工夫が施されている。

ただそれと同時に、読む速さはハードウェアの性能によっても変わってくる。
ソフト的には何も変わっていなくても、ハードウェアの性能が何倍にもなればそれだけで同じ時間でより深く読めるわけである。
最近はトップ棋士が高性能なコンピュータを購入しているというのが話題になることが多いが、その理由の1つがこれである。
(もう1つの理由はDL系のソフトを使うためには高性能なGPUが必要なため)

まとめ

ミニマックス法という探索方法について分かりやすく解説したつもりであるが、伝わっているであろうか。
この考え方は多くのゲームに適用できるし、またゲーム以外でも様々なやり取りをミニマックス法でモデル化することが出来る。
「最低でもこうなる」と保障される(ただし読んだ範囲で)という特徴は結構便利なものであるので、考え方として覚えておいて損は無いと思う。