Connect Fourをちゃんと強化学習できた話

アルファ碁ゼロの手法で、Connect FourというゲームのAIを強化学習で作成させてみました。

Connect Fourは、「重力付き四目並べ」のようなゲームです。(四目並べ - Wikipedia
そこまで探索空間が大きすぎず、またソルバーもあるため、強化学習が正しくできるかのテスト用としては妥当なゲームでしょう。なお、正しく打てば先手必勝です。

参考文献の「AlphaGo Zeroの手法でリバーシ強化学習をやってみる」のコードをforkしたものを元に作成しました。 Connect Four用に直し、自分の好みで構造を整理しています。

コードは以下にアップロードしました。細かい工夫がたくさんあり複雑な割には分かりやすくなったはず・・

github.com

学習結果

  • 環境:
  • 学習時間:
    • 18時間程度、170000ゲームの自己対戦
  • 強さ:
    • 先手番はほぼ10割の勝率
    • 後手番は完璧なソルバーには当然勝てないが、10%ランダムに打つソルバーには5割、30%ランダムに打つソルバーには9割勝てていて、ほぼ悪手は適切に咎められる感じ
       (以下、先手番を黒番、後手番を白番ということにします)
    • 100000ゲームくらいから十分な強さになってくるか。170000ゲームでもまだ収束しきってはいなく、もう少しだけ強くなりそうです。

参考文献

AlphaGo Zeroの手法でリバーシ強化学習をやってみる

https://qiita.com/mokemokechicken/items/a5803b4280751848e36b
https://github.com/mokemokechicken/reversi-alpha-zero
アルファ碁ゼロの手法の細かい工夫がしっかりと実装されていて、今回大変参考にしました。

最強囲碁AI アルファ碁 解体新書 増補改訂版

https://www.amazon.co.jp/dp/B07F11T4CS
手法が分かりやすく説明されている書籍です。

Lessons From Alpha Zero

https://medium.com/oracledevs/lessons-from-alpha-zero-part-6-hyperparameter-tuning-b1cfcbe4ca9a
丁寧に書かれており、単なるアルファ碁ゼロの手法だけでなく、学習を高速化するためのさまざまな工夫が書かれています。コードが無いのだけが残念。

SOLVING CONNECT 4: HOW TO BUILD A PERFECT AI

強化学習でなく、探索ベースのConnect4のソルバーの作り方が説明されています。
http://blog.gamesolver.org/

また、Webアプリとしても公開されていて、作成したAIの強さを確認するのに便利です。 https://connect4.gamesolver.org/en

Kaggle Connect X

https://www.kaggle.com/c/connectx
Kaggleで以前行われたメダルなしのコンペです。モデルのアップロードはできないはずなので微妙かも。

なお、Connect4をアルファ碁ゼロの手法で十分に学習できたというコードやモデルは見つけられませんでした。

さまざまなポイント

今回やってみて気づいたさまざまなポイントについて記述していきます。

アルファ碁ゼロの手法

今回は、AlphaGo Zeroの手法に加えて、AlphaZeroの手法のようにモデル同士を戦わせることを省略するようにしました。
ざっくりとまとめると、以下のようになります。

  • 自己対戦による棋譜データをもとにモデルの学習を行う。次の手を指す確率(ポリシー)と盤面の評価(バリュー)を同時に学習するデュアルネットワークを用いる
  • 自己対戦の着手はモンテカルロ木探索により決定する。
    • 探索の中で未評価のノードに到着した場合、モデルによる推論を行う。推論によりポリシーとバリューが求まり、バリューをその探索の勝敗とする。
    • 探索の中で評価済のノードに到着した場合、今までの探索の勝敗とポリシーから次の手を決定する
    • 探索を複数回繰り返し、最も選択された手を着手する。
  • 特にモデル同士を対戦させることはせず、棋譜がたまるとモデルの学習を行い、自己対戦用のモデルを更新する

アルファ碁関連の手法はAlphaGo, AlphaGo Zero, AlphaZeroとあり、混乱しやすい名前となっています。
(AlphaGoとAlphaGo Zeroの違いは「最強囲碁AI アルファ碁 解体新書 増補改訂版」が分かりやすいです)

自己対戦ワーカーと学習ワーカー

アルファ碁ゼロの手法の構成として、自己対戦ワーカーと学習ワーカーを作成し、それぞれのプロセスを常に動かしておくのが良さそうです。

  • 自己対戦ワーカーは、自己対戦し学習データを生成しつづける。定期的に学習ワーカーによって作成されたモデルを読み込み、アップデートする
  • 学習ワーカーは、生成された学習データをウォッチし、十分に溜まっていればモデルの学習を行う

AlphaGo Zeroメソッドではモデル同士を対戦させて上回っているときのみ更新するため評価ワーカーが必要ですが、AlphaZeroメソッドでは不要になります。
今回は、学習の進行状況を把握するために、プレイヤーとソルバーを戦わせる評価ワーカーを動かしています。

着手の選択か、モンテカルロ木探索での選択かの区別

「次の手の着手を何によって決めるか」と「モンテカルロ木探索の中で次の手を何によって決めるか」を区別する必要があります。

  • 着手選択は、モンテカルロ木探索で探索した回数が最も多い手を指す
  • モンテカルロ木探索での選択は、探索での勝率であるQ値と、次の手を指す確率(ポリシー)などで求められるU値を加重平均した値が最も大きい手を指す

実際にはここに、

  • 着手選択は、序盤はモンテカルロ木探索の(最も回数の多い手でなく)回数に比例した確率で指す
  • モンテカルロ木探索での選択にはディリクレ分布によるノイズを与える

などのオプションが入ってくるため、混乱しないように理解しておくことが必要ですね。

どっちの手番問題

二人ゲームの探索を書くと、普通は相手番をひっくり返しているうちに混乱してしまい、相手評価が最も低い手を打つべきところで最も高い手を打つような類のバグが発生しがちです。

今回は、このような処理になっています。

  • 着手選択では、黒番に変換する (白番であれば、盤面をひっくり返して自分が黒番だと思い込む)。
  • モンテカルロ木探索では、黒番も白番もあるが、評価値は常に黒番からの評価を返すようにする(白番であれば、評価を反転させる)
  • ニューラルネットの推論・学習を行うデータは、次の手番ベースに変換する。
    • つまり、(次の手番のnp.array,  次の手番でない方のnp.array)の組を入力とし、
      次の手番が指す確率(ポリシー)と次の手番側の評価(バリュー)を返す

並列および非同期処理による効率化

アルファ碁ゼロの手法では、新しい盤面がモンテカルロ木探索で出てくるたびにニューラルネットの推論を行います。 ここで、これを並列や非同期処理を何も考えずに行ってしまうと、バッチサイズ1の推論を延々とGPUで行うことになり、かなり非効率になってしまいます。

そのため、以下のような流れで並列および非同期で自己対戦を行うと良いでしょう。

  • 並列で、自己対戦ワーカーを動かす。つまり、複数のゲームを同時に行う
  • 自己対戦ワーカーで、Pythonのasyncioなどの非同期処理の枠組みを使う。
    つまり、各ゲームでのモンテカルロ木探索は非同期に行い、推論のデータを投げて待っている間には他のノードの探索を進める
  • 推論データが一定以上溜まったらニューラルネットでの推論を行い、結果を返す。

このようにするとGPUが効率的に扱えるため、結構CPUがボトルネックになる印象があります。特にPythonで雑な盤面の更新を行うと速度に影響が出てきます。

メモリリーク

細かい計算を大量に行うためか、ずっと流しっぱなしにしているとメモリが枯渇して落ちてしまうことがあります。

  • keras.backend.clear_sessionを行う
  • 定期的にプロセスを再起動する
  • ニューラルネットライブラリのバージョンを適切にする

などの対処法がありますが、現状完全には解決できていなく4-5時間連続で流すと再起動が必要になるようです。 つらいので、いずれ再調査したいです。

評価の難しさ

Connect Fourはソルバーが存在し、AIが指した手が合っているか間違っているかを把握できるのが素晴らしい点です。

当初、昨年末に学習を試みた際には、「SOLVING CONNECT 4: HOW TO BUILD A PERFECT AI 」のテストケースを使って、

を出力させていました。

正答率は8-9割までは行くのですが、それ以上には上がらず、十分に学習できていない、と思い込んでいました。

しかし、改めてソルバーと対戦させてみたところ、勝ちの状況からは負けず、負けの状況から相手が悪手を指したときには勝ちになる手を正しく指せていました。 おそらく、上記テストケースには適切に打った場合には到達しない盤面も含まれているため、強いゲームAIが必ずしもそれらの盤面を正しく評価できる必要はないということなのでしょう。 さらに、ゲームAIとしては、モンテカルロ木探索を行うため多少のニューラルネットの評価の誤りは修正してくれます。

対戦相手となるAIと対戦させるのが適切な評価といえそうで、今回は一定の確率でランダムに指し、それ以外では最適な手を指すソルバーと対戦させて勝率を測ることにしました。

ソルバーによる手数制限

試行錯誤する過程で、一定手数が経過したときにソルバーで勝敗判定して打ち切る機能を追加しました。 例えば、勝敗判定の手数を7手にすると当然ながら自己対戦や学習は高速に進み、1時間くらいで収束します(それでも100000ゲームくらい必要なようですが)

パラメータや手法が有効かどうかを確認するためには、このようにゲームをフルでやらずに一定手数に制限した環境で試すと効率的でしょう。