オセロAIを作り、世界top50位内まで育てた話
はじめに
会社の研修で、オセロAIを作る機会がありました。
研修内では参加者同士でAIを対戦させ、最終的に優勝することができました。
自分なりに探索方法や評価の仕方を調べながら実装していたこともあり、研修を終えた時点ではそれなりの手応えがありました。
そんな中、調査の過程で見つけたのが、CodinGameの「Othello」です。
本記事ではCodinGame上の参加者全体における順位について、分かりやすさを優先して「世界○位」と表現します。
与えられた8×8の盤面から、制限時間内に次の一手を決める。
研修とは実行環境もルールも異なりますが、取り組んでいたテーマとしてはかなり近いものでした。
そこで研修終了後、研修で得た知識や考え方を起点として、CodinGameの公開ルールに合わせたオセロAIを個人で改めて実装することにしました。
最初はPythonで最低限対戦できるところまで作り、リーグへエントリーしました。
結果は、
Wood 2、390位。
研修で優勝できていたこともあり、多少の自信はありました。
しかし、結果だけ見れば全く通用していませんでした。
そこから改善を重ね、Python版で189位。
さらにC++で設計から見直し、最終的には44位 / 629人まで順位を上げることができました。
この記事では個々のアルゴリズムを深掘りするのではなく、
一度作ったものを別の評価環境へ持っていき、現実とのギャップを確認しながら改善していった過程
について整理します。
研修で終わらせず、もう一度作ってみる
今回の取り組みは、最初から世界ランキングを狙って始めたものではありません。
そもそものきっかけは会社の研修でした。
研修ではオセロAIを実装し、それぞれが作ったAIを対戦させます。
そこで優勝できたこと自体は素直に嬉しかったのですが、それ以上に面白かったのが、
「どうすればプログラムに、より良い一手を選ばせられるのか」
を考える過程でした。
単純に現在の石数だけを見ても、必ずしも良い手は選べません。
相手が次にどれだけ打てるのか。
角を取られる可能性はないか。
数手先では盤面がどう変化しているのか。
そういったことを調べ始めると、単純なゲームに見えていたオセロの中に、探索・評価・計算量といったテーマが詰まっていることが分かりました。
その調査中にCodinGameのOthelloを知ります。
せっかくここまで調べたので、研修の中だけで終わらせるのではなく、別の環境でも試してみたい。
そこで、CodinGameのルールと入出力仕様を確認し、個人でPython版のAIを作り始めました。
最初の目標は、強いAIを作ることではありません。
まずは、
- 盤面を正しく受け取る
- 合法手を扱う
- 自分のロジックで着手を決める
- 制限時間内に正常な手を返す
という、対戦プログラムとして最低限成立する状態を作ることを優先しました。
この段階で一度リーグへ提出しました。
結果が390位でした。
「動く」と「戦える」の間にはかなり距離があった
390位という結果を見たとき、最初に感じたのは、
「思っていたより、かなり弱い」
ということでした。
ただ、振り返ると当然でもあります。
研修内で優勝できたことと、不特定多数の参加者が改善を重ねている環境で上位に入れることは、まったく別の話です。
比較対象が変われば、求められる水準も変わります。
この390位という結果は、自分にとってかなり良い基準になりました。
それまで、
「この評価方法なら強そう」
「もう少し深く読めば良さそう」
と考えていたものに、初めて客観的な順位が付きました。
ここからは「強そうなAIを作る」のではなく、
実際の結果を見ながら、何が不足しているのかを一つずつ潰していく
という進め方に変わっていきました。
まずはPythonで、考えていた改善を一通り試した
390位から、すぐに言語を変えたわけではありません。
まずはPythonのまま、自分が改善できると考えていた部分を実装していきました。
このとき意識していたのは、一度に大きく変更しすぎないことです。
基本的には、
- 現状の問題を考える
- 改善案を決める
- 実装する
- 対戦結果を見る
- 次の問題を考える
という流れを繰り返しました。
AI開発に限った話ではありませんが、複数の変更を一気に入れてしまうと、結果が良くなっても悪くなっても「何が効いたのか」が分からなくなります。
特に対戦AIの場合、一局ごとの結果にはどうしてもばらつきがあります。
そのため、改善そのものと同じくらい、改善結果をどう評価するかが重要になりました。
こうしてPython版を改良していった結果、Wood 1へ昇格し、189位まで順位を上げることができました。
390位から189位。
一定の改善はできました。
ただ、このあたりから、アルゴリズムとは別のボトルネックがはっきり見えてきます。
次に問題になったのは「時間」だった
オセロAIでは、基本的に先の局面を読むほど判断材料が増えます。
ただし、当然ながら深く探索するほど計算量も増えます。
CodinGameでは一手を返すまでの時間に制限があります。
そのため、
どれだけ賢い評価方法を考えるか
だけではなく、
制限時間の中で何局面まで探索できるか
が強さに直結します。
Python版の改善を続ける中でも、
「もう少し深く読みたいが、時間的に厳しい」
という場面が増えていきました。
また、上位の実装について調べてみると、C++を使っているものが多く見つかりました。
もちろん、言語をC++に変えれば自動的に強くなるわけではありません。
探索方法が悪ければ、速く大量に無駄な局面を調べるだけです。
一方で、探索アルゴリズムを工夫したうえで、同じ制限時間の中でもう一段深く読めるのであれば、処理速度そのものが競争力になります。
そこで、
Python版を細かく最適化し続けるより、一度C++で作り直して、探索全体を見直した方が伸びしろが大きい
と判断しました。
C++への移行を「単なる移植」にしなかった
C++版を作る際は、Python版をそのまま翻訳することはしませんでした。
せっかく作り直すのであれば、処理速度だけではなく、探索時に大量に呼ばれる処理そのものを見直した方が効果が大きいと考えたためです。
現在の実装では、盤面を64bitのビットボードで表現しています。
黒石と白石をそれぞれ64bit整数として保持し、合法手生成や石の反転処理をビット演算で扱います。
探索についても、現在は以下の手法を組み合わせています。
- Minimax探索
- Alpha-Beta枝刈り
- Principal Variation Search（PVS）
- 反復深化
- Aspiration Window
- 置換表
- 着手順序の調整
- 定石
- 終盤の完全読み
ただし、重要なのは技術要素の数ではありません。
これらを最初から全部入れて完成させたわけでもありません。
実際には、
ボトルネックを見つける → 改善する → 結果を見る
という作業の積み重ねでした。
例えば現在は、ゲームの進行状況によって処理を分けています。
序盤では定石を利用します。
中盤では評価関数を使いながらゲーム木を探索します。
終盤では空きマスが10以下になると、可能であれば終局まで読み切ります。
また、通常探索では反復深化を採用しています。
最初から深い探索を始めるのではなく、浅い深さから順番に探索し、時間切れになった場合は最後まで完了できた深さの結果を使う構成です。
CodinGameでは、どれだけ良いアルゴリズムを実装していても、時間切れで正常な手を返せなければ意味がありません。
そのため、
探索の強さと、制限時間内に必ず結果を返すことの両立
はかなり意識しました。
このあたりから、単に「オセロで強い手を考える」というより、
限られた計算資源をどう配分するか
という問題になっていった感覚があります。
AIだけではなく「改善を測る仕組み」も必要になった
開発を続けていると、もう一つ問題が出てきました。
変更したAIが、本当に強くなっているのか分かりにくいことです。
例えば、新しい評価項目を追加したAIが一局勝ったとしても、それだけで改善したとは判断できません。
対戦する色や局面によって結果は変わります。
そこで、新旧AIをローカルで直接対戦させる環境も作りました。
黒と白を交代しながら複数回対戦させ、
- 勝数
- 総石数
- 定石を利用できた手数
- 通常探索で到達した最大depth
- 完全読みを完了できたか
などを確認できるようにしました。
これによって、
「この変更は強くなった気がする」
ではなく、
「変更前と比較して、実際にどう変わったのか」
を見ながら改善できるようになりました。
個人的には、ここは今回の開発でかなり大きかった部分です。
アルゴリズムそのものに目が向きがちですが、改善を続けるのであれば、評価するための仕組みも開発対象になると感じました。
実務でも、計測できないものは改善しにくいです。
対戦AIでも同じでした。
そして44位まで到達した
こうした改善を続けた結果、最高順位は
44位 / 629人（上位約7%）
まで上がりました。
最初のPython版が390位だったので、順位だけを見てもかなり変わりました。
390位。
Pythonで改善して189位。
そこからC++で作り直し、盤面表現や探索方法、時間管理を見直して44位。
最初から44位を取るための完成形が見えていたわけではありません。
その時点で見えている問題を一つ解決すると、次の問題が見える。
その繰り返しでした。
現在の実装や設計資料、ローカル対戦環境についてはGitHubで公開しています。
具体的な探索アルゴリズムやビットボード、評価関数については、それぞれ一つの記事にできる程度の内容になっています。
今回は開発の流れを中心にしたかったため、技術詳細についてはここでは深掘りしません。
気が向いたら、そのあたりも別の記事としてまとめようと思います。
世界50位以内を、一度区切りにする
オセロAIは、まだ改善できます。
評価関数にも改善できる部分があります。
探索効率も、定石も、終盤処理も、調べればまだ試したいものがあります。
ただ、ランキング形式のものは上を見始めると終わりがありません。
今回は一つの目標として考えていた世界50位以内に入り、44位まで到達できました。
そのため、ここをひとまず一区切りにしようと思います。
開発をやめるというより、
「順位を上げなければ」
と追い続けるフェーズから、
「面白そうな改善があれば試してみる」
くらいのペースへ変えるつもりです。
ここからはゆっくり、もう少し上を目指してみます。
自分の武器をどこで見つけるかは分からない
今回の取り組みを振り返って、一番印象に残っているのは44位という順位ではありません。
会社の研修で偶然触れたテーマが、ここまで続く個人開発になったことです。
研修で優勝した時点で、
「良い結果だった」
で終えることもできました。
しかし、調査中にCodinGameを見つけました。
面白そうだったので、個人で作り直して挑戦してみました。
すると390位でした。
通用しない理由を考えてPython版を改善しました。
189位まで上がると、今度は処理速度が気になりました。
C++で作り直すと、盤面表現や探索効率が気になりました。
改善を重ねると、今度はその変更が本当に有効なのか測りたくなり、ローカル対戦環境まで作りました。
最初から、
「ビットボードを使って、PVSを入れて、置換表を作って、対戦環境まで用意しよう」
と計画していたわけではありません。
一つ問題を解決した結果、次に解くべき問題が見えただけです。
ただ、振り返ると、こういう積み重ねが一番自分の力になっているように感じます。
エンジニアとして、自分の武器になる技術やテーマにどこで出会うのかは分かりません。
今回はたまたま仕事の研修でした。
別の人にとっては、業務で少し困ったことかもしれません。
趣味で作った小さなツールかもしれません。
何となく触ったライブラリかもしれません。
大切なのは、見つけた時点で完成としないことなのだと思います。
外の環境で試してみる。
うまくいかなければ理由を調べる。
仮説を立てる。
実装する。
結果を測る。
そして、また次を考える。
今回の開発を通して、一つのテーマを自分なりに昇華していく面白さと、その大変さを知ることができました。
研修や仕事、普段の学習の中で、
「これ、少し面白いかもしれない」
と思えるものがあれば、そこで終わらせず、もう一段だけ掘ってみるのも面白いと思います。
思ってもいなかったところから、自分の武器になるものが見つかるかもしれません。
自分も、今回見つけたものをもう少し育ててみようと思います。
この記事は個人の経験や調査内容をまとめたものであり、内容の正確性を保証するものではありません。