注意
- 国語力皆無の理系なので暇な人だけ読んで下さい。
- ちなみに中の人はオセロのルールだけ分かるレベルの人です。
これ何
オセロAIをゼロから作って世界最強クラスのオセロAIに初勝利を上げるまで、の回顧録です。
事の発端
その昔将棋電王戦とか言う将棋のプロ棋士と将棋ソフトが戦うイベント?があって、それを見ていた私がそんなん俺様が作ってやるよｵﾗｧﾝと思って作り始めたものの、HTMLとJavascriptで画面だけ作ってそこから何をどうすれば良いのかとかアルファベータ探索が全然理解できなかったりとかしたので、結果が盤上の石の数を数えるだけで良いという定量的で且つ囲碁のように盤面があまり広くないという理由でオセロAIを作り始めることになりました。やり始めて色々読んでわかったんですが、オセロはまだ完全解析までは行き着いていないということを知りました。完全に舐めてました。
HTML+Javascript
とりあえず画面から作り始めてしまう性分のようで、まずは人同士で遊べそうなブラウザ上でマウスでポチポチするとなんとかルール通り遊べるぐらいのモノができました。
完全読み
次に自動で指し手を決める思考部を作るわけですが、前述の通りアルファベータ探索をあまり理解できていなかったので、N手先まですべての手について読んでその中で一番いい手を選ぶ方式を作りました。Javascriptで作ったせいもあって、遅い＋メモリ消費多ではありましたが終局まで相手をしてくれるものが出来上がりました。評価関数は至って単純で、黒1,白-1,空き0として8x8マス分の重みと掛け算をしてその積の総和を評価とするものでした。評価関数もエイヤで決めた数字を使っていたこともあって当然ながら、ルールを知っている私でも勝てるくらいのよわよわでした。また、一番良い手を選んでいるつもりが、一番悪い手を選ぶ形になっている時期もありました。
ニューラルネットワークと自己対局
学生時代にニューラルネットワーク(以下NN)とか最小限のことは習った記憶があるので隠れ層1層の簡単なNNを組んでそれを評価関数としました。そこで問題になったのは学習に使う棋譜です。対局結果を棋譜として出力する機能は作ったものの、N手全読みなので同じ局面では同じ手しか指さないし、人力でポチポチやってたら時間が掛かります。そこで、初期局面を初めのうちは人力で2手目に登場する局面のバリエーションはこれとこれとこれと…とファイルに書き出してそれを初期局面として使い、量的なところはseleniumというソフト的にブラウザ上でボタンを押したりしてくれるソフトを使って自己対局～棋譜の保存を自動化することが出来ました。その甲斐あって最終的にはgithubにpushすると自己対局～棋譜の保存を自動でやることが出来るようになりました。
それでもまだ弱々で、私でも勝ててしまう状況は変わりませんでした。
Rust
ちょっと速度的にも手詰まり感が出てきたので、新しいことの勉強を兼ねて最近流行りの?Rustで全面的に書き換えることにしました。Javascript等ブラウザ上で計算をする処理系ではSIMDや並列計算等がやりにくいという理由もありました。
何とかJavascriptを移植してN手全読みまでたどり着きましたが、全然勝つ気配がありません。どうやらsigmoid関数の実装を間違えていたようです(てへぺろ)、どおりで弱々なわけです。
それを直したことで少しづつ強くなり始めました。
色々工夫
そろそろ長文すぎて書くのに疲れてきましたが。。。
高速化のために色々やりました。
- アルファベータ枝刈り
イマイチ理解が進まなかったアルファベータ枝刈りですが、色々ネットで検索してようやく自分の中で納得がいったのでようやく実装にこぎつけました。日本語のWikipediaのページの情報が正しくないという情報(要出典)も助けになりましたｗ。てっきり全読みと同じ結果を少ない読み数で得られる方法だと思っていたら、悪くない手を探す方法だったんですね。 - SIMDとbitboard
8x8の盤面を計算するので4つずつ8つずつ1命令で計算するSIMD(SSE, AVX)は相性がよく、実際処理は高速になりました。探索速度(nps)で大体2倍速。実装の仕方によって効果が得られない時があって、それはSIMDのレジスタ本数が足りなくてレジスタの退避が発生すると極端に処理時間が遅くなるというものでした。もう少し工夫の余地があるのかもしれません。また、効率よく計算するために、1マス1バイトのbyteboard(黒1, 空0, 白-1)よりも、1マス1ビットのbitboardの方がよりsimd計算に向いていることがわかりました、黒石64bit, 白石64bitで2つの64bit変数で表現できるところも簡単で良いです。 - multi-threading
最近のCPUは1つのCPUでたくさんの処理を同時に走らせることが出来るのでこれを使わない手はありません。Rustはスレッド間の同期がしっかりしている言語だと思って使い始めたこともあります。実際にやってみると、Rustはスレッド間の同期が厳格で真面目に同期処理を行うとあまり速度的なありがたみはありませんでしたが、それ以上に沢山のスレッドで手を検討してもスレッドを生成するコストが結構かかったり枝刈りがされにくくなったりして多スレッドの恩恵の限界を感じました。それでも、1スレよりは2スレなら最大2倍速になってくれたようです。 - 棋譜生成と互角局面集
前述のように自己対局のために初期局面が必要ですが、今までは生成した棋譜から人力で拾ってくる時間のやり方をしていたのですが、そろそろ我慢の限界的なものが現れて、ソフト的に1手ずつ着手可能な手を広げていくことで初期局面集(8手目まで)を作ることが出来ました。またその頃には後述のEdax先生と対局できるようになっていたので先生のお力を借りて13手目までの互角局面集(Edax先生が-1~+1の評価をつける局面)を作ることが出来ました。 - OBF(Othello Board File)とRFEN(Reversi Forsyth Edwards Notation)
オセロの盤面の表現の仕方としてOBFというXO-の羅列で盤面を表現をする方法があるようです。チェスや将棋ではFEN, SFENといったアルファベットで駒の位置を表して、空きマスはその連続数で表現する方法があります。このFEN(SFEN)の考え方を利用したものがRFENで、黒石は大文字(A~H)、白石は小文字(a~h)、空きマスは数字(1~8)で左から右へ連続する数を数えて表現します。XO-の羅列よりはわかりやすいはずっっっ。
ex. 初期局面
OBF: "---------------------------XO------OX--------------------------- X"
RFEN: "8/8/8/3Aa3/3aA3/8/8/8 b"
ね？短いでしょ？
vs Edax
色々と記事を漁っていたときにQiitaに自作したリバーシAIでEdaxに挑む！という記事を見つけました。
CUIベースのソフトなのでこの記事を参考にEdax先生に挑むことにしました。
初めて挑んだときは最後まで指せずにあっけなく完敗しました。
そこからNNを大きくしたりしてある日何となくEdax先生に1局挑んだら勝てちゃうじゃないですか！最初はいつものように負けたのかと思ったら、こちらが黒でも白でも黒が勝ったので、とうとうEdax先生に勝ったのだと理解が出来ました。
でも、更にNNの学習をしたら勝てなくなったので、たまたま勝てる手順をちょうど学習出来てたってことのようです。。。
Edax先生と互角局面集を使って対局するモードを最近追加しましたが、先生が強すぎてレート計算が正しく出来る気がしません(先生が全勝)。
精進します。
今後の展望
予定は未定ですが一応、
- NNのサイズを大きくする
- 判別関数を変える
- UIと連携する
感想
一応それなりの強さのオセロAIを作ることが出来て良かったです、引き続き気長に頑張ります。色んなゲームの最強ソフトを作っている人たちはどういう頭の作りでどういう思考であんなツヨツヨが作れるのか。。。
当初の目標である将棋AIは点数付けのプランが思いつかないのでまだまだ先の話になりそうです。。。歩が100点とはよく聞きますが。。。
長文にお付き合いいただき、ありがとうございました。
参考(順不同)