オセロAIを作ってみた話（設計編）
この記事について
はじめに
タイトル通り、この記事はオセロAIを作った道程をまとめた話です。電王戦が開催されていた時期からいつか自分でも作れたらなあと思ってました。ようやくある程度の成果が見えたのでここでアウトプットしておきます。
このページは設計編です。仕組みについてを説明します。実装した際の話は別記事にしますので、良ければそちらも是非ご覧ください。私が思いつきで考えた仕組みなのでボードゲームAIについての参考となる解説にはなりませんし、ましてやAIという言葉の一般論とは何の関係もございません。ご了承ください。
モンテカルロ木探索を自分なりに変えてみたことが主な話です。数学的な導出というよりは直観的な発想を試行錯誤した内容です。一応解説もしてみますが誤りを含んでいる可能性は十分にあります。
テーマ
それと今回AIを作るにあたっていくつかのテーマがありました。
- オセロについての戦略的な知恵は実装しない
- なるべく単純かつ直観的なアルゴリズムで実装する
- 自分には勝てるくらい強く
例えば角におくと強いとか序盤は石をとりすぎないとか、オセロについての知恵はプログラムしないこととします。オセロについてプログラムに教えることはルールだけです。なのでプロの棋譜から学習させることもしません。
なるべくわかりやすいアルゴリズムを目指しました。直観的に納得感があるようなものを作りたかったのです。
上記を満たしてもまるで弱かったら面白味がありません。長年ここで上手くいっていなかったのですがとりあえずオセロ素人である自分が負ける程度には強くなったのでよしとしました。
目次
ビットボード
まずはオセロを実装しなければ始まりません。ただ実装しただけも駄目で、高速に処理できてメモリ消費が少ないことが重要です。なぜこのふたつが重要かというと、人間では一生かけても不可能かもしれない探索を数十秒で処理しないといけないからですね。
オセロを実装するのに主な問題となる処理は下ふたつでした。
- 挟まれた石をひっくり返す
- ひっくり返せるマスを判定する
普通なら8×8の2次元配列と各8方向の繰り返しと条件処理をまず思い浮かべると思いますが、重いし遅いし到底間に合わないです。
ボードゲームにはビットボードというアイデアがあります。オセロなら64マスの石の有無をビット列で表現します。黒石白石合わせて128ビットで全ての盤面を表現できます。詳しくは調べてみてください。64ビットというと現代のアーキテクチャと丁度ハマっていそうですよね。実際コード上でひとつのInteger変数として扱えるのでオセロは特に楽でした。これが理由でオセロにしたようなもんですね。
問題のふたつの処理をビット列でどう実装するのかですが、私は下記記事を参考にしました。というかほぼパクりました。
https://primenumber.hatenadiary.jp/entry/2016/12/26/063226
https://qiita.com/klattimia/items/0f9dd41da83a68aa6d0f
いやホントすごいよね…。こんなのどうやったら思いつくんだ。ありがとうございます。
余談ですが、システムを作るときにまずデータ構造から考えるって大事だなあと改めて思いました。データ構造によってアルゴリズムが決まると言ってもいいですからね。
モンテカルロ法を発展させる
モンテカルロ法
さてAIと呼ぶ部分の話です。タイトルでは便宜上AIと呼称しましたが、実体としては探索アルゴリズムです。何をAIと呼ぶかは人によるところがありますが、私は教師あり学習より探索こそAIみを感じますね。
ここの章では発展の基盤となるモンテカルロ法についての説明をします。なのでわかっているかたは次の見出しへ飛ばしてしまって結構です。
局面の推移を木構造で考えます。ノードひとつがひとつの局面にあたります。その局面から1手進んだノードが子ノードです。置ける場所が複数ある場合は同じ数だけ子ノードもあることになります。今回は根のノードを現在の局面と考え、その子ノードを手の選択肢と考えます。わかりやすいので。
オセロであり得る全てのノードを展開することは不可能です。全てのノードは5個の子ノードを持つと単純化すると、あり得る局面の数はおよそ5の60乗になります。現代のハードウェア性能ではオセロの完全解析は現実的でないです。
ので、乱数を活用したシミュレーションによって勝率を見積もります。とある局面（つまりノード）から見込みのある手（つまり子ノード）を選びたいとき、子ノードをランダムに選択しさらにその子ノードもランダムに選択するのを繰り返してゲームをシミュレーションします。いずれは終局し勝敗が決着します。
1回のシミュレーションをプレイアウトと呼びます。プレイアウトを何回も繰り返した結果、勝率が良かった子ノードが見込みのある手と考えることができます。なにせランダムなシミュレーションなので、勝率に差が出るとしたら始めの子ノードが有利あるいは不利であったはずです。
ただこのモンテカルロ法、それほどうまくいかない気がします。複数の子ノードのうち抜群に良い手がひとつあった場合、親ノードの推定値がランダムに子を選ぶせいで低い推定値になってしまうんですよね。実際のゲームでは最も良い手を選ぶのが当たり前なので最も良い子ノードの勝率がほとんど親ノードの勝率であるはずなのに、全ての子ノードを平均したような勝率を算出してしまっている感じです。
効率的に探索する
そこで、プレイアウト中に子ノードを選ぶときの「ランダム」について考えます。先に書いたランダムというのは「全ての子ノードが等しく選ばれる可能性を持つ」という意味です。実際の手順っぽく考えると、全ての子ノードそれぞれについて一様分布[0,1]から生じる乱数を引き、最も数値の高かった子ノードを選べばランダムということになります。
このランダムを、もっと賢いランダムにしたいです。これまでのプレイアウトで勝率が良ければ良いほど1に偏った乱数値を引くようにしたいです。そうすればでたらめに石を置くのでなく良いと思われる手を優先して選ぶシミュレーションができます。モンテカルロ法のランダムゆえに平均化してしまう問題を回避できます。双方良いと信じる手を選ぶのが本来のゲームであり、自然なシミュレーションと考えることもできるでしょう。
ベータ分布乱数を利用することで上記の賢いランダムが実現できそうです。ベータ分布は母数αβによって[0,1]において確率密度分布関数を持ちます。αが大きいほど1側に偏り、βが大きいほど0側に偏ります。またふたつの数が大きいほど分散が小さくなります。プレイアウトの結果勝ちであればαに、負けであればβに何らかの評価値、単純に考えれば1を足せば分布の形は都合よく偏っていきます。この分布から乱数を生成すれば望んだ乱数が得られそうです。
ただ、本当は他にもっと良い子ノードがあるのに偶然シミュレーション初期で勝ってしまった子ノードがいた場合、局所解に陥らないかという疑問も浮かびます。一応分散が良く作用するはずで、試行が少ないノードほど乱数の分散も大きく、高い乱数値を引く余地があります。よって勝率の考慮と未知の探索とをバランス良くしてくれるはずです！（思考放棄）
プレイアウトを重ねる毎に木構造データは大きくなり、各々の情報も更新されていきます。乱択によって選ばれた子ノードはさらにその子ノードを展開し、また乱択によって子ノードが選ばれ…というのを繰り返しながらプレイアウトは進んでいきます。やがて終局ノードに達し勝敗が決まったら辿ってきたノードを遡るように勝敗情報を母数に反映していきます。
母数をどう更新すればいいかは難しい問題です。1回のプレイアウトで序盤から終盤にかけてのノードが全て更新されるわけですが、序盤と終盤のノードで母数を更新する値が等しいのはどうかと思うんですよね。プレイアウトは乱択で進むので、1回1回のプレイアウトによる勝敗も偶然性を多分に含みます。探索の初期は特にですね。プレイアウトの最終的な勝敗は序盤ノードに遡っていくほど相関が少なくなっていくと考えられます。
なので、序盤ノードと終盤ノードが同じ速度で更新されないように調整します。ノードを遡る毎に更新値を割り引いていきます。これで偶然による勝敗によって乱数が偏ることも防ぎ、分散が小さくなりすぎることも防ぎます。ただどの程度割り引けば良いかがまた難しく、ここの話は実装編でまたお話したいと思います。
既知のアルゴリズムと比較する
モンテカルロ木探索
先に言うべき話でしたが、ボードゲームAIを木構造で考えるアイデアはモンテカルロ木探索と呼ばれる既知のものです。今回私が考えた探索方式もモンテカルロ木探索の特殊系といえます。モンテカルロ木探索は何らかの優先値を持って子ノードを展開する部分と一様な乱択によってプレイアウトを進める部分が分かれています。ノードは設定した試行回数を超えると子ノードが展開されます。
私が思いつきで実装したモンテカルロ法発展形は、モンテカルロ木探索で子ノードを展開する条件がなく、プレイアウト中にそのノードに至った時点で子ノードを展開する特殊系と言えます。そしてゲーム終了まで子ノードを展開するので、一様な乱択部分は存在しません。
Thompson Sampling
実装中に知ったのですが、ベータ分布乱数を利用する今回のアイデアはどうやらThompson Samplingという既知のアルゴリズムのようです。バンディット問題の優先度の算出式としてUCTが有名ですが、ThompsonSamplingもかなり有力なアルゴリズムのようですね。といっても数式をきちんと追ったわけではないので、今回のアイデアが本当にこれに該当するかはおそらくという話になります。
おわり
といった感じでオセロAIの仕組みを思いつくまま作ってみた話でした。わかりやすく説明するのは難しいですね…上手に説明できない。意味わからないところとか間違っている箇所などあればコメントくださればできる限り対応します。
実際に実装したときの話は別編で記事にしますのでご興味あれば是非。
