オセロAI

学内では毎年12月にオセロAIのコンテストが開催されていて、今年は今月の12日にあった。CODE RUNNERと日程が被ってたから学科の友達にAIだけ渡して参加してもらったら優勝できたらしい。今回は1ヶ月前ぐらいから準備を開始したけどそれでも間に合わなかったから来年は今年実装できなかった部分を実装しきって参加したい(参加資格はB3以下だから次がラストになるし)。

書いたコード
github.com

作るにあたって調べたこととか来年の自分に向けてのメモ

参考にしたサイト

ThellというオセロAIのアルゴリズム解説。すごい詳細に書かれていてわかりやすい。 http://sealsoft.jp/thell/algorithm.html

vsOthaというオセロAIのアルゴリズム解説
vsOtha アルゴリズム解説 - 人生きつね色

東大のISで昔オセロAIの大会があったらしくその資料が置いてあるwiki.パワポを見るとオセロAIについて俯瞰できると思う(色々調べていたら上2つのAIはこの時開発されたものらしくてそれを知った時はとても驚いた)。 http://starlancer.org/~is2004/owiki/wiki.cgi?page=%A4%CA%A4%F3%A4%C7%A4%E2%A5%BB%A5%DF%A5%CA%A1%BC

Zebraという強いオセロAIの解説サイトの翻訳
強いオセロプログラムの内部動作

最初に借りた本。基本的なことから書かれていて読みやすかった
www.amazon.co.jp

Thellの開発者が書いた本らしい
www.amazon.co.jp

やったこと

bitBoard
negaScout
move ordering(速さ優先探索)
中盤12手、終盤20手完全読み
ラスト6手からは通常のnegaAlpha
中盤の評価関数はテーブルベース+着手可能数+確定石の数

やってないこと

定石
Book?
パターンを利用した評価関数の学習
並列処理(YBWC?)
キラー応手
置換表(途中までは実装に入ってたけど3日前にバグに気付き修正する時間はないと決めて取り除いた)
Prob Cut
ラスト1手展開
ラストn手展開
SSE4?を使ったビット演算の高速化

感想みたいなの

オセロについては既に研究し尽くされている感じがあって、調べれば調べるほど情報が出てきて楽しかった。
終盤のAIの高速化に殆どの時間を費やしたと思う。FFO test の40の読み切り時間は9秒だったけど、そこまでの高速化はしていないのに思っていた以上の速度が出たのはプロセッサの進歩のおかげなのかな。あとVisual Studiox64のみに向けたバイナリを生成するようにすると実効速度が2倍速くなったけど、これと同じようなオプションってg++にもあるのかな(-m64がそれっぽいけどコンパイルして実行しても効果を感じることができなかった)。
-std::numeric_limits::min(); がオーバーフローすることに気づかず1週間ぐらい溶かした時はとてもつらかった。
それと前日の最終調整中に、ここで0を代入しているのに、coutすると0以外の数値が出力されるバグを見つけてしまって頭を抱えた。原因はVisual Studioでまずい文字コード(BOMなしutf-8)を使用していたせいで日本語コメントを全て取り除いたら期待通りの動作になった。
初めて単体テストを書いてみた。使ったフレームワークGoogle Test.途中まではテストを書きながらコードを書いてたけど、最後の方は締め切りに追われてテストを書いている時間がなかったのでスケジューリングの重要性を感じた。

来年も勝ちたい