2023年3月から、CodinGameというサービス上で動作するオセロAIを開発しています。目的は、AlphaZeroのアルゴリズムをスクラッチから実装する体験をすることです。AlphaZeroは、ゲーム固有の戦略に関する知識をプログラムに実装することなく、強化学習によってコンピュータが自動的に戦略を獲得していく点が魅力的な手法です。一方で欠点として大量の計算資源を必要とする問題があります。私は以前からコンピュータ将棋ソフトの開発をしていますが、将棋でAlphaZeroを実装した場合に有効な戦略を獲得するまでに必要な計算資源が膨大である（AobaZeroプロジェクトでは分散計算によりAlphaZeroの将棋タスクにおける追実験を行っている）ため、試していませんでした。今回、オセロAIを自動的に対戦させてランキングしてくれるサービスがあることを知り、オセロであれば将棋と比べ合法手の数や終局までのターン数が少なく、手持ちのパソコンでも学習が可能なのではないかと思い実装してみることにしました。
2023年3月31日時点で、プレイヤー426名中17位になりました。
AlphaZeroのアルゴリズム自体は論文や解説記事で別途学んでいただくとして、自分で一から実装してみると何が必要になるのか、どんな順序で実装するとよいかなど、取り組んだ結果をこれからの記事で解説していこうと思っています。
トピック
トピックとしては以下のようなものがあります。すべてが記事になるかはわかりませんが、面白い点はできるだけ書き残したいと思っています。記事ができたらここからリンクを貼ります。
- 下準備
- 評価関数の学習
- AlphaZero式強化学習
- 対局エンジンの実装
- DNNの推論器の独自実装
- 全滅対策
- TVMを用いたDNNのコンパイル
- DNNの構造最適化
- CodinGame特有の話題
- 投稿の仕方
- 実行環境の詳細調査
- ソースコードを1ファイルにまとめる
- 実行バイナリを直接投稿する
- Unicodeで文字数制限の限界を攻める
CodinGameの仕様
CodinGameのオセロ部門では、以下の仕様に沿ってAIを投稿することになります。
- ソースファイルを1個だけ提出できる。言語はC++, Python, JavaScriptなど多数の選択肢あり。ソースコードの長さは10万文字まで。
- 自分の手番が来るごとに標準入力から現在の盤面と合法手リストを受け取り、標準出力に指し手を出力する。
- プログラムはCodinGameのサーバ上で実行され、自動的に他のプレイヤーとマッチングし、順位が決定される。
- 初手は思考時間2000ms、それ以降は1手150ms。
開発の方針を定めるには、並列化ができないなど、詳しい実行環境を知ることが重要になります。この記事に調査結果をまとめています。
注意点
AlphaZero（および探索に用いているMCTSアルゴリズム）はおそらくオセロAIを作る際に最適ではありません。オセロは軽量な評価関数を人手で作りやすく、合法手の数も少ないためアルファベータ法をベースとした全探索に近いアルゴリズムのほうが有力と考えられます。さらに、CodinGameではシングルコアCPUしか使用できないため、マルチコアでの並列化が難しいアルファベータ法にとって有利かつ、深層学習モデルを動作させるのに向いたGPUも使えません。 また、分散計算については扱いません。手持ちのリソースの都合上、一台のパソコンで学習を行います。
