ここに書いた内容はかなり高度です。オセロAI初心者の方はぜひオセロAIの教科書を先にお読みください。
ビットボードを使っています。
探索アルゴリズムにはMTD-f法を使っています。Null Window Search(NWS)は置換表つきNegaalpha法を用いています。
置換表は自前実装のハッシュテーブルを使っていて、minimax値の上限と下限が両方保持されています。Egaroucidの特徴は、常に2つの置換表を保持しているところです。
1つは通常の現在探索している深さですでに探索したノードのminimax値の上限/下限を格納しておくもの、もう1つは前回の探索(深さが少ないもの)の結果を格納するものです。
Egaroucidでは一定よりも探索深さが深い場合、反復深化しています。そのときmove orderingに前回の探索の結果を使うためにこのようなことをしています。
枝刈りは後ろ向きなもの(minimax値が厳密に求まる)と前向きなもの(minimax値が厳密には求まらない)があります。Egaroucidでは、後ろ向き枝刈りとしてalpha-beta枝刈りと置換表によるもの、前向きな枝刈りとしてMulti Prob Cut(MPC)を使用しています。
なお、後ろ向きの枝刈りとして確定石によるものを使ってみましたがnps(1秒あたりの探索ノード数)の落ち方が激しい割には訪問ノード数があまり減らなかったので不採用としています。
move orderingには前回の浅い探索の結果によるものと静的評価関数によるものを併用しています。
前回の探索で訪問したノードは、訪問した時点でそれなりに有力であることが期待できるので、その時点でボーナスを与え、それに加えて置換表に格納された値を得点とします。
前回の探索で訪問しなかったノードはその場で静的評価関数にかけて探索順を決定します。なお、ここで使う静的評価関数は適当な仕様で良いはずなので、もっと高速なものに置き換えても良いと思っています。
評価関数は60手を4手ずつの15フェーズに分けた上で、さらに先手と後手で分けた、合計30個のモデルで構成されています。全部合わせて2300万ほどの盤面データを用いてパラメータを調整しました。
評価関数はパターン評価、着手可能位置によるパターン評価、その他特徴量評価の総和という設計になっています。合計24種類、86個の特徴量で、総パラメータ数は23,927,640個です。それぞれ解説します。
パターン評価は強いオセロAIでは一般的な手法です。Egaroucidでは16種類、62個のパターンを使っています。パラメータの調整には最急降下法を用いています。
パラメータ調整についてはオセロソフトThellの作者によるパラメータ調整に関する資料(PDF)に丁寧に記述されています。
着手可能位置をパターンとして抽出し、通常のパターン評価と同様に点数付けしています。
なお、着手可能位置については1つの場所に先手と後手の両方が着手できる場合があるので、先手と後手のそれぞれについて着手できるか否かを表すため2ビット(0から3)で状態を表しています。
Egaroucidには以下の追加特徴量を点数付けして使っています。