DCNNを使った強化学習の特性と限界

要点

1. DCNNは局所的な特徴を大量に記憶する仕組み
2. 「人間が論理構造を把握できる問題」ならば「DCNN＋強化学習」の利用価値は低い。
3. 「局所的な特徴だけで判断できない問題」ならば「DCNN＋強化学習」の性能は低い。
4. 「多様な訓練データを作成できない」ならば「DCNN＋強化学習」の性能は低い。
5. Alpha Go Zeroの成功は色々な条件と工夫の結果であり、Alpha Zero方式は万能ではない。

はじめに

　2018年3月頃から、いくつかのゲームAIのコンペティションに参加するため、DCNN（Deep Convolutional Neural Network）を使った強化学習プログラムを作っていました。成功したものもあれば失敗したものもあり、それらの経験からDCNNを使った強化学習の特性みたいなものも見えてきたので、そのあたりをまとめます。

　プログラムの作り方については、特に解説していませんので、作り方を知りたい方は他の記事を参考にしてください。あと、専門用語を解説なしで使っていくので、ある程度知識がある人を対象にしています。

作成してきた強化学習プログラム

　今までに作成した強化学習プログラムとその結果について紹介します。

囲碁 - 継続中

　人間の棋譜を使わずに、Alpha Go Zeroよりも少ない計算機資源で強い囲碁プログラムを作ろうとしています。Alpha Go Zeroとの違いは、学習時の探索数が少ない（8局面だけ）かわりに、地（領域）の大きさを報酬に入れている点です。現在のところGnuGoよりも強いプログラムにはなっていますが、強さが頭打ちになっているので、改良が必要なようです。

Legends of Code & Magic（Codingame）- 成功

　対戦型のカードゲーム（シャドウバースが近い）のAIをAlpha Zero方式で作りました。ただし、PUCTのかわりに幅優先探索を採用しました。Policy Network（PN）とValue Network（VN）の両方を学習させようとしたのですが、PNの学習は上手くいかず、VNだけを使うことにしました。Alpha Zero方式よりDQNの方が近いかもしれません。結果は上手くいきまして、全体で49位となりました。このゲームだけは、中間層3層の小さい全結合型NNを使っており、DCNNは使っていません。

Xmas Rush（Codingame）- 失敗

　タイルを移動させて移動経路を作ってアイテムを回収していくゲーム（チクタクバンバンみたいなゲーム）のAIをAlpha Zero方式で作りました。ただし、報酬は勝率ではなく、アイテム回収数にしています。それなりに何かを学習したようですが、私が適当に作ったプログラムよりも圧倒的に弱いという状態でした（Wood1を突破できず）。

SamurAI Coding 2018-2019 - 失敗

　指定されたマップをゴールまで出来るだけ早く走るAIをAlpha Zero方式で作りました。このときは、ほぼオリジナルと同じ方式（PN + VN + PUCT）で作ってみました。学習は上手くいっていたようですが、私が作った幅優先探索のプログラムより弱いという結果になりました（予選24位）。

DCNNを使った強化学習の特性

　強化学習の特性の前に、現在までに判明しているDCNNの特性について考えます。私はDCNNの特性を考える上で最も重要な論文は「Understanding deep learning requires rethinking generalization」だと思っています。この論文は、画像データセット「CIFAR-10」を使ってDCNNの性能を評価したものであり、各画像にランダム（でたらめ）にラベルを設定したとしてもDCNNはそれらの画像とラベルの関係を「完全に記憶できる」ことを明らかにしています。また、Adversarial Examplesのような現象があることを考えると、DCNNは画像全体を見ているのではなく、局所的な特徴のみを判断基準にしていると考えられます¹。つまり、DCNNは局所的な特徴を大量に記憶する仕組みであり、全体の構成を判断したり、複雑な論理関係を把握したりする仕組みではないと思われます。

　このような特性を持つDCNNを使って強化学習を行った場合、そのプログラムの性能にもDCNNの特性が大きく影響します。まず、論理構造を「ほとんど」学習できません。例えば、ResNetなどの典型的なDCNNではグラフ構造を理解できないようで、容易に全探索できるような探索木であっても解を見つけられないことがあります²。訓練データとまったく同じ探索木であれば解けるのですが、一部に変化があると正答率が大きく低下します（解と関係ない部分だとしても）。また、局所的な特徴よりも全体的な構造の方が重要な問題の場合、DCNNを使った強化学習は性能を発揮しません。全体的には同じような形であっても、一部のパターンが変化しているために、間違った選択をすることが「よく」あります。

　これらから言えることは、Alpha Zero方式を含む「DCNN＋強化学習」が高い性能を発揮できる問題はかなり限定されるということです。具体的には「人間が論理構造を把握できないぐらいには複雑であり、局所的な特徴だけで判断できるぐらいには簡単な問題」にだけ効果を発揮する、ということになります。

DCNN＋強化学習を上手く使いこなすには

　DCNNは局所的な特徴を記憶するだけで従来手法よりも高い画像認識性能を発揮するわけですから、局所的な特徴を記憶する仕組みとしては非常に優秀な手法だともいえます。つまり、これ以外の仕組みについては他の手法を使えばよいわけです。例えば、私の「Legends of Code & Magic（カードゲーム）」のプログラムでは、カードやライフなどの「状態値」を作成（論理計算）し、これをNNに入力して勝率を計算していました。また、リーサル（そのターンの勝ち筋）については単純な幅優先探索を使っていました。このように、DCNNだけではなく、それ以外の手法とうまく繋げることが重要となります。

　また、DCNNは記憶する仕組みですので、できるだけ多様な訓練データを作成することも重要となってきます。例えば、Alpha Zero方式では、ゲーム中のすべての手をPolicy Network（PN）の訓練データとしています。もし、そのゲームに勝った側だけの手を訓練データとした場合、その時点でよいと判断している手のみを選択するPNとなり、その次のステップ以降の訓練データから多様性が失われてしまいます。Alpha Go Leeでも強化学習を使っていたのですが、対局に勝った手だけをPNの訓練データとしていたため、PNの性能が頭打ちになったと考えられます³。

　つまり、DCNN+強化学習のプログラムが高い性能を発揮するためには、いくつかの条件をクリアする必要があります。

　１つ目の条件は「人間が論理構造を把握できない問題である」です。人間が論理構造を把握できるのであれば、DCNNを使うより、探索やルールベースで実装した方が高い性能を発揮します。よい特徴量を作れるが評価値を計算する方法が分からない場合、人間が作った特徴量から評価値を計算するためにDCNNを使うとよいかもしれません。ただし、この場合も、Bayesian NetworkやRandom Forestの方がよい性能を出すことがあります。

　２つ目の条件は「局所的な特徴だけで判断できる問題である」です。例えば、全体像を把握しなくてはならない最短経路などの問題には（そのままでは）DCNNを使えません。ただし、DCNNで局所的な評価値を計算し、それを別の方法で統合して全体の評価値とする、という方法があります。後述しますが、Alpha Go ZeroのValue Network + MCTSは局所的な評価値を統合する仕組みになっているようです。

　３つ目の条件は「多様な訓練データを作成できる」です。DCNNは非常に多く（数万個以上）の状態を記憶することができますが、そのためには、記憶するための多様な訓練データを作成しなくてはなりません。一方、見たことがない状態に遭遇した場合、DCNNの精度が大幅に低下することがありますので、探索空間はあまり広くない方がよいです（問題の対象となる探索空間が狭く、その探索空間を網羅するような訓練データを作れるとよい）。

Alpha Go Zeroはどうなの？

　DCNN+強化学習といえばAlpha Go Zeroが挙げられますが、Alpha Go Zeroは上述の3つの条件をクリアしています。まず、囲碁というゲームは「人間が論理構造を把握できない問題⁴」です。また、強化学習ではMCTSを使うことで「多様な訓練データを作成」しています。一方、囲碁は「局所的な特徴だけで判断できる問題」ではありません。勝率を計算するには全体の趨勢を見なくてはなりませんし、シチョウなどの離れた場所の形勢が影響する場面も少なくありません。

　これらの問題に対し、まず、Alpha Go Zeroでは局所的な有利・不利を統合⁵することで、全体の勝率を計算しています。また、Alpha Go Zeroでは探索にMCTSを使っていますが、これは各盤面の勝率の平均を計算することが目的のように思えます。つまり、それぞれの盤面全体の形勢を判断して勝率の高い盤面を選んでいるのではなく、個々の局所的な形勢を判断し、有利な部分が多くなりそうな局面を選んでいると考えられます。

　また、Alpha Go Zeroだけではないのですが、多くの囲碁・将棋プログラムは特定の局面を好む傾向にあります⁶。このあたりの解析はプロ棋士の方に任せたいのですが、おそらくは、Alpha Go Zeroは離れた場所の形勢がお互いに影響しない盤面を選んでいるのではないかと思います。囲碁の場合、ある程度プレイヤがゲームの流れをコントロールできます。そこで、Alpha Go ZeroではDCNNが評価できる盤面（Alpha Go Zeroがよく知っている盤面）に持ち込むことで強さを発揮しているのではないかと考えています。

　ちなみに、私の作ったカードゲーム「Legends of Code & Magic」のプログラムの場合、テンポアドバンテージをとりにくタイプのAIになりました⁷。これは、複数カードを連携させるよりも、個々のカードの能力をできるだけ活かすことを重視する戦術であるため、NNを使って個々のカードの評価値を計算し、それを統合することで勝率を予測できたのだと考えられます。

まとめ

　１年ほど、DCNNと強化学習を使って色々なプログラムを作ってきました。私自身のプログラミングスキルは低く、プログラミング大会に出ても自力では勝てないので、Alpha Zero方式を使えば勝てるのではないか思ったのですが、世の中はそんなに甘くありませんでした。あと、DCNN+強化学習方式の適用可能範囲が思ったよりも狭いということも分かってきました⁸。

　DCNNを含むニューラルネットワークに関する研究は非常に盛んに行われおり、GCNやSiamese Networkなどの新しいタイプのNNも提案されています。近い将来、私の技術力でもトッププログラマと同じ性能のプログラムを自動的に作れるようになるかもしれませんが、現在のところ、「自動的に高性能のプログラムを作る」というのは難しいようです。

---

1. DCNNが局所的な情報しか見ていないことを実験的に示した論文もでてきていますが、そのあたりの話は別の機会に。 ↩

2. この問題があるのでGCNNの研究が盛んになっているのかもしれません。 ↩

3. まったく同じ実験をやったところ、同じような結果になりました。 ↩

4. 「盤面の状態からその対局の勝率を数式等のロジックで表現できない」という意味です。 ↩

5. Value Headに含まれる1x1 Convolution Layerが局所的な有利・不利（に関する特徴量）を計算している部分で、Full Connection Layerがそれらを統合している場所だと考えています。実験では、Full Connection LayerをGlobal Average Poolingにしても、DCNNの性能は大きく変化しませんでした。 ↩

6. 囲碁なら早期三々入り。将棋なら居飛車。 ↩

7. カードゲームをしている人ならご存知だと思いますが、アグロ・テンポ・ミッドレンジ・コントロールなどの戦術があり、どれが強いというわけではありません。 ↩

8. 「使えない」という意味ではなく、「他によい方法があることが多い」という意味です。 ↩