Minimax法
概念とその効果
ここで紹介するMinimax法は、数多くの探索法の基となっているアルゴリズムです。 考え方は非常に単純で、「白(黒)は、白(黒)にとって局面評価が最も高くなる手を選択する。 黒(白)は、白(黒)にとって局面評価が最も低くなる手を選択する。」 という考え方に基づいて指し手を決定します。
動きの例
例を使って説明します。この例では、 １つの局面について可能な着手が３つづつ、先読み手数は２手先の自分の手までとします。まずは、現在自分の手番です。今の段階ではまだ局面の評価値はわかっていません。
| 自分の手番 | ？ | ||||||||||||||||
続いて、現在の局面から可能な着手を全て生成します。 生成した局面もまた評価値が分かっていないので、値は？としておきます。
| 自分の手番 | ？ | ||||||||||||||||
 |
 |
 |
|||||||||||||||
| 相手の手番 | ？ | ？ | ？ | ||||||||||||||
ここではまず、自分は左端の手を指したと仮定します。 そして相手はこの局面に関して同じように手を生成します。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | ？ | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | ？ | ？ | ？ | ||||||||||||||
次の局面は、コンピュータにとってもう十分先読みしたと判断される深さなので、 コンピュータは局面を静的に評価します。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | ？ | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | ？ | ？ | ||||||||||||||
そして、一手戻したところの評価を仮に5とします。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | 5 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | ？ | ？ | ||||||||||||||
次の手を探索します。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | 5 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | ？ | ||||||||||||||
相手の手番のときは評価値が小さいものを選択するので、 ここでは-2が新たな評価値とされます。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | ？ | ||||||||||||||
さらに、最後の可能な着手を調査します。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | -1 | ||||||||||||||
ここでは、以前に決まった仮の評価値の方がより小さいため、 この手の表価値は-2のままとなります。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | -1 | ||||||||||||||
これで全ての局面を静的に評価しました。 そのため、この局面の評価値を現在の評価値-2とし、 局面を一手戻し、そこの評価を仮に-2とします。
| 自分の手番 | -2 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | -1 | ||||||||||||||
再び自分の手番ですが、まだ探索すべき手が残っているので、 それらの手も同様に探索します。 ルートの評価値は、自分の手番なので最も大きい4となります。
| 自分の手番 | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | -5 | 4 | ||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||
| 自分の手番 | 5 | -2 | -1 | 1 | -5 | 6 | 5 | 8 | 4 | ||||||||
以上のようにして、コンピュータは右端の手を指すよう決定します。 動きが多少分かりにくいかもしれませんが、 全ての探索法の基礎になるためしっかり理解しておいてください。
