時系列モデルが木構造を学習できることの検証

 前回の考察では、時系列モデルが暗黙のうちに木構造を学習できるので木の遷移履歴を時系列展開しても良いという仮説を立てた。この仮説を多少なりとも検証するため、今回は木に関する簡単なタスクを考えて、それが学習可能かどうかを実験により確かめた。

実験

 タスク概要:「木についての深さ優先探索での訪問順が与えられるので、幅優先探索での訪問順を出力せよ」

具体的なデータ生成手順

  1.  N頂点の木をランダムに生成する
  2. 生成した木についてランダムに根を決定
  3. 根から深さ優先探索を行い、訪問順を記録(これを時系列モデルへの入力とする)
  4. 根から幅優先探索を行い、訪問順を記録(これを正答とする)

f:id:tokumini:20200708111225p:plain

細かい点

  • DFSでは戻る際の訪問も記録しているので、系列から完全に木を復元可能(だと思う)
  • BFSにおける同じ深さでの優先度はDFSで先に探索された順と同じとする
  • ノードを入力する際はOnehotベクトルの形式にして入力
  •  N頂点の木から得られるDFSの系列(入力)は 2N - 1

実装

実験結果

頂点数 N = 6

f:id:tokumini:20200708111650p:plain

 単純なLSTMおよび以前実装したDNCのいずれにおいても50000データほど学習させると正答率(BFS順を完全一致で出力できた割合)が100%になった。 N = 6という小さい木ではあるが、訪問順を詳細に記録しておけば木構造を認識することはできていそうである。

頂点数 N = 20, 50

 LSTMについて N = 20, 50として実験を行った。

f:id:tokumini:20200710135415p:plain

 20ノード, 50ノードのものはバッチ学習として1ステップ32データにしているので、データ数としては5 * 32 = 160万データとなる。それだけ学習させると20ノードのとき正答率93.7%、50ノードのとき正答率8.0%となった。

頂点数 N = 50 その2

 50頂点くらいはなんとか学習してほしかったので、GPUを使うようにプログラムを変更してバッチサイズを256、学習ステップ数を20万(計データ数は5億程度)にして再度実験を行った。

f:id:tokumini:20200711101243p:plain

 最初は隠れ層の次元数512(青線)でやったところ正答率60%程度で頭打ちになり最後は突然nanになって崩壊してしまった。1024(赤線)でやり直したが、学習は遅いうえ損失も(nanではないが)爆発して正答率が崩壊するのは同様だった。LSTMで記憶容量を超えるとこういう感じで崩壊してしまうものなのだろうか。

雑記

 特に工夫していない1層のLSTMではそこまで長い系列(大きい木)は扱えないかもしれない。DNCをバッチ学習に対応させて可能性があるかどうか、あるいは違う系列モデルを実装するか。 N = 50だと入力系列の長さは 99であり、自然言語処理で考えて99単語からなる文となると長めではあるか。

 一方で30頂点くらいでもちゃんと探索できれば探索なしよりは強くなるんじゃないかという気もする。この記事でやっている実験は実際のゲーム木探索での状況とはやや異なるので、これの性能を追い求めていてもなぁとも思うところ。MCTSnetも実装するべきことを考えると結構実装が重たいので早めに実際の利用環境で試してみたいという気持ちはある。どちらの方針を取るにしてもとにかく実装を進めねば。

MCTSnetの損失計算部

 MCTSnetの解説は他にもある

ので、そちらも参照されたし。この記事では損失計算部分にだけ注目して記述する。

 arXiv版OpenReview版は式番号が異なるので注意。OpenReview(ICLR2018)で一回Rejectになって、ICML2018に通っていて、arXivの最新版はそのICMLにある版のと近そうなので、とりあえずこの記事では基本的にarXiv版に準拠する。

3.5 MCTSnetの訓練

 MCTSnetの読み出しネットワークは、最終的に探索全体を考慮した行動決定および評価を出力する。 この最終出力は、基本的に値ベースの学習や方策勾配法などの損失関数に従って(つまり強化学習によって)訓練できるが、簡単のため以下では各状態で教師行動が決まっているもとで教師あり学習でMCTSnetを学習することを考える。

 記号の定義

  •  z _m :  m回目のシミュレーションで確率的にサンプリングされた行動系列
  •  z_{\le m} :  m回目までのシミュレーションで確率的にサンプリングされた行動系列の系列
  •  \boldsymbol{\mathrm{z}} : 確率変数としての z_{\le m}
  •  M : 総シミュレーション回数

 基本的には M回シミュレーションを行った後の最終的な出力方策 p _\theta(a|s,  \boldsymbol{\mathrm{z}})について、教師行動 a ^ *について交差エントロピーを計算する。


\displaystyle
l(s, a ^ * ) = \mathbb{E} _ {\boldsymbol{\mathrm{z}} \sim \pi(\boldsymbol{\mathrm{z}}|s)} [ -\log p _\theta(a ^ *|s,  \boldsymbol{\mathrm{z}}) ] \tag{8}

 上式は周辺分布についての対数尤度の下限としても解釈できる(※ここはよくわからない)。

 そして現実的に \boldsymbol{\mathrm{z}}全てについて計算できるわけはないので、一つのサンプルについて勾配の推定を行う。(Schulman et al., 2015が引用されているのでちらっと見てみたがよくわからなかった)


\displaystyle
\nabla _ \theta l(s, a ^ * ) = -\mathbb{E} _ {z} [\nabla _ \theta \log p _\theta(a ^ *|s,  \boldsymbol{\mathrm{z}}) 
+ (\nabla \log \pi(\boldsymbol{\mathrm{z}}|s; \theta _ s)) \log p _\theta(a ^ *|s,  \boldsymbol{\mathrm{z}}) ]
\tag{9}

 (この式中の \boldsymbol{\mathrm{z}} zの間違いである気もするが、とりあえず論文通りの記述にしておく)

 最初の項は単純に上の損失をそのまま微分したもの。

 2番目の項はシミュレーション分布に関する勾配に対応し、REINFORCEアルゴリズムあるいはActor-Criticのようなやり方によって学習する。この項において \log p _\theta(a ^ *|s,  \boldsymbol{\mathrm{z}})が報酬信号の役割を果たす。これが大きくなるようなシミュレーション系列は良いシミュレーション系列だったと見なすことができるため。

 (式としては記述がないが?)シミュレーション方策 \pi(a|s; \theta _ s)に負のエントロピー正則化項を追加する。

3.6 信頼割り当ての工夫

 REINFORCE勾配は不偏だが分散が大きい。最終的な行動 a ^ *を決定するまでに M回のシミュレーションが寄与していて、各シミュレーション中でもどのノードを選択していくかという問題があるため計 O(M \log M)から O(M ^ 2)ほどの行動決定があり、信頼の割り当てが難しい。これに対処するため一つの逐次的決定問題のサンプルからBias-Varianceのトレードオフを調整できる手法を提案する。

  M回のシミュレーションを行うとして、 m = 1, \dots, Mのいつでも最終的な行動決定分布 p _\theta(a|s, z_{\le m})を考え、損失 lを計算することはできる。 m回時点での損失を l _ m = l(p _ \theta(a|s, z _ {\le m}))と定義する。

 最終目標は -l _ Mの最大化である。 l _ 0 = 0としたとき、この最終的な損失は次のように変形できる。


\displaystyle
-l _ M = -(l _ M - l _ 0) = \sum _ {m = 1} ^ {M} -(l _ m - l _ {m - 1})

  \bar{r} _ m = -(l _ m - l _ {m - 1})と置くと、これは m回目のシミュレーションで損失が減少した量であると見なせる。ここで、 m回目以降のこの量の累積和を R _ m = \sum _ {m' \ge m} \bar{r} _ {m'}と置くと、最終的に求めたい量は - l _ M = R _ 1である。

 式(9)のREINFORCE項について -(\nabla \log \pi(\boldsymbol{\mathrm{z}}|s; \theta _ s)) \log p _\theta(a ^ *|s,  \boldsymbol{\mathrm{z}}) = Aと置くと、


\displaystyle
A = \sum _ m (\nabla \log \pi(z _ {m}|s; \theta _ s)) R _ 1
\tag{10}

 (次の式以降そうなるのだが、ここも多分 \pi(z _ {m}|s; \theta _ s)ではなく \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)だと思われる。まぁ自明なものとして省略しているのか)

 ここで z _ mにおける確率変数は m以降の部分にしか影響を及ぼさないことから R _ 1の部分は R _ mに置き換えることができ、


\displaystyle
A = \sum _ m (\nabla \log \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)) R _ m \\
 = -\sum _ m (\nabla \log \pi(z _ {m}|s, z _ {\lt m}; \theta _ s)) (l _ M - l _ {m - 1}) \tag{11, 12}

とすることができる。つまり、 m回目のシミュレーション終了時点では、最終損失をそのまま強化信号として使うのではなく、最終損失と m回目時点での差分を使用する。これによってバイアスは生じないまま分散は小さくなる。

 さらに割引率 \gammaを導入してバイアスと分散のトレードオフを行う。 m回目のシミュレーションは m回目に続く近いところで多く貢献していると考え、遠い未来についての貢献は多少考慮する量を減らすという意味合いがある。 R ^ \gamma _ m = \sum _ {m' \ge m} \gamma ^ {m' - m} r _ {m'}と置いて、MCTSnetの最終的な勾配計算は


\displaystyle
\nabla _ \theta l(s, a ^ * ) = -\mathbb{E} _ {z} [\nabla _ \theta \log p _\theta(a ^ *|s,  z) 
+ \sum _ m \nabla \log \pi(z _ m | s; \theta _ s) R ^ \gamma _ m ] \tag{13}

木探索についての考察2

 以下の続き。

 木探索がそもそもどういうものであるかと考えると、状態をノード、行動をエッジとして構築されるグラフ上を遷移しつつ、ノード上の価値を更新していく作業だと思われる。モンテカルロ木探索の選択ステップに「一個親のノードへ戻る」という選択肢を加えれば、理論上は木の自由な遷移ができるので、たとえば以下のようなことができる。

 ステップ1

 ステップ2

 ステップ3

 ステップ4

 結局各ステップで解きたい問題は「木の遷移履歴が与えられるので、現ノードを適切に評価し次に遷移するエッジを決定する問題」としてまとめられそうだ。ここで、木の遷移履歴は状態を訪問順に並べた単なる時系列入力として扱える。(無茶かなぁ……)。状態の分散表現取得や、状態価値の評価にはAlphaZero的なモデルの分岐直前までの部分などを使うとして、次のようなやり方を今のところ想定している。

f:id:tokumini:20200704173449p:plain

 木のような句構造を持つことが多い自然言語文の処理ができることから、LSTMなどには時系列入力から木構造的なものを読み取る力があることが示唆される。

 なので多少はこういう無茶なことをやっても効果があるのではないかという気はする。少なくとも探索なしよりは強くなるんじゃないかと願望込みで。いや、実際のところはあまり上手くいく気はしないが……。とりあえず致命的な勘違いがなければこの方針で実装をしてみる予定。

 あれ、しかしこれどうやって学習させるんだ? 学習方法の問題を完全に見落としていた。各ステップで取るべき正解はわからないのでラベルは作れなくて、方策勾配法すら適用できない気はする。MCTSnetと同じトリックを使えばなんとかなる? ちゃんとMCTSnetの論文を読み返してみないとな……。

 というところまで。

Differentiable Neural Computersの実装

で書いた通り、ワーキングメモリモジュールを持つ探索マネージャについて考えている。

 ワーキングメモリモジュールとしては

あたりが可能性ありそうなのかなと思うところ。調べているとLSTMに木構造的なものを導入する研究もある1,2

 とりあえず今回はDifferentiable Neural Computer(DNC)を実装してみて、単純なタスクで上手くいくのかどうかを確かめてみた。

実装

 DNCの実装では、コントローラ部分にもLSTMを使うようではあったが、LSTMを使ってしまうと以降の部分が間違っていてもそこで学習できてしまう可能性を危惧してとりあえず普通の全結合層とした。

実験

 やったタスク : 10種類の記号(1~10)の系列をOnehotベクトルとして入力し、それらとは別の「入力終了」を示す記号(-1)が入ってきたタイミングから、それまでの入力と全く同じ記号系列を出力する。-1以降の入力は0(Onehotベクトルとしてもどの要素も経っていない0)。

入力: 3,4,1,2,-1,0,0,0
正答: X,X,X,X,3,4,1,2(Xは何でも良い)

 系列長は4から7まで一様ランダムに生成。記号も1~10でランダムに生成。長さが揃ってないというのもあってバッチ学習とかはせず1系列ごとに学習。

実験結果

f:id:tokumini:20200701115259p:plain

 DNCの方もなんだか学習出来ている気配はあるが、非常に不安定でなにか実装ミスがあるのではないかと疑いたくなるところ。

 いろいろ考えているうちに実はメモリモジュールにこだわる必要がなく、ただの時系列モデルを使えれば良いのではないかと思えてきたところもあるので、とりあえずLSTMで上手くいくかを試してみることを優先するのが次の工程か。

学習スレッドのスリープ時間と学習速度の関係

 現状では少ない計算資源の下でできるだけAlphaZeroの設定に近づけるために、学習スレッドは1ステップごとに定数時間のスリープ時間を入れて、学習量に対して生成量が十分になるように調整している。スリープ時間をどの程度にすれば良いのかを決めるため、今回は3つの設定で学習を行った。

  • 256gen_0.5M : 1ステップあたり256局面を生成するのにかかる時間だけスリープし、計0.5Mステップ学習する
  • 128gen_1M : 1ステップあたり128局面を生成するのにかかる時間だけスリープし、計1Mステップ学習する
  • 64gen_2M : 1ステップあたり64局面を生成するのにかかる時間だけスリープし、計2Mステップ学習する

 スリープ時間が短いものではその分学習ステップ数を多くするようにして、どれも最終的な学習時間(生成量)はほぼ変わらないように設定した。

実験結果

 対局まで行う余裕はなかったので検証損失のみで判断した。概ね棋力と損失値には相関がありそうなのでそこまで間違った判断ではないと思われる。

 横軸に実学習時間、縦軸に損失値を取ってプロットすると次のようになった。

f:id:tokumini:20200629133341p:plainf:id:tokumini:20200629133344p:plain
左:Policy損失 右:Value損失

 だいたいどれも変わらない。つまり結局生成する量が同じくらいであるならば、それを細かく刻んで2Mステップ学習しようがゆっくり刻んで0.5Mステップ学習しようがあまり変わらないということになる。

 横軸に学習ステップを取ってプロットすると次のようになった。

f:id:tokumini:20200629133357p:plainf:id:tokumini:20200629133400p:plain
左:Policy損失 右:Value損失

 同じデータなので結論自体は変わらない。生成量自体が本質的に重要なところであり、学習間隔はわりとどうでも良いということになる。同じ性能であるならば学習ステップ数は少ない方が学習にかかる時間がほんの少しだけ削減できるので良いと思われる。

 これも含め学習率減衰とかもいろいろ試していたが、わりと空振りという感じで残念。やはりそういう非本質的な改善では一歩先には届かなそう。

AtCoder Beginner Contest 171

結果

順位   3812th / 10526
パフォーマンス   856
レーティング  1784 → 1718(-66)

 気が狂うほど何もわからない回だった。二夜連続の3桁パフォーマンスは精神に来る。先週が+49, +45で喜んでいたら今週-63,-66でひどい取り立てだ。借金取りだってもう少し良心的だぞ。

A - αlphabet

 本当はislowerとか使いたいんだけど調べる手間が惜しくて普通に判定してしまった。良くない。

 提出

B - Mix Juice

 ソートして前から K個だけaccumulate。提出した後 K \gt Nのケースがあるんじゃないかと思って一瞬ヒヤッとした(制約でそうならないことは保証されていた)。

 提出

C - One Quadrillion and One Dalmatians

 WA出しまくり、30分くらい考えて解けなかったので飛ばした。単純な26進法ではないということに気づくのにまず時間がかかったし、気づいた後も上手く処理する方法がわからなくて無理だった。文字数を見る発想は一切なかったので上手くループで処理するしか道はなかったわけだけど、ループごとに-1していけば良いとか異常発想でしょう。いやそう思えてしまうのは本質が見えていないからなのだろうけど……。

 解説ACした後もなんだか腑に落ちない感覚が強い。0に相当する記号を持たないからこんなに変なことになっているという理解でたぶん合っていると思う。普通だと01 = 1なのだけどaが0じゃないからabがbではなくて、その分のズレがどんどん生まれていくというような。難しい。難しいっす。

 提出

D - Replacing

 std::mapで数を管理しながら見ていくだけ。簡単で良かった。ここに激ムズ問題が置かれて解けなかったりしたら心臓発作で死んでいたかもしれないな。

 AtCoderの提出で見るとaddsubがハイライトされるのはなんなんだろう。予約語ではないと思うが……。

 提出

E - Red Scarf

 サンプル1をビットで見ると、各桁で1が偶数だとそのままで奇数だと反転しているということがわかるのでそう書くと通る。これも無証明なのでダメだなぁ。自分がやっていることがXORそのものだということがさっぱりわかっていない。解説PDFのような考えをしているわけではないので。ひどい。

 提出

F - Strivore

 C問題は考える気が起きなかったので戻らず、以降はずっとF問題を解いていた。が、まぁ解けなかったというわけで。何を食えばこの発想に至るのか、解説ACをした後でもわからん。 

 提出

最近木探索について考えていること

 最近、「探索の仕方自体を学習する」手法について興味が出ている。AlphaZeroの手法をニューラルネットワーク + モンテカルロ木探索として分けて見た場合、前者は学習されるが後者は固定的なアルゴリズムとなっているため、ここを学習にすることができればより性能が高まる可能性があるのではないかと感じたためだ。特に静止探索的な概念を踏まえて、「ある局面で探索を打ち切ってよいか」という判断を行うことで、評価が安定しにくい局面などで改善ができるのではないかと思っている。

 探索というものは次の3モジュールによってモデル化できるのではないかと考えている。

f:id:tokumini:20200619133856p:plain
探索のモデル

 たとえばAlphaZeroでは

というように解釈できるのではないかということだ。

 自分の研究を振り返ってみると、B4のときはAlphaZeroにCategorical DQNを混ぜるということをやっていて、これは上の図で言えば評価器の改善を目指したものだった。M1では先週JSAIで発表したように遷移モデルの学習について研究をしていて、これは図の中央にそのまま相当する。というわけでM2で一番上の部分を扱うとすれば統一的に解釈できるのかもしれない。まぁそのために無理やり捻り出した感もあるモデルなのだが。

 探索マネージャの学習について、知っている限りで一番近そうだと思っている論文は以下の「Learning model-based planning from scratch」というDeepMindが2017年に出したもの。(僕DeepMindの論文を後追いしているだけの人間では?)

 上の論文で記憶モジュール(LSTM)が使われているように、探索マネージャには記憶(特にワーキングメモリ)が必要であるように思われる。たとえばモンテカルロ木探索では置換表がそれまでの探索結果を記録しており、それを参照することで次に探索するべき局面を決定している。(αβ探索では置換表は絶対に必要なものではないが、再帰関数を使っているループそのものが他の行動の価値を記憶している部分と見なすことができる……?)

 ワーキングメモリとしてLSTMで十分なのか、もっとリッチなもの(Neural Turing Machineとか、それをさらに発展させたらしいDifferentiable Neural Computersとか? ちなみにこのDNCもDeepMindの論文)を使う必要があるのかはよくわからないが、木探索では感覚的には明瞭な記憶が必要な気がするのでLSTMよりは外部メモリを明示的に使う手法の方が良さそうかなと思っている。

 全体として探索自体の学習というのはかなりロマン寄りの研究テーマっぽいのでまともな形(実際にプログラムに組み込んでSOTAが達成できるということ)にはならなさそう。「次に評価するべき局面と行動」をどう指定するのかとか、評価結果をどういう形で取り込むかとか、そもそも木という制約を上手く入れないとまともな学習はできなさそうだとか、課題は多い。

 なにか似た論文の情報や質問等あればコメント欄なり@tokumini_ssなりに教えてもらえるとありがたいです。

【コンピュータオセロ8】全結合ネットワークでの学習・対局

要約

 全結合ネットワークにした場合、CNNの場合よりもレートが200ほど落ちてしまった。オセロにおいて終盤の評価が難しいのはゲームの性質による問題の可能性がある。

背景

 オセロでの対局を検証していると、終盤での状態価値推定の精度が良くないのではないかという疑念が生まれた。たとえば、以下のような局面においてNNによる推論では評価値分布は中央図のようになるが、実際のところはこれは引き分けであり、右図のような評価値が正しい。

f:id:tokumini:20200612132906p:plain

 原因の一つとしてCNNが局所的な特徴しか取れていないため全体を考慮した判断ができていない可能性を指摘いただいた。

 よって全結合NNにして実験を行った。

実験

 今までチャンネル数64の残差ブロック5(つまりおおよそ10層CNN)としてたNNを、隠れ次元数512、5層の全結合NNに変更して学習、対局を行った。

実験結果

f:id:tokumini:20200612133418p:plain

 CNNよりもレートが200以上下がってしまった。終盤の様子を見てみても、やはり価値推定の精度はあまり高くなさそうだった。

f:id:tokumini:20200612133904p:plain

考察

 オセロの終盤で価値推定精度が低いことは、ネットワーク構造の問題やプログラムのバグなどではなく、ゲームの性質に由来する本質的な問題であると思われる。(将棋の方でこういう乖離があまり起きていないのは、自己対局だと中盤の時点で差が付き、一手差争いのような終盤になっていないためである可能性が考えられる。)

 上の図のように、終盤の局面から探索が開始される場合は800回の探索中に終端に行き着くので評価が間違っていることがわかるが、800回目の探索で丁度終局の一手前などとなる場合、そこで得られるNNでの評価がめちゃくちゃであるため探索に悪影響が出ていそうだ。

 これに対処するためには、価値推定の精度を上げる工夫を入れるよりも実際に盤面を動かして勝敗判断をした方が効率が良い可能性がある。つまり、ネットワークを大きくすることなどではなく、探索中の工夫により改善を目指したいものであるように感じられる。

 一つ考えているのは静止探索的な概念を導入することだ。

竹内 聖悟,金子 知適,山口 和紀 局面の情報を利用した,静止探索中の動的手生成

 将棋でも、たとえば詰ましにいって王手をかけている途中で形勢判断をすることにはあまり意味がないと思われる。しかし現状のMCTSではそのような局面でもValueを推論し、その結果をバックアップしていくため、末端以外で評価を勘違いしていた場合など評価がおかしくなっているかもしれない。

 とはいえ、MCTSの都合上、途中でノードの評価をスキップしてしまうとPolicyが展開されず探索を進められなくなってしまうので、完全に評価しないということは難しそうであり、Valueのバックアップにおいて今回の評価値をどの程度寄与させるかを調整するなどが現実的な手段かもしれない。

【コンピュータオセロ7】優先度付き経験再生の検証

要約

 優先度付き経験再生はオフにした方が良さそう。

背景

 比較実験でAlphaZeroの学習が妙に弱いことがわかった。

 原因として優先度付き経験再生が悪さをしている可能性が考えられた。優先度付き経験再生は1年前の検証で結果が良かったので採用したのだが、実装などが大きく変わりレートも上がった現在だとかなり事情が違うかもしれない。

 優先度付き経験再生は損失を基準にやっている。N個のデータがリプレイバッファに格納されているとして、 i番目のデータ選択される確率 p_iを前回計算した損失 l_iを用いて


p_i =  \frac{l_i^{\alpha}}{\sum_j l_j^{\alpha}}

と計算する。 \alpha = 0とすると確率が \frac{1}{N}となるので通常のランダムサンプリングに一致する。

実験

 前回の結果(の一つ)は \alpha = 2のものであった。比較対象として新たに \alpha = 0で各実験をやり直した。

f:id:tokumini:20200522190603p:plain

  \alpha = 0とするとAlphaZeroにおける性能がものすごく改善され、ScalarやCategoricalでも \alpha = 0の方が性能が良かった。ScalarやCategoricalでの改善量は微差だが、全体として優先度付き経験再生はオフにした方が良いということになる。

 この点から考えてみると、 \alpha = 2でCategoricalの性能が良かったのは、Value損失の計算方法が違う影響で損失のばらつきが小さくなるなどして、優先度付き経験再生の悪影響を受けにくかったということなのかもしれない。学習中の損失を見てみると

f:id:tokumini:20200522212816p:plainf:id:tokumini:20200522212819p:plain
左:Policy損失 右:Value損失

となっており、 \alpha = 0のときはPolicy損失が改善されることがわかる。Value損失はCategoricalの場合に大きいことがわかり、これの影響である可能性は十分にある。

【コンピュータオセロ6】2つネットワークを使った強化学習

要約

 2つネットワークを用いて対局させても学習時間が長くなるばかりで学習高速化とか性能向上といった改善は見られなかった。

背景

 個人的に、今まで手元で行ったAlphaZero学習ほぼ全てについて、最終的に得られるモデルが

  • 対抗形に弱い
  • 穴熊の評価がおかしい

という性質を持つことについてずっと違和感を抱いている。

 これらは要するに探索範囲が狭い(生成する棋譜が特定の戦型に偏っている)ことが原因だと考えられ、特定できていないだけで居飛車についても悪影響が出ているのではないかと思っている(たとえば未検証だがじっくり組み合う相矢倉とかも弱いかもしれない)。

 探索範囲を広げるためには、複数のエージェントを学習させるという方法があると思われる。今回は単純に2つのネットワークを訓練しデータ生成はこれらを両方使って行うという手法について実験を行った。

実験

 全く同じアーキテクチャのネットワークを2つランダム初期化し、それらを用いてデータ生成、学習のサイクルを行っていく。

データ生成

 データ生成では実装の都合上、1回推論するごとに使うネットワークを切り替える方式で行った。1局面あたり800回探索(ネットワークでの局面評価)をするわけだが、そのうち400回はネットワークAを、残り400回はネットワークBを使う形になる。今まで1つのネットワークで自己対局していたところを交互に使うだけになるので、これによる計算量の増加はない。

 本当は手番ごとに入れ替えることが理想だとは思うのだが、GPUキューに貯まる評価要求局面は手番がバラバラになり得るので難しい。愚直に実装すればできないことはないが、生成速度が落ちてしまいそうなので見送っている。

学習

 学習はリプレイバッファは共通、サンプリングは別で行った。学習ステップで2つネットワークの重み更新を行うので、学習部分は計算量が2倍になるが、基本的にAlphaZero型の学習は「学習の計算時間 <<<< データ生成の計算量」となるので学習が2倍になっても総学習時間にはあまり影響がない。これは

で主張されているのと同じ。

実験結果

f:id:tokumini:20200521102233p:plain

 学習速度、性能などほとんど変化はなかった。オセロで探索範囲が狭い挙動が出ているかどうかは確認していないので、ゲームに依存する可能性ももちろんあるが、2つネットワークを使うことが一般に性能向上に繋がるわけではなさそう。

 学習時間はほとんど増加しないと思っていたが、実際はオセロだとデータ生成部分が軽いからかかなり差が出て、ネットワーク1つだと18時間45分、2つだと27時間29分であり、約1.47倍となった。冷静に考えると教師あり学習でも0.5Mステップ回そうとするとそれなりに時間はかかるので、無視できるような量ではないか。

余談

 以下余談。穴熊や、そもそも振り飛車みたいな居飛車とは大きく異なるような指し方を発見するためには、一つ一つの指し手レベルでのランダム性ではなく方針レベルでのランダム性が探索において重要そうな気がしている。それを実現する上でマルチエージェント的にやっていくというのは自然な方向に思われるが、今回みたいに雑にやって上手くいくというわけではなさそうか。もちろんオセロだったから変わらなかっただけという可能性も十分にあるが……。

 マルチエージェント的なやり方をするにしても複数のネットワークを(同程度の棋力を持ちつつ)性質の異なるものとして学習させる必要がありそうだとは思っていて、全体を見て制御する主体が必要になりそう。そうなるとほぼ階層的強化学習そのものなのでは? という気もするが、良い定式化の方法を知っているわけでもない。

 そもそも問題意識自体が合っているのかどうかもやや不安になるところ。AobaZeroとかは普通に後手四間飛車を指すらしいし、Miacisが振り飛車を指さないのは単にハイパーパラメータのちょっとした違いが原因だったりするのかもしれない。データ生成量が少ないまま学習を繰り返すので最初に発見した良いやり方(それは飛車先を突いていく場合が多そう)にすぐ適合してしまい、振り飛車が切り捨てられるのが早すぎるという可能性もありそうなところ。むつかしい。