のどあめ

ググってもなかなか出てこなかった情報を垂れ流すブログ。

AlphaZeroで最強のターン制ぷよぷよAIを作る！

最近こちらの本を読みました。
丁寧にAlphaZeroの解説が載っているので、AlphaZeroに興味ある方にはおすすめです。

www.borndigital.co.jp

この本を読んでゲームAI作りたい欲が湧いてきたので、
今回はAlphaZeroでターン制ぷよぷよ（細かいルールは後述）の最強AIの学習にチャレンジしました。

※今回はかなり本を参考に実装したためソースコード公開はしません

結果（CNN モデル VS ResNetモデル）

先に結果だけ見せるとこんな感じです。
自己対戦だけで初代ぷよぷよの定石（早めに中連鎖する）を学習することができました！

f:id:ykicisk:20200405170810g:plain
CNNモデル（左） VS ResNetモデル（右）

AlphaZeroとは

AlphaZero自体については色々な方の解説記事が沢山あるので割愛します。
例えばブレインパッドさんの記事がおすすめです。

強化学習入門 Part3 － AlphaGoZeroでも重要な技術要素！ モンテカルロ木探索の入門 － - Platinum Data Blog by BrainPad

AlphaZeroでターン制ぷよぷよのゲームAIを学習する

AlphaZeroは二人零和有限確定完全情報ゲームのためのアルゴリズムです。
今回はぷよぷよをターン制にした二人零和有限確定ゲーム（完全情報ではない）を考え、これを対象としました。

ぷよぷよを参考にしたターン制落ち物ゲームは過去いくつか考えられているようです。
今回はpuyoloftさんの連棋（rengi）というゲームを参考にルールを決めました
「連棋(Rengi)」ターン制落ち物対戦パズルゲーム

今回扱うターン制ぷよぷよのルール

実装の都合などで本家から色々改変していますが、 基本的にはフィールドが小さい初代ぷよぷよだと思って貰えればOKです。

  • 基本ルール
    • プレイヤー２人
    • ターン制で同時着手方式（※この要素で完全情報ゲームでなくなっている）
    • ぷよは4色＋お邪魔ぷよ
    • お邪魔ぷよ以外の同色ぷよが４つ以上つながると消える
    • お邪魔ぷよは隣接するぷよが消えたとき一緒に消える
    • フィールドは横6列×縦9段（※計算時間短縮のため本家より4段小さい）
    • 左から3列目、下から8段目が埋まると負け
    • N連鎖するとN+1ターンの待状態になる
  • ツモ（組ぷよ）
    • ２個１組のツモ
    • ツモがあるときはどこかに置かなければならない
    • ツモ固定
    • 未来のツモが既知 （※AlphaZeroのアルゴリズム上そうなる）
  • 点数計算・お邪魔ぷよ
    • 相殺なし（初代ぷよぷよルール）
    • 点数計算、落ちてくるお邪魔ぷよの数は本家と同じ
    • お邪魔ぷよがおちる場所は（ターン数シードの）ランダム

モデル（デュアルネットワーク）

AlphaZeroは「自己対戦→棋譜を作成→モデルを学習」を繰り返してゲームAIの学習を行います。

AlphaZeroのモデルには、現在のゲーム状態を入力・ (policy, value)の２値を出力とするデュアルネットワークを使用します。 ここでpolicyは次の手の確率（行動数次元の出力）、valueはゲーム状態の評価値（1次元）みたいなイメージです。

（詳しくはAlphaZeroを解説している記事を参照してください）

行動数

行動数はツモを落とすパターン＋パスの23通りです。
そのため、モデルのpolicy出力は23次元です。

ツモを落とすパターン 行動数
○▲ 左端〜右端までの5通り
▲○ 左端〜右端までの5通り
○
▲		 左端〜右端までの6通り
▲
○		 左端〜右端までの6通り
ツモなし 1通り ※自分・相手の連鎖待ちなどでツモがない場合はこの行動を取る

ゲーム状態のテンソル表現

モデルの入力にするためにターン制ぷよぷよのゲーム状態をテンソルで表現します。

今回はゲーム状態を（9 × 6 × 49）次元で表現します。
ここで（9 × 6）はフィールドのサイズで、49のchannelに以下の要素が含まれます。

１．フィールドの状態

  • ぷよが存在する位置は1, それ以外は0のテンソル
  • {自分, 相手} × {ぷよ 5種 ※お邪魔ぷよ含む}の10 channel

２．ツモ色を（9 × 6 × channel数）にone-hotエンコーディングっぽくしたもの

  • {自分, 相手} × {現在, Next} × {ツモ個数 2個} × {ぷよ 4種} の32 channel
  • 例えば、現在ツモが「●●」のときは、以下のような（9 × 6 × 8）次元のテンソルになる。

f:id:ykicisk:20200405153540p:plain
ツモ（組ぷよ）のテンソル表現

３．上と同様にその他の情報を（9 × 6 × channel数）にエンコーディングしたもの

  • 以下の7channel
    • 経過ターン数 1 channel
    • 次ターンに落ちるおじゃまぷよの数 {自分, 相手} の 2channel
    • 連鎖が終わったら落ちるおじゃまぷよの数 {自分, 相手} の 2channel
    • 連鎖待ち時間 {自分, 相手}の 2 channel

モデル

今回はTensorflow 2.1のtensorflow.kerasで２つのモデルを試しました。
本家AlphaZeroに比べるとかなり軽量なモデルです。

モデル名 ネットワーク詳細
CNNモデル Conv2D→Conv2D→MaxPooling2D→DropOut→Flatten→Dense
ResNetモデル Conv2D→BatchNormalization→ResidualBlock※*4→GlobalAveragePooling2D→Dense

※ResidualBlockは Conv2D→BatchNormalization→Conv2D→BatchNormalizationで１ブロックになっています。
※ResidualBlockの出力は、入力と最後のBatchNormalization出力の和になる

実装の工夫

自己対戦では現在のモデルのPredict値を使ってモンテカルロ木探索します。
そのため、普通に実装すると１手ごとにモンテカルロ木探索数だけ直列にPredictが走ってしまいます。

そこで計算時間短縮のために以下の工夫を行いました。

  • multiprocessingで自己対戦の並列化
    • 自己対戦は独立なので並列に行っても問題ありません
    • Tensorflowが絡む部分（モデルのPredictionなど）はメインプロセスで行います。
    • 自己対戦プロセスからPredictionの入力（ゲーム状態）を Queue でメインプロセスに送り、メインプロセスはPrediction結果を後述のキャッシュに格納します。
  • （ゲーム状態, モデルのPredict値）、（ゲーム状態, モンテカルロ木探索結果）のキャッシュ

正確に測っていませんが、体感で10倍以上の高速化になっていると思います。
（もうちょっと賢い方法はありそう）

実験

パラメータ・学習時間

パラメータ 備考
エポック数 100 自己対戦〜モデル学習のサイクル数
１エポック数あたりの自己対戦数 150 AlphaZero本家は25,000回。学習時間の削減のためかなり少なめ。
１エポック数あたりの時間 約60分 高速化した割には遅い気がする。。
うちモデル学習時間 約1分 学習のほとんど自己対戦している時間。GPUなんていらなかった。

結果（再掲）

左がCNNモデル、右がResNetモデルで対戦した結果です。
CNNモデルが３連鎖ダブル、ResNetモデルが４連鎖でResNetモデルの勝ちです。

ターン制だけあってちょっとアグレッシブな積み方をしていますが、 いらないぷよを端に避けたりしいて面白いですね。

f:id:ykicisk:20200405170810g:plain
CNNモデル（左） VS ResNetモデル（右）

考察

  • 自己対戦の時間
    • 自己対戦ではPredictionのキャッシュがあるので同じような展開が多いと学習時間が短くなります。
    • 学習時間はエポックが進むに連れて単調に落ちると思ったのですが、新手を見つけるとキャッシュに当たらなくなり学習が遅くなるようです。（下図）
    • 学習時間を見ることでブレイクスルー的なものが確認できるかもしれません。
    • 学習時間が増えている「エポック数40-50」、「エポック数80-100」の差を見てみました。

    f:id:ykicisk:20200405162623p:plain
    ResNetモデルにおけるエポック数（横軸）と自己対戦にかかった時間（縦軸）

エポック数40と50の差

f:id:ykicisk:20200405162708p:plain
ResNetモデルにおけるエポック数40（左）とエポック数50（右）の差

エポック数40と50では、３連鎖 vs ３連鎖（２連鎖目ダブル）という違いが出ています。
中盤で置くぷよの位置が変わったようです。

エポック数80と100の差

f:id:ykicisk:20200405162753p:plain
ResNetモデルにおけるエポック数80（左）とエポック数100（右）の差、（上）連鎖前、（下）連鎖後

エポック数80と100では、３連目での消えるぷよが１個増えています。
その結果、お邪魔ぷよが落ちたときにギリギリ１手差で勝つようになりました。

まとめと感想

  • AlphaZeroを使うことでターン制ぷよぷよのゲームAIを作ることができました
  • ツモが固定問題
    • ツモ固定のため、対戦というより中連鎖の最適解を探すモデルになっていたようです。
    • 実際相手の盤面をほとんど見ないモデルになっていそうでした。
    • ツモを固定にせず学習すれば汎用的なぷよぷよAIになるかもしれません。
  • 自己対戦時間がネック
    • AlphaZeroにおいて自己対戦をいかに早くするかが勝負です。
    • モデルの学習よりモンテカルロ木探索やゲーム自体の最適化が重要だと思います。
    • もちろんお金があればサーバを横に並べて力で殴っても良いと思います。
  • 過学習問題
    • 早々に過学習してしまう場合があり、AlphaZeroを安定して学習するのは難しそうです。
    • 例えば１〜５エポックでカエル積みを覚えてしまうと、何エポック経ってもそこから抜け出せないことがありました。
    • １エポック数あたりの自己対戦数を増やすと解決するかもしれません。
  • matplotlibでアニメーション作るのが想像以上に便利でした。