128チャンネルで1ヶ月学習(2回目)

コンピュータ将棋

　5月の世界コンピュータ将棋オンライン大会が終わってから、実験サイクルを早めるため学習は64チャンネルのネットワークで行っていた。しかしlibtorch1.5.0版に対応した影響で後方互換性がなくなり、すぐ動かせる強いパラメータが手元ないと細かい動作の検証で困るため、128チャンネルのネットワークで1ヶ月の学習をやり直した。

実験

　ほぼMiacisのWCSOC2020版

と同じ内容で実験を行ったが、「学習スレッドのスリープ時間と学習速度の関係」から生成量2倍で学習ステップ数1/2にしてもほぼ変わらないという結果を得ており、それを追試も兼ねてそこ（と学習率の減衰）についてだけ変更を行った。

変更のある項目 今回 前回
生成量 1ステップあたり256局面 1ステップあたり128局面
学習ステップ数 1M 2M
学習率 学習の80%経過時点で1/10 学習の50%経過時点、75%経過時点で1/10

学習結果

　横軸に学習時間、縦軸にfloodgate棋譜を用いた検証損失を取りプロットすると次のようになった。

f:id:tokumini:20200727100602p:plainf:id:tokumini:20200727100604p:plain
左:Policy損失　右:Value損失

　今回の学習の方が進みが良く、前回の学習の学習率減衰が起きた後と同じくらいの損失値を学習率減衰が起こる前で実現できていた。

　横軸を学習ステップ数にして比較した結果も載せておく。

f:id:tokumini:20200727102916p:plainf:id:tokumini:20200727102920p:plain
左:Policy損失　右:Value損失

　最終的な学習時間は649時間28分(≒27日)であった。前回の672時間32分より約一日短くなったが、これは学習ステップ数が少なくなった影響である。

　最終ステップでの損失は具体的には

手法 Policy損失 Value損失
今回 1.897591 0.672531
前回 1.923749 0.677997
差分 -0.026158 -0.005466

となった。以前の検証ではEloレートと損失の間に線形な関係を仮定すると係数はPolicy:-2135、Value:-8649と算出され、今回の結果と合わせるとPolicy損失の差分から計算すると55.8、Value損失の差分から計算すると47.3のEloレート向上が予想できる。

対局結果

　Miacis(1手1秒)とYaneuraOu/Kristallweizen(1手0.2秒、4Thread、定跡オフ)で対局を行った。

手法 勝数 引分数 負数 勝率 相対Eloレート
前回 317 0 183 63.4% 95.4
今回 697 2 301 69.8% 145.5

　約Eloレート50の伸びであり、ほぼ想定通りといったところ。

　YaneuraOu/Kristallweizenは持ち時間を増やしていくとかなり強くなる印象なのでなかなか同条件で互角というところまではまだ遠そうだが、また少しは近づいたか。

MCTSnetの学習（仮）

探索系NN

　MCTSnetのだいたいの実装が終わり、将棋での教師あり学習を回し始めている。

　簡単に回してみたところ、Backupネットワークでの振る舞いが上手くいっていないように思えたので、論文の3.4 Design choicesに記載されているように、Backupネットワークをゲート付きの差分更新にして学習を行った。

f:id:tokumini:20200723101650p:plain

実験

　floodgateの2016年〜2019年の棋譜を用いて、棋譜で指された行動をOnehotの教師信号として交差エントロピーで損失を計算した。MCTSnetの正しい学習方法は以前記事に書いた通りだが、今回はとりあえず簡便のため、 M = 10回の探索まで都度ルートノードからReadoutを行い、教師と比較して損失を計算したものの和

\displaystyle \sum _ {m = 1} ^ {M} l _ m

という単純な損失について学習を行った。

結果

f:id:tokumini:20200723095000p:plainf:id:tokumini:20200723095015p:plain
左:学習損失　右:検証損失

　図には1回探索後から10回探索後まで10本の学習曲線があるわけだが、それらがほぼ全て重なるような形になっている。学習が安定したようにも見えるが、Backupネットワークにゲートを追加した結果ゲートが常にOFFになるよう学習され、探索によってルートノードの埋め込みベクトルが全く更新されなくなっただけの可能性もある。

　ちなみにこのPolicy検証損失値が4.0付近という値は非常に悪い。今までのAlphaZeroモデル(10ブロック128チャンネル)などでほぼ同じデータに対して検証損失を計算すると、教師あり学習の場合なら1.5、強化学習の場合でも1.9ほどまでは落ちる。精度が低い原因としては

  • 埋め込みネットワークが3ブロック64チャンネルと小さい
  • バッチサイズ1なのでBatch Normalizationが機能していない
  • そもそも学習もやや足りていない

などが考えられる。どれも基本的にどうしようもない問題なので改善は難しいかもしれない。ネットワークは大きくしたくないし、バッチサイズ複数に対応するのもあまり現実的ではないように思える（MCTSのパスの長さが都度異なるのでどう実装すれば良いのかわからない）。今回の学習量でもかかった時間は2080tiのマシンで14時間ほどで、バッチサイズが1なのでどうしても学習速度は高くならない。

　そもそも探索回数10程度で将棋ではっきり強くなるかはやや疑問であり、どちらかというとオセロの終盤での評価がまともになる可能性を感じているため、オセロでどうにか棋譜を探して教師あり学習をやるというのが現実的な線だろうか。

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

探索系NN

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

実験

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

具体的なデータ生成手順

  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

探索系NN

　以下の続き。

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

　ステップ1

　ステップ2

　ステップ3

　ステップ4

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

f:id:tokumini:20200704173449p:plain

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

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

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

　というところまで。

Differentiable Neural Computersの実装

探索系NN

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

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

あたりが可能性ありそうなのかなと思うところ。調べていると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の提出で見るとaddとsubがハイライトされるのはなんなんだろう。予約語ではないと思うが……。

　提出

E - Red Scarf

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

　提出

F - Strivore

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

　提出

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

探索系NN

　最近、「探索の仕方自体を学習する」手法について興味が出ている。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のバックアップにおいて今回の評価値をどの程度寄与させるかを調整するなどが現実的な手段かもしれない。