Negamax法
概念とその効果
Negamax法とはMinimax法を改良したアルゴリズムです。 Minimax法では「白(黒)は、白(黒)にとって局面評価が最も高くなる手を選択する。 黒(白)は、白(黒)にとって局面評価が最も低くなる手を選択する。」 という考えで指し手を選択していましたが、 Negamax法では「白(黒)は、白(黒)にとって局面評価が最も高くなる手を選択する。 黒(白)は、黒(白)にとって局面評価が最も高くなる手を選択する。」 という考えで指し手を選択します。 つまり、「白(黒)にとって局面評価が最も低い」＝「黒(白)にとって局面評価が最も高い」 という考えです。このアルゴリズムを採用することによって、 探索速度が上がるとか、少ないメモリで探索できるといった、 コンピュータの強さに関する改善は得られません。 ですが、プログラムを作る上では手番に関係なく同じ関数を使うことができるようになり、 バグの入り込む余地が少なくなります。 また、この考え方(白にとって良い＝黒にとって悪い)自体が他の探索法と同時に用いることができるため、 一般にどの探索法でも用いられています。
動きの例
この探索法についても、Minimax法で使った例で説明します。可能な着手を生成し、十分な深さで静的に評価するところまでは同じです。
| 自分の手番 | ？ | ||||||||||||||||
 |
 |
 |
|||||||||||||||
| 相手の手番 | ？ | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | ？ | ？ | ||||||||||||||
一手戻ったところの評価値は-1を掛けたものになります。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -5 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | ？ | ？ | ||||||||||||||
次の手の評価値は-2なので、それに-1を掛けて現在の評価値と比べます。 Negamax法では値の大きい手を採用するので、2が評価値となります。
| 自分の手番 | ？ | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | 2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | ？ | ||||||||||||||
最後の手の評価値が-1なので、ルートの評価値は-2となります。
| 自分の手番 | -2 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | 2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | -1 | ||||||||||||||
残りの手についても同様に探索します。 得られた値(2,5,-4)に-1を掛けたものから最大の値を選択するため、 ルートの評価値は最終的に4となります。
| 自分の手番 | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | 2 | 5 | -4 | ||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||
| 自分の手番 | 5 | -2 | -1 | 1 | -5 | 6 | 5 | 8 | 4 | ||||||||
以上のように、着手の決定方法は全て 「得られた評価地に-1を掛けて最大値を選択する」 に統一されていることが分かると思います。
