Egaroucid 技術資料
ここに書いた内容は高度なものです。一般的なアルゴリズムの話はしません。オセロAI初心者向け記事はこちらに書きました。
このページは日本語のみで、のんびりと気が向いたときに書き足していきます。
minimaxかMCTSか
ゲームAIを作る上でのアルゴリズムは古くからminimax法が有名でした。1997年にチェスで人間を打ち負かしたDeep Blueも、同年にオセロで人間を打ち負かしたLogistelloも、このminimax法から派生するアルゴリズムでした。しかし、2000年に入るとMCTS(モンテカルロ木探索)が発展し、さらに2010年代にはMCTSをさらにアップデートしたPV-MCTS (Policy Value MCTS)が発展しました。2016年に囲碁で人間を打ち負かしたAlphaGoはPV-MCTSです。
この2つのアルゴリズムは根本から違うものです。将棋AIでは聞くところによるとすでにPV-MCTS優勢(2022年現在の伝聞)だそうですが、オセロにおいてはどちらを使うのが良いでしょうか。
オセロにおいてminimax系統が良いのかMCTS系統が良いのかは、まだ断言できないと思います。ですが、私はEgaroucidに対してminimax法から派生したNegascout法を利用しました。この理由について、軽くまとめます。
オセロでは精度の高い評価関数を簡単に作れるから
minimax法では、計算量の問題で終局まで読みきれない場合には終局前に評価関数を使って、それをそのまま終局まで読んだ確定値と同じように利用します。つまり、評価関数の精度が悪ければ必然的にAIは弱くなります。
囲碁では評価関数が作りにくいようで、そのために評価関数を使わなくて済むMCTSが発展したそうです。
オセロにおいては、Logistelloに関する論文「Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello」でパターンを用いた評価関数が提案されてから、(それなりに)手軽に高精度の評価関数が作れるようになりました。ですので、この方法を踏襲すれば良かったわけです。
オセロは合法手数が比較的少ないから
MCTSは評価関数を必要としない以外にも利点があります。それは、合法手が多いゲームでもそれなりの性能が出せるところです。オセロは局面1つに対して概ね10手前後の合法手しかありませんが、例えば囲碁はとんでもないことになります。
各局面の合法手数をb、探索する深さをdとすると、minimax法の計算量はb^d、そしてminimax法に効果的な枝刈りを施したαβ法はsqrt(b^d)です。これでは、合法手が多いゲームでは計算量が爆発しやすくなって困ります。
しかし、オセロに関して言えばこの問題は囲碁などのゲームと比較して大きくありません。
実験してみてあまり強くならなかったから
CodinGame OthelloというオセロAIのコンテストに参加しているときに、minimaxとMCTSを両方試してみたのですが、どうも私の実装ではMCTSがあまり強くなりませんでした。あくまでも私の実装力の範囲の話なので、本当にオセロにMCTSが向いていないのかを議論することはできませんが、とりあえずminimaxを使おうという結論になりました。
完全読みの実装に繋げたいから
Egaroucidでは終盤の決められた手数で完全読みをしてしまいます。完全読みはその名の通り、終局まで完璧に読み切ってしまうことですが、これはminimax系統のアルゴリズムで行います。Egaroucidでは完全読みの際、完全読み以前の探索結果を使うことで探索の高速化を実現しています。中盤探索をMCTSで作るとこのあたりの実装が多少煩雑になることが想像できます。
評価関数
既存の強豪オセロAIに広く使われているパターン評価は、Logistelloで提案され、今日のEdaxまでほとんど形を変えずに受け継がれています。Egaroucidもこのパターン評価をベースにしていますが、少し特徴量を追加しました。
Egaroucidでは石自体をパターンとして評価する既存手法に加え、合法手をパターン化したもの、追加の特徴量の全ての得点の和を評価値としました。
評価関数は2手を1つのフェーズとして合計30フェーズ用意し、それぞれ大量の学習データを用意し、確率的勾配降下法で最適化しました。
石評価パターン
盤面のパターンとして使ったのは以下です。
合法手評価パターン
Egaroucidでは独自の評価パターンとして、合法手のパターンを用いています。両手番の合法手か否かの情報を1マスにつき2bitで割り当て、8マスをセットにしてパターンとしています。
その他の特徴量
Egaroucidではさらに、それぞれの手番について以下の項目を計算し、特徴量に追加しました。- 石が空きマスに接している数
- 合法手数
- 石数