リバーシAIを実装した話(FL実験2019)

理学部情報科学科の関数論理型言語プログラミング実験の最終課題でリバーシAIを実装したので過程のメモです
とりあえず僕が提出したものはここにあげてます。
github.com

言語は関数論理型なら相談すれば許可されるようでしたが僕は諸々のインターフェースが提供されているOCamlで実装しました。
Prologで実装する人を見てみたい...あとなぜか手続き型であるところのRustが許可されていました。
課題が締め切りの1ヶ月前に公開されたのですが余裕がなくて結局試験期間中に合間を縫ってやったのと試験後2日で仕上げました。

中盤終盤探索

nega-max,nega-alpha,nega-scout,MTD(f)の順くらいで実装しようかな〜とか思ってたんですが結局nega-alphaまでしかやりませんでした(怠惰)
とりあえずなにも考えずにnegamaxで終盤読み切りを書いて、その後nega-alphaに変えて枝刈りを入れました。
終盤10手読み切りその他ランダムでランダムに勝率8割くらいで思ったより低いなぁと感じたので適当な評価関数で終盤以外も4手読むようにすると100戦100勝になりました。

bitboard

与えられた雛形のボードの処理はとても重いので64bit整数2つ(各ビットが64マスに対応)のbitboardモジュールを書いてそれに切り替えました。
実装はオセロをビットボードで実装する - Qiitaが参考になると思います。
この時点でランダム性はないのでbitboardを導入しても変わるはずのないのですが、挙動が微妙に変わってしまったのでデバッグを試みたのですがこれに3日も溶かしてしまいました。
int64型の0x7f7f7f7f7f7f7f7fというmaskをつくるときに一番上のbitが立ってないのでof_int 0x7f7f7f7f7f7f7f7fと書いていたのですが、OCamlのintは63bit符号付き整数なので63bit目が立っている数は負の数を表しており、of_intでint64に変換すると符号拡張されて0xff7f7f7f7f7f7f7fになってしまうというカラクリでした。既存のボードを全関数の引数に加え直して内部で等しいか判定して違ったら例外を投げるようにして角がひっくり返る現象を発見したときはマスオさんばりにえぇ〜っ!?となりました。

序盤

適当な評価関数で序盤も手を決めていたのでこれではいくら終盤を強くしてもそのうち限界がくるだろうと思ったので定石を入れました。いろいろ調べてみるとlogistello,edax,WZebraあたりの定石があってこの中でもedaxのが一番強そうだったのですが、bookの構造が結構複雑だったので諦めてlogistelloのopening bookをハッシュテーブルにいれるようにしました

終盤探索再考

nega-scoutを実装しようかなとか想いつつ関数型で実装しにくい形してるなぁと思ってダラダラchess programming wikiを読み漁っているとalpha-betaの枝刈りはmove ordering(次にどのノードをdfsするかの順序付け)によって刈られる量が劇的に変わる(少し考えればそれはそう)とあったのでmove orderingに力をいれることを決意しました。とりあえず相手の有効手を減らす手から探索するように変えるとめっちゃ早くなって探索可能手数が5手くらい伸びました。その他にオーバーヘッドは増えるが2~3手の浅めの探索をしてその評価値の高い順に探索する方法や、深さkの探索の評価値の順を用いて深さk+1の探索をやる、を繰り返す反復深化(ID-DFS)があって、反復深化が早そうと思ったので実装してみました。しかしそんなに早くなくて、原因を突き止める時間も気力も残ってなかったので潔く捨ててもとのorderingに戻しました。
ここまで終盤読み切りで勝ちの時は石差が最大になるような手を選ぶようになっていましたが、一つでも勝ちルートを見つければそっちに突っ走ればいいのでそれを選択するように変えました。そうすると勝ちの場合にかなり早く探索が終わることが結構ありました。ここまでは終盤読み切りは残り18マスになってからでその前までは中盤探索、というように明確に分けていたのですが上の改善を利用するために残り19~22マスのときにも5000000ノードに限定して勝ちルート探索(超えたら例外を投げてplay内で捕捉して中盤探索に切り替え)するように変えました。akouryyやgasinさんとの対戦ではこれが結構効果があるようでした(数回に一回くらい20,21手で勝ちルートが見つかっていた印象)。
でもこの改善によって自分のAIがかなり有利な状況でも33-31で勝つようないやらしいプレーをするようになって少し悲しかったです。
本番の環境が自分の学科PCと同等かそれ以上である保証がないので、本当は制限は時間で設けるべきなのですがこれをサボったので変に切れ負けしないかどうかが心配...(一応学科PCで20秒くらいは残るようにしているけど)。
nega-scoutにするか〜と思ったけど時間がなかったので諦めました、評価関数もはじめの適当なやつのままですがそんなに弱くもなかったので妥協しました。

対戦成績

提出verとgasinさんのOCalloを100戦させると50勝40敗10分けでした。

まとめ

競プロで枝刈り探索は最悪ケースが読めないし通ったり通らなかったりするのであまり好きではなかったのですが、オセロの探索の高速化は結構楽しかったです(結局序盤はopening book拾ってきただけ、一番つらそうな評価関数のチューニングからは逃げてしまいましたが)

19er内での順位が気になるところですがひとまず忘れようと思います
(終盤24手読み切ってると言っていたkamiが何をしたのかとても気になって仕方ない...)

2020/1/9 追記

ようやくリバーシの対戦結果が後悔され、結果は93勝231敗で24位/28人中、レポートは過去最低点を記録しました。(本番環境は学科PCよりも低スペックだったようです)
弱すぎて泣きました。
19er内でいい順位とりたかっただけに残念です
ちゃんと時間はかってチューニングしましょう
20erの方の参考になれば幸いです。