OCamlでオセロAIを書いた話

大学の課題でオセロAIを関数型or論理型言語でかけという課題があったのでその記録です。
来年以降の後輩の役にすこしは立つかなーぐらいの気持ちです。

 
githubのリンクは以下です。
github.com

実装したことについてつらつらと書きます。

  • misc

 byte-codeではなくnative-codeを吐くようにコンパイルするとめっちゃ速くなります。

  • bitboard

 盤面を64bitの整数で表現するだけです。
 が、OCamlのintは63bitしかないので、int64というものを使う必要があります。そして、これは遅いです。
 ですがまぁマスクとかで便利なので一応実装しました。できるだけint64の演算をしないように工夫すると速くなります。
 blog.janestreet.com

  • opening book

 いわゆる定石です。
 あらゆるサイトに効果的と書いてあるにもかかわらず、ググれどもググれども定石データベースなるものが見つかりませんでした。
 Logistelloという過去の強いAIの自己対戦10数万局が公開されていたのでそれを利用しました。
 同じ局面が出現したら、Logistelloがどこに何回おいたかを重みづけして確率的にそこを選択します。
LOGISTELLO's Homepage
 parseしたりloadしたりcompressしたりちょっとめんどいですが、かなり強くなります(ちょっとずるい)。

  • flip

 駒をひっくり返す処理です。かなりの頻度呼ばれるのでこれを高速化するのは大事です。
 bitboardを使っているので、以下のようなことをしたくなります。
github.com
 しかし、int64の演算が遅いせいかむしろ遅くなったのでビット演算でかっこ良くやる方針が捨てられます。
 他の方針としては、各行や列について事前に全て計算しておいて計算時にはハッシュテーブルを引くだけにするなどがありますが、今回は愚直に各8方向について1マスずつ見ていきました。
 一応8方向のループを展開して、境界条件などをできるだけ消すなどの高速化はしました。

  • 中盤探索

 中盤でできるだけ深読みをするほうが強くなるのでその高速化です。
 とりあえず愚直にnegamaxを実装して、negaalphaを実装して、negascoutを実装するのが楽です。
 MTD(f)は自分の評価関数に自信がなかったのと安定性が欲しかったのでやめておきました(バグらせそうだし)。
 また、前向きの枝刈りも評価関数に自信がなかったのでやめておきました(これはやると弱くなりました)。
 これらをすると中盤で8手深読みができました。
 以下の記事がかなり参考になります。
www.geocities.jp

  • 完全読み

 最後の方になると全部調べられるのでその高速化です。
 こちらは実装が楽で、negascoutやらなんやらする必要がなく、勝てればおしまい、負ければだめ、それだけです。
 速さ優先探索を実装して、いい感じの手から調べるようにしています。これがかなり効果的です。
 また、最終一手最適化や、ハッシュテーブルの利用、どこの深さまで速さ優先探索をするのかなどのチューニングなどをしました。
 残りマスが19になったら完全読みをするようにしました。
 ビット演算がうまくできないことや、int64が遅いことなどにより結構つらいです(言い訳)。

  • 評価関数

 山の形(ググッてください)、相互の着手可能数、隅におけるか、各マスの重み、確定石が特徴量になっています。
 適当にこんなもんじゃねって言ってパラメータをおいてお気持ちでチューニングしました。
 というのが最終的にbinの中にあるプログラムです。

 が、tuningというbranchが存在していて、実はここで一番時間をかけていたのですが、成果が生めませんでした(その結果上記のような明らかに弱い評価関数となった)。
 チューニング時には特徴量として、隅の2*2の全パターン、辺の半分の1*4の全パターンを追加していました。
 また、パラメータも盤面の進み具合によって分けており、5手ごとに切っていました。
 一般的な手法としては以下の記事に詳しいのですが、教師を持ってきて、石差を目標値にして、各盤面での二乗和誤差の和を最小にするようにチューニングします。
http://sealsoft.jp/thell/learning.pdf
 この手法だと最急降下でうまくいくのですが、個人的には石差を目標値にするのに納得がいかず(だって-1と1って距離2ですけど20と22の2とは違いますよね)別の手法を取りました。
 それは、教師の着手を当てるように学習をすすめるという手法です。
 評価関数は結局最善の手を打つためのものなので、教師の着手を再現できる評価関数が偉いと思い、こうしました。
 具体的にはLogistelloの自己対戦のデータを持ってきて、それを教師にしてパラメータのチューニングをしました。
 しかし、距離関数の定義の仕方がわからず(できない?)、ランダムサーチしたので収束が遅く、あまりうまくいきませんでした(元に比べて少し弱くなったかな程度ではありました)。
 ランダムサーチしたのは以下のブログをみて、グリッドより強そうじゃんって思ったからです。
www.rco.recruit.co.jp
 いずれにせよ、失敗したので元に戻しました(悲しい)。

まとめ

 一番力を入れたところがポシャッたので悲しい。
 去年の一番強かったAIを対戦したところ勝率1割程度でケチョンケチョンにされた。
 今年の中では一応まだ誰にも負け越してない(潜伏勢に負ける気がする)。
 実はRustが言語として許されて強い人たちがそっちに走ったので探索の深さで殴られたら悲しい。