最善手の探索方法について

先読み時に自分は最も有利な手を、相手は自分にとって最も不利な手を打つものとして探索を進める方法をミニマックス法と呼びます。ミニマックス法は最も基本的なアルゴリズムとして殆どのプログラムで使用されています。

ミニマックス法では、例えば、64石勝ちに至る進行があったとしても、相手が途中で阻止できる場合には、その進行は最善手とは判定されません。ミニマックス法に基づく評価値は相手がどれだけ頑張っても最低限確保できる有利さを示しています。実際の対局では相手がミスする場合もあるため、通常はミニマックス法で得られた評価値以上に有利な展開が望めます。

αβ探索はミニマックス法に基づく最善手の探索を高速に行うための手法です。探索の途中で採用されることがないと判断できる局面の探索を打ち切ることで処理の高速化を行います。

例えば、幾つかある着手の中で既に10石勝ちできる着手が判明しているとします。さらに、この状況で他着手の探索中にある局面で相手が2石勝ちする着手が発見されたとします。

上記の時点では相手の2石勝ちの着手が最善手かどうかは不明です。しかし、相手の2石勝ちの着手が発見された時点でその局面に至る進行は2石負け以下であることは確定します。ミニマックス法ではその局面での最善手を求めるために残りの着手についても探索が継続されますが、 10石勝ちの着手が他にあるため、2石負け以下が確定しているその局面への進行は100%採用されません。 αβ探索ではこのような場合に残りの着手の探索を行わないようにすることで処理速度を向上させます。

同様の考え方は相手が既に10石勝ちできる着手を発見している場合にも適用できます。この場合にはその着手が存在する局面以降で自身が勝てる手を見つけたとしてもその進行が最善手として採用されることは無いため、その局面の探索を打ち切ることになります。

αβ探索での高速化の度合いは各局面で善手をどれだけ速く発見できるかに依存します。このため、αβ探索を行う場合には、善手をより速く発見するために通常は探索順の順序付け(オーダリング)が行われます。順序付けが優秀な場合には探索速度は大きく向上します。ただし、順序付け処理のオーバーヘッドが大きい場合には処理速度を低下させる危険性もあります。

通常、探索順は浅い先読みを行った結果を利用して決定されています。ただし、終盤では処理のオーバーヘッドが速度向上効果に対して大きくなる傾向があるため、別の手法も用いられます。これらの中で主要なものとしてはFastestFast方式が上げられます。

FastestFast方式では着手可能数が少ない局面から先に探索するように順序付けを行います。着手可能数が少ない局面を辿っていけば、少ない探索数で(早期に)暫定スコアを確定することができます。 αβ探索では確定スコアがあって初めて高速化が期待できますので、早期にスコアを確定することも高速化につながります。

なお、αβ探索では自身および相手の暫定スコアが重要となるため、それらをα値およびβ値として管理します。 αβ探索のアルゴリズム上、評価値がα値とβ値の間にある進行についてのみ探索は継続され、それ以外の評価値が検出された進行については探索が打ち切られます。このため、αβ探索ではα値～β値のことをウインドウ(窓)と呼んでいます。

ヌルウインドウサーチはαβ探索の高速化効果を最大限に利用しようとする探索方法です。ヌルウインドウサーチでは探索開始前にα値とβ値を予め設定しておくことで探索の最初から高速化が行われるようにします。この時、探索対象が最小限となるようにβ値にはα値よりも一つだけ大きな値を設定します。ヌルウインドウサーチはαβ探索のウインドウ幅を0(ヌル)とすることが名前の由来になっています。

ヌルウインドウサーチではα値以下となる局面の探索は最初から打ち切られるため高速化が期待できます。ただし、α値を超える局面が発見された場合には探索は実質的に即時終了するため最善手が発見できる保障はありません。このため、最善手を探索するためにヌルウインドウサーチが利用される場合にはより上位のアルゴリズムと併用されます。ヌルウインドウサーチを利用するアルゴリズムとして有名なものにはNegaScoutとMTD(f)があります。

NegaScoutでは浅い先読みの結果等から最善手と判断した着手についてのみ、まず通常のαβ探索で最善値を求めます。それ以外の着手についてはその最善値をα値、最善値+1をβ値としてヌルウインドウサーチを行います。もし最初に探索を行った着手が想定どおりに最善だった場合にはα値を超える値は検出されません。この場合には最初に検出された最善値が局面の最善値として確定します。 α値を超える値(β値)が検出された場合には、最初に検出された最善値は局面の最善値ではないことが判明します。この場合には、ウインドウ幅を変更してから再度探索を行って次の最善値候補を求めます。

MTD(f)では浅い先読み等の結果から直接αβ値を設定してヌルウインドウサーチを行います。もし真の最善値がα値よりも大きい場合にはヌルウインドウサーチの結果はβ値となります。もし真の最善値がα値と同じか小さい場合にヌルウインドウサーチの結果はα値となります。結果がβ値だった場合にはαβ値をより大きくして同様の処理を再度行います。結果がα値だった場合にはαβ値をより小さくして同様の処理を再度行います。 MTD(f)では最初の探索結果から真の最善値の上限または下限が判明します。次の探索により、さらにその範囲は狭まります。同様の処理を繰り返していくことで範囲はさらに狭まり、最後には最善値を検出することができます。

一般に、MTD(f)はNegaScoutよりも効率的に最善値を探索できるとされています。ただし、MTD(f)では本質的に同一着手を複数回探索するため、置換表の併用が前提となります。また、MTD(f)では最善進行が探索されないため、最善値とともにその進行を知りたい場合には利用できません。

幾つかのプログラムではMTD(f)とほぼ同様の手法をウインドウ幅を1にして使用しています。ウインドウ幅を1にした場合には探索範囲が広がるため、一般的にはヌルウインドウサーチより低速になります。ただし、最初に設定するαβ値が適切だった場合には二度目の探索は不要となり、より高速化される可能性があります。また、最善進行を探索対象とできるため、最善進行を知りたい場合にも利用できます。

多くのリバーシプログラムは序盤から中盤では通常の先読みを使用しますが、終盤では勝敗/完全読みを使用します。勝敗/完全読みが使用するアルゴリズムは通常の先読みと同様ですが、探索対象が異なります。

通常の先読みでは探索する局面の良し悪しは評価関数が出力する評価値によって判定されます。このため、評価値に含まれる誤差の影響から発見される最善局面は真の最善局面では無い可能性があります。これに対して、勝敗/完全読みでは終局までの先読みを行った上で終局時の状態によって局面の良し悪し判定します。このため、発見される最善局面(終局面)は真の最善局面であることが保障されます。

勝敗読みと完全読みはほぼ同様の処理を行いますが、完全読みが終局時のスコアを利用するのに対し、勝敗読みではその符号しか利用しません。このため、完全読みで発見される最善局面ではスコアが保障されますが、勝敗読みで発見される最善局面で保障されるのは勝ち/負け/引き分けの違いのみになります。その代償として、勝敗読みは完全読みよりも高速に探索を終了させることができます。

勝敗読みではスコアの大小が考慮されないため、勝てる手が複数ある場合にどの手を選択すべきかは判りません。このため、勝敗読みを使用する場合には通常はそれ以前に浅い先読み等を行って探索順を決めておきます。この順番に従って勝敗読みを行い、勝てる手が見つかった時点でその手を最善手と見なして探索を終了させます。この場合にも、最善手を選択できる保障はありませんが、多くの場合、善手を選択することは可能になります。勝てる手が無い場合には、引き分けの手が、引き分けの手も無かった場合には浅い先読みでの最善手が選択されます。

リバーシプログラムが先読み/完全読み/勝敗読みを使い分けるのは必要とされる処理時間が異なるからです。勝敗/完全読みは終局まで読みきることが必要となるため、早い段階で使用すると膨大な処理時間が必要になります。これに対して、通常の先読みは終局まで読みきる必要がないため、序盤から使用できます。このため、序盤から中盤にかけては先読みが使用され、終盤で勝敗/完全読みが使用されるようになります。勝敗読みは完全読みよりも高速に処理できるため、完全読みよりも早い段階で使用されます。ただし、最善手の検出が行えないことから、通常はより終局に近づいた段階で完全読みに切り替えられます。