オセロAIを作り始めた日のこと
あれは2021年4月のこと、今思い返せば偶然が重なって起きた出来事でした。
第一の偶然は、ゲームAI(ゲームを自動プレイするAI)世界4連覇の方になぜかゲームAIの初歩的な話を30分程度教わっていたことです。
第二の偶然は、Twitterの知り合いが「オセロソフトRTA」なる競技をやっているのを目にしたことです。なんじゃそりゃ、と思った私はすぐに、その競技が 「オセロで遊ぶプラットフォームをどれだけ早く作るか」を競うものだとわかりました。
面白い、やってみよう。
YouTubeでライブ配信しながら、私はオセロソフトRTAをやってみました。その時のライブはこちら。3時間で完成できれば良いと思っていたのですが、思ったよりも早く終わってしまいました。
オセロAIでも作るか。
こうして私のオセロAI制作が開始しました。
何をしたら良いかわからなかった
オセロAIを作ると言っても、事前知識は30分教わったアルゴリズムの概略だけです。これだけでは到底まともなオセロAIを実装するところまではたどり着けません。
最初に私が考えたのは、とりあえず目先の石数を最大化することでした。この戦略が強くならないことは承知していましたが、どうすれば良いかわからなかったのです。
そんなこんなしているうちにオセロソフトRTAライブ開始から3時間程度が経過し、とりあえずライブは閉めることにしました。
最初は弱小AIだった
最初はオセロ初心者の私にギリギリ勝てるかという弱さでした。
Master Reversi for HTML5という結構強いオセロAIがあるのですが、それには全滅させられていました。
ゲームAIを勉強する
まず、ゲームAIを作る上で必要になる「ゲーム木探索」についてひたすら学びました。mini-max法やalpha-beta法と呼ばれるものです。ここで、最初期に教わっていたゲーム木探索アルゴリズムの初歩が役に立ちます。教わった当時はあまり理解できていなかったことが、ここに来て理解できるようになりました。
そして、目先の石数を最大化するのではなく、相手の置けるところを少なくしようと努めるように工夫したりしました。
結構強くなる
4月30日に対戦して全滅させられた強豪オセロAIと、2週間後に再戦しました。その結果、なんと勝つことができました。
コンテストに出してみた
CodinGame Othelloという世界中からオセロAIが集まって互いに対戦しているコンテストがあったので、そこに出してみることにしました。その結果、世界15位になれました。オセロAIを作り始めて3週間ほどのことです。
8bitマイコンでオセロAIを動かしてみた
もしこのオセロAIを8bitマイコンで動かしたらどうなるだろうか
ふと思った私は早速8bitマイコン用に自作オセロAIを改変し、動かしてみました。しかし、問題がありました。当然ながら、あまりにも遅かったのです。これに対して私は8bitマイコン自体の数を増やして互いに通信させてタスクを割り振り、無理やり高速化するという解決策を取ります。
せっかく8bitマイコンというレトロなものでオセロAIを動かすので、オセロのハード部分もレトロな感じにしようと、古風なLEDを使いました。余談ですがこの方針は自分の首を締めることになります。配線が大変すぎました。3日くらいずっと配線していました。
その結果できたのが「レトロオセロAI」です。
ちなみにこのレトロオセロAIについて発表した技育展2021では最優秀賞をいただけました。
世界10位になる
本筋のオセロAIの改良も進め、6月には世界10位になっていました。
これを機に、このオセロAIをブラウザで遊べるよう公開しました。
人間の強さを思い知る
この頃の私は有頂天になっていました。そんな私はたまたまTwitterで知り合った人間オセロ世界4位経験者に対戦を申し込みました。
結果は敗北です。有頂天から一転、さらなる高みを目指そうを誓いました。
新たなアルゴリズムを使ってみる
もうやれることは全てやった。なのになぜまだ最強になれないんだ…
完全に詰まってしまった私は、試しに囲碁やチェスで素晴らしい実績を持つAlphaZeroというゲームAIのアルゴリズムを真似してみることにしました。
このアルゴリズムはこれまで私が作っていたオセロAIに使われていたmini-max法系統のアルゴリズムではなく、モンテカルロ木探索という全く別のアルゴリズムでした。
結論を言ってしまえば、このアルゴリズムで多少強くすることに成功したものの、思うような性能向上にはなりませんでした。
詳細を話せば長くなりますが、モンテカルロ木探索は一般にオセロにはあまり向いていないと言われています。それを思い知りました。
評価関数を再設計する
結局新たなアルゴリズムの性能は限定的でした。そこで、私はアルゴリズムを元に戻し、「評価関数」の設計を変更することにしました。
私が採用したアルゴリズムでは、盤面を見てその盤面がどちらにどれほど形勢が傾いているのかを判定する作業が必要です。これを行うのが評価関数です。評価関数の精度が向上すれば、探索をいじらなくても自然とオセロAIは強くなります。
これまでは様々な人為的な特徴量(石の数や着手可能数など)の重みつけ和で評価していた評価関数を、盤面の石の並びを見て総合評価する「パターン評価」に変更しました。
パターン評価の問題はパラメータ数が膨大になることにあります。特にコンテストではコードの長さに厳しい制限があり、パラメータ数の多さは死活問題です。私はこの問題に対し、深層学習を使うことで実質的なパラメータ数を削減しました。
深層学習を使う発想が浮かんだのは、この直前にAlphaZero方式を試していて、この中で深層学習を使っていたからでした。一見回り道をしていたのですが、きちんとその経験は役に立ちました。
制作開始から半年、ついに世界1位に
2021年11月、それまでの努力が実り、ついにコンテストで世界1位になれました。
評価関数の性能向上に加え、探索の高速化、定石の強化など、様々な工夫を詰め込みました。
真の世界最強に目標を定める
コンテストで世界1位になったものの、果たしてこのオセロAIは真に世界最強でしょうか。答えはもちろんNoです。
現状世界最強と名高いオセロAIにEdaxというものがあります。試しにこのオセロAIと対戦させてみました。結果はボロ負け。私のオセロAIは遅くて弱いという救いようのないものだったのです。
目標を真の世界最強に定めました。コンテストはもう気にしません。
本気の評価関数
これまでは評価関数に深層学習を使っていましたが、これを最急降下法による膨大なパラメータの調整にしました(※)。
私の経験上、深層学習は少ない学習データでかなり強い評価関数を作れるのですが、強さには限界があります。
43万局、2200万局面ものデータを使って、私は新たな評価関数を作りました。
(※)深層学習と最急降下法を同列に扱うことに違和感を覚える方もいらっしゃるでしょうが、今回の用途では深層学習したモデルを使って前計算することで高速な評価関数を制作したので、前計算部分を丸々最急降下法で直接最適化することができます。
本気の探索
コンテストではシングルスレッドでしか探索できませんでしたが、もうそんな制約は取り除いて良かったのです。さらに、コンテストで厄介だったコード長制限ももう考えなくて良いのです。
探索をマルチスレッドで効率的に行う手法を導入し、さらに、コードを長くしてでも突き詰めて高速化しました。これらの工夫でコンテストで世界1位になったAIの10倍速以上の高速化を実現しました。
真の世界最強は誰だ
2022年2月、ついに私の本気のオセロAIが完成しました。そして、世界最強と名高いEdaxと対戦させる時が来たのです。同じ先読み手数で数百回対戦を繰り返しました。
結果は私のオセロAIの大幅な勝ち越しでした。
ついに、私のオセロAIは真に世界最強となったのです。
オセロソフトをリリースした
真に世界最強となった私のオセロAIを搭載したオセロ対戦・研究用ソフトを制作し、リリースしました。
オセロAIｶﾝｾﾞﾝﾆﾘｶｲｼﾀ
この記事のタイトルで多くのITエンジニアの皆様はご察しでしょう。まだまだ私はオセロAIのことを何もわかっていないのです。
確かに世界最強と名高いEdaxには勝ちました。しかし、ここに重大な問題があります。探索スピードを比べたとき、同じ先読み手数であれば私のオセロAIが数倍遅いのです。
探索スピードについても世界最強を目指したい。私の目標は現在、ここにあります。現在の私は並列化や定数倍の高速化についてはまだまだ知識が足りません。これらを学んで今後もアップデートを継続します。
紹介したいURL
- 自作オセロソフトEgaroucid: https://www.egaroucid-app.nyanyan.dev/
- ブラウザで遊べる自作オセロAI: https://www.egaroucid.nyanyan.dev/
- オセロAIの作り方を解説する記事集「オセロAIの教科書」: https://note.com/nyanyan_cubetech/m/m54104c8d2f12
- 私のTwitter(静かな方): https://twitter.com/takuto_yamana
- 私のTwitter(うるさい方): https://twitter.com/Nyanyan_Cube
- オセロAIコンテストサイトCodinGame Othello: https://www.codingame.com/multiplayer/bot-programming/othello-1/leaderboard