オセロの終盤読み切りしてみた話

　少し前からチョコチョコやっていたオセロの終盤読み切りの話です。
　動機は、ただ高速化やってみたいなと思ったらそこにオセロがあったというだけです。やりつくされたネタではあるので、ここに書かれているようなことはググればすぐにヒットします。
　今回僕が目指したのは、現在の盤面から勝ちor引き分けに持っていけるかを判定し、もし勝てるのならば勝つための次の手、引き分けが最善ならば引き分けるための次の手を出力することです。もし負けているのならそれを伝えるだけなので実際に対戦で使うときはその時の処理も考える必要があります。
　主にやったことを時系列順に列挙しておきます。

ビットボード
ハッシュ化
flipを高速化する
コンパイラオプションその他細々とした高速化
速さ優先探索

　ビットボードとは、オセロの盤面は64マスであり、C++のunsigned long longは64bitなのでそれを利用してunsigned long long型の変数二つで現在の盤面を保持するという一般的なテクです。こうすることで多くの処理がビット演算で書くことができるようになり、処理が高速になります。
　ハッシュ化はその名の通り盤面をハッシュ化してメモしておき、同じ盤面が現れたらその結果を使うというものです。盤面はゾブリストハッシュを用いてハッシュ化し、unordered_mapに突っ込むようにしました。なお、ここでゾブリストハッシュの乱数の生成範囲を64bitにしないと衝突しまくって死にます。また、探索した盤面をすべてunordered_mapに突っ込んでしまうとメモリが溢れてしまうので、ある程度の深さまでだけメモ化するようにしました。深さをいくつかに分割してそれぞれハッシュ化するなどの手法も試してみたのですが、速くなりませんでした。
　flipとは盤面の反転処理のことです。各方向での処理をループ展開したり、細々と高速化したりとなかなかに時間をかけたのですが、やはり時間がかかってしまったのでここは諦めて
primenumber.hatenadiary.jp
の記事のコードを借りました。ただ、並列化うんぬんは環境が整ってないので、全方向についてゴリゴリと書いています。
　コンパイラオプションは

-O3 -march=native -flto -mtune=native

このような感じにしました。こんなにいらないと書いてある記事もありましたが、書けば書くほど速くなったので書いておきました。また、一つ一つ言っていたらキリがないですが、細々と高速化しました。着手可能位置については強い人たちはビット演算でオラっとやっているのですが、僕は空きマスの情報を伝播させていき、その全ての空きマスについてflipした後盤面が変化しているかどうかを見ています。ここはまだあまり触れていませんが、改善の余地がありそうです。
　最新の更新では速さ優先探索を組み込みました。これはもっと前にやっていたつもりだったのですが、すっかり忘れていました。今回の僕のプログラムでは、各盤面の探索において勝つ手が一つでも見つかればよいのでできるだけその先の候補が少ない手から試したほうが速く終わるんじゃないかというアイディアを実装した探索です。実際、これでかなり速くなりました。
　たまに気が向いたら開発しているものなので、まだまだ改善すべき場所もありますが、そこそこ速くなった気がしたので公開しておきます。TSGの部員から与えられた22マス空きの盤面に、開発始めのころは3000sほどかかっていましたが今では20sほどまで高速化されました*1。
github.com

*1:速さ優先探索を実装したら20倍ぐらい速くなりました