オセロAI世界一になりました
にゃにゃんです。
オセロAIで世界1位になりました!
この記事では半年前にゲームAIに入門した私がどういうルートを辿ってオセロAI世界1位になったのかを軽く時系列順に話します。
技術に関する話はほとんどしません。誰にでも読みやすくなるよう心がけました。
はじめに
私が作ったオセロAIはWeb上で遊べるように公開しています。
ただ、記事執筆時点では世界3位になったときのプログラムが走っています。本当はもう少し強いです。アップデートしました。
告知
12月に私が所属する筑波大学理工学群工学システム学類のアドベントカレンダーで「オセロAIの教科書」という記事集の公開を開始します。
この記事集はオセロAIを初歩からかなり強いところまで作る中でゲームAIに関する知識と経験をつけることを目的とするものです。
4月
Twitterでつながっている方が「オセロソフトRTA」という競技を考案し、挑戦していました。これはオセロAIではなく、人間同士でオセロを対戦するためのソフトを作る時間を競うものです。
これを見た私はぜひやってみたいと思い、YouTubeで生配信してこの競技を行いました。
配信していたら1.5時間程度で完成してしまい、時間が余ったのでオセロAIを作ってみることにしてみました。これが全ての始まりです。
最初の私はなんの知識もありませんでした。良さげな手をどうやって探したら良いか、とりあえず簡単なアルゴリズムで数手先の石数を最大化するプログラムを書いた気がします。
もちろん全然強くありませんでした。
5月
オセロのようなゲームは現在の盤面から複数の手が分岐し、さらにその盤面から分岐が増えていき…と、N手先読みをするとNに関して指数関数的に考えうる局面が増えてしまいます。これをなんとか効率的に探索するアルゴリズムが考案されているので、これを勉強して実装しました。
余談ですが、Twitterの知り合いでゲームAIにとても強いthunderさんという方に、ちょうど4月くらいにゲームにおける探索について軽く概要を説明していただいたことがあって、この経験がとても役に立ちました。
6月
様々な改良を施して、世界10位になりました。
ゲームAIでは盤面を評価するために、盤面を入力するとどれくらい良い/悪い局面かを判断してくれる「評価関数」という関数を使います。この評価関数を当時はほとんど手動で設計していました。
また、プログラムがとても遅かったので、制限時間内に深くまで読むことがかなり難しかったです。
7月・8月
精神状態が悪化してほとんど進捗がありませんでした。精神の健康は大事です。
9月
ゲームAIに強いTwitterの知り合いのthunderさんにおすすめの本を教えていただいたのでそれを買って読みました。
本の内容はAlphaZeroというゲームAIアルゴリズムに関するものです。AlphaZeroは囲碁で世界チャンピオンに勝ち越したAlphaGoのアルゴリズムを改良したものです。
AlphaZeroは機械学習と比較的新しい探索手法を組み合わせることで囲碁や将棋、チェスでとても強いAIが作れます。
とりあえずオセロAIにこのアルゴリズムを組み込むことで、AlphaZeroのアルゴリズムを勉強しました。
10月
この頃には6月に世界10位になった私のオセロAIは他の人に抜かされまくって世界20位まで落ちていました。
AlphaZeroのアルゴリズムを使ったオセロAIを頑張って作り、世界17位まで戻ってきました。しかし、思ったより強くはならず、悩みました。
結局、AlphaZero方式がオセロAIにおいてそこまで有効ではないという結論に至りました。ただ、ここで培った経験は11月に活きることになります。
11月
6月に使っていた探索アルゴリズムをより洗練して、さらに評価関数の作成に機械学習を取り入れることで強力なオセロAIを作りました。
6月のときよりも細かな高速化まで頑張って行い、平均して同じ時間で6月よりも2手から4手深くまで読めるようになりました。また、探索アルゴリズムについて論文を漁りまくって新たな知識も沢山つけました。
評価関数については、昔から良いとされている手法にAlphaZeroで学んだ機械学習を組み合わせて精度を上げました。
さらに、機械学習した評価関数は往々にして計算時間が多くなってしまうのですが、これをとても高速にするアイデアを思いついたので実装しました。
さらに、序盤は評価関数の精度が悪い関係で、大量の棋譜から統計を取って「良さそうな手」を事前に見つけておき、それをオセロAIに埋め込んでしまうという工夫もしました。
これらの改良で最終的に世界1位になりました。
今後
コンテストにおいて世界1位になりましたが、現在世界でトップクラスに強いとされるいくつかのコンテストに参加していないオセロAIと対戦させても負けることはなく、試した限りでは全て勝ちか引き分けとなりました。
今後、オセロAIをさらに強くするのは難しいかもしれませんが、主に評価関数の改善をさらに進めていこうと思っています。
さらに、せっかく世界トップクラスに強いオセロAIを作ったので、Web公開している機能よりも多くの機能を備えた、オセロを専門にやる人にとっても有用なオセロソフトとして公開したいとも思っています。
今後も開発を続けていきます。
この記事が気に入ったらサポートをしてみませんか?