edaxが使っている枝刈り手法を説明します。
- stability cutoff: オセロの終盤では「今後絶対にひっくり返らない石」が生じます。これをstable discと呼びます。四隅が最も有名ですが、それ以外にも例えば上下左右斜めの8方向に空白が一切存在しない石は自明にstableです。もちろんその条件に当てはまらない非自明なstable discも存在しえます。 edaxでは「手番側の石のうち自明にstableな石を高速に列挙する関数」を搭載していて、これで手番側の最終スコアの下界を計算できます。その下界がβ値よりも低ければ枝刈りできます。
- (enhanced) transposition cutoff: 置換表にスコアが書かれていればそれで枝刈りできます。また、任意の指し手に対して、それで1手進めた先でtransposition cutoffが生じるかを先に判定してしまうことも可能で、これはenhanced transposition cutoffと呼ばれます。これはオーバーヘッドが少し大きいので、中盤の限られた場面でのみ試みます。
- probcut: 浅く読んだ結果が深く読んだ結果の予測値になっていると考えられますが、edaxではその誤差の標準偏差をモデル化してあります。そのモデルによって一定以上の確率でαβカットされることが予想される場合に探索を打ち切ることができます。これをprobcutと呼びます。上2つと違い完全性が保証されないので完全読みの本筋では使えませんが、move orderingのための読みの中では使えます。
edaxには探索ルーチンがいくつかあります。中盤と終盤とかで色々分けてあるのですが、どれも基本的には以下の手順で探索します。
- stability cutoffなどの枝刈り手法を試し、枝刈りできたらそこで終了。
- 全合法手とそれでひっくり返る石を全列挙する。
- 列挙した合法手各々の有望度を計算する。
- 合法手を有望度で降順にソートする。
- 有望な順にその先を探索する。
2～4番目に改良の余地があります。いくつかの論点に分けて以下で説明します。
まず、edaxはwipeout(=それを打つとすべての石が自分の石になり即勝利する手)を最も有望と評価します。1手詰みで+64点が得られるのですから当然ですね。そして置換表の手が次に有望とみなされます。edaxの指し手評価ではそれらの手は他の任意の手よりも必ず高く評価されます。この設計自体は妥当なのですが、それならば2番目の処理中にwipeoutの手が存在するとわかった時点で残りのmove orderingを全て放棄してβカットしてよくて、そうすると高速化できます。イメージとしては「wipeout cutoff」みたいなのを2番目の処理と同時に計算する感じです。
2番目の処理を終えた時点でwipeoutが見つからなかった場合、3番目の有望度計算をする前に置換表の手の探索を行ってよいです。それでβカットされれば3・4番目の処理を省略できるからです。
wipeoutの手が存在する局面では、置換表に手が書かれているならばそれは必ずwipeoutの手です。ゆえに、置換表の手を探索するのは*2番目の*処理の前とすべきです。まとめると、「置換表の手があればそれを探索する→2番目の処理をやる（置換表の手がなかった場合はwipeoutかどうかのチェックも行う）→3番目に進む」となります。
4番目のソートですが、すべての手を探索する前にβカットが発生しうるので、最初に全部ソートするのではなく「未探索の手のうち有望度最大の手を得る関数」を都度呼ぶべきです。選択ソートを1ステップずつやるイメージです。あるいはヒープソートのように、最初にヒープをO(N)で構築すればsecond best以降の手を得るのはO(logN)で済むみたいな手法を使う手も考えられます。これはエレガントですが、実際にはオセロの合法手は少ないのでヒープソートとかは定数倍遅いと思います。
言い換えると、2～4番目の処理は一つのコルーチンのように書くべきだということです。「有望度最大の手を特定できたらその手をyield returnして、探索結果がβカットでない場合のみ続きを計算する」わけです。ちなみに、これらの点は将棋ソフトでは以前から考慮されていました。将棋では駒を取る手だけを高速に生成するなどの実装が可能なので、タダ取りとか駒得できる手を素早く得ることができます。また、将棋は合法手の数が比較的多い（歩以外の持ち駒があるとすぐ100通りを超えます）ため、ソートのコストも無視できません。
