AtCoder Beginner Contest 134

結果

tokuminiさんのAtCoder Beginner Contest 134での成績:320位
パフォーマンス:1845相当
レーティング:1913→1906 (-7) :(

 D問題で4WA出したのが痛かった。

 提出

A問題

半径aの円に内接する正十二角形の面積は3a^2であることが知られています。 

知らなかった。

B問題

 \lceil \frac{N}{2 D + 1} \rceilで求まる。整数型だと(a + b - 1) / bで切り上げできるというの便利だなと書くたびに思う。

C問題

 A_iが最大値のときだけ二番目に大きい値を出力してそれ以外は最大値を出力する。この一番大きい値と二番目に大きい値を求めるというやつはモンテカルロ木探索の終了タイミング判定でやるので手が覚えていた。

D問題

 後ろから入れていけば不可能になる場合はないなと思ったけど、ボールを入れる場合に約数をO(\sqrt{N})で列挙して入れていくやり方で実装していたら脳が混乱してバグらせまくった。4WA出した末に調和級数の和が\frac{1}{N}みたいなことを思い出して普通にやったらAC。前者の方針通せなかったのは約数列挙で割り切れるときiN / iの両方を考慮しないといけないのにiの方しか考えてなかったからだった。凡ミス。

E問題

 std::multisetでやっていくと通る。

F問題

 ずっとdp[i[j] := 1からiまでの順列で奇妙さがjになる個数]というものの遷移を考えて全然とけねーってなってた。情報が足りない感じはあったけど確信できなかった。

 解説PDFを読んでもあまりよくわからなかったが解説放送を見て納得した。

f:id:tokumini:20190721143946p:plain

 この図がすごい。放送では遷移はまぁ考えればできるでしょとのことだったけどわりと時間かけてもわからなかったのでPDFに戻って理解してAC。この遷移を詰めきるのもなかなか難しいと思う。面白い問題だった。

AtCoder Grand Contest 035

結果

 A,Bの2完。順位は悪くなかったしレートも上がったけど嘘解法もありC問題を解けず、反省点は多かった。

f:id:tokumini:20190715093426p:plain

A問題

 300点という見た目に惑わされて「簡単に解けるはずなのに全然わからない」と焦るのもいい加減やめよう。確かAGCの300点はABCの300点とは違うと明言されていた気がする。

 周期3でループする感じになることに気づいてやや安心したが実装が上手くできなくてひどかった。各数字の出現回数をmapに詰めてごちゃごちゃ場合分けしてゴリ押しして通したが、よくこれでWA出さなかったものだ。と思って今冷静に見るとどうも間違っているようだ。自分のプログラムではNが3の倍数で要素の種類が2種類以上のときは、数列全体のXORが0ならばYesとしているが、それでは次のようなパターンで明らかにYesになってしまう。

6
1 2 4 1 2 4

 他の人のACしたコードで試してみるとちゃんとNoになった。テストケースが弱かった? なんにしても運が良かっただけ……。

 提出

B問題

 手元でいろんな例を考えると

  1. 辺の数は偶数じゃないとダメそう
  2. 次数が1のノードは吸い込む側にしかなれない
  3. 上の二つに気をつけるとわりと適当に組み始めてもなんとかなる

ということに気づいて、じゃあ次数の小さい順にpriority_queueから取り出して適当に辺を繋いでいくことを繰り返していけばいいんじゃねというコードを出したら通ってしまった。自分の解法の正当性がよくわからないが、解説PDFとやや近い考え方ではあるんだろうか。はっきりとはわからない。

 提出

C問題

 まず構築可能/不可能の条件だけ考えて、2の冪乗+1だけが可能とか、奇数なら可能とかいろいろ考えつつassert仕込んだ提出をして、結局2の冪乗だけNGであると把握した。構築可能な場合、Nの偶奇で場合分けして、奇数の場合は4以降の数字をj, j+1で2個セットにして1にくっつければ良くて、というところまではわかったのに偶数の処理がわからなくて結局時間切れ。最後終了3分前に偶数のときは4,5,6をセットにして3にくっつければ消えそうと思ってコード出したときは心拍数めちゃ上がってたけど全然違った。そもそも3にくっつけてもダメだし7,8が組になってしまう時点で論外なのはすぐ気づきたかった。

 惜しかったという感触はあったけど、しかし終了後に解説PDFを読んでも偶数の場合の処理がすぐには理解できなかったのであと10分,20分あっても実は解けなかったかもしれない。1ではなくN + 1の方にくっつけて、そうすると偶数も奇数もN + 1に全部くっつくからそこでNが適当な3つ組から構築可能なんだな。やはりすぐ思いつけた自信はないので仕方ないか。

 提出

感想

 今回かなりパズル要素が強い回だと感じた(構築だから?)。その分かわからないけどよくわからない抜け道も発生して順位表が荒れると。いつものAGCといえばそうなのかもしれないが……。自分に関して言えばAは嘘解法、Bは無根拠無証明で通しただけと動きがひどかった。幸運に恵まれて結果自体はいいペースで行っていたのに、まともに解けそうだったC問題をきちんと仕留めきれないようでは。相手のエラーと四球で巡ってきたチャンスに併殺打でおかえしする感触だった。

学習中に生成した棋譜の分析

要約

 生成している学習データの質が悪い可能性がある。質を高めていくために(1)価値を考慮した行動選択 (2)c_{puct}の調整 (3)リプレイバッファサイズの調整 などを考えていきたい。

実験

 前回1Mステップの学習を行ったが、まだ収束していないようにも思えたので2Mステップの学習をランダム初期化した(前回とは異なる)パラメータから行った。

 検証損失推移

f:id:tokumini:20190712100644p:plain

 技巧2(深さ8)と1手0.25秒で500局対局を行った結果

f:id:tokumini:20190714104648p:plain

 1Mステップ時点でR2600前後という結果は前回得られた結果とほぼ同等である。今まで実験していた結果からしても、試行による最終的な棋力のバラつきはあまりないように感じられる。これはScience版AlphaZero論文でも似たようなことが主張されている。

f:id:tokumini:20190712101139p:plain

 ここから本題として、上記の学習を行う際に、生成した対局を500局に1局の間隔で保存した。学習データの質を確認するため、保存された棋譜4611局について簡単な分析を行った。

手数の統計情報

項目
平均 75.5
中央値 74
最小値 317
最小値 14

 全対局詰みまで指しているにも関わらず平均手数は短い。また512手に到達した場合は引き分けとしているのだがそこまで到達する対局が存在していない点も気にかかる。千日手による引き分けは実装していない(ノイズによって同一局面でも指し手がバラつくと考えている)のだが、ここまで長手数にならないものか。

 一番気になる14手で終わった対局は次のようなものであった。

f:id:tokumini:20190711202014p:plain

 他にも30手以内で終わっているものを何局か見たところ、どうも上と同じように▲6八玉▲7七角▲7八銀の形で△7七角成と取られた場合に▲7九玉と逃げて頓死するパターンがあるようだった。12手目△7七角成とした局面について2Mステップ時点のパラメータを用いて800回の探索をさせたところ

指し手 ニューラルネットの出力方策 探索回数による方策 行動価値
▲同銀 91.7% 98.6% +0.047
▲同桂 1.7% 0.2% -0.200
▲同玉 1.4% 0.2% -0.156
▲5八玉 3.6% 0.6% -0.960
▲7九玉 1.7% 0.6% -0.977

となった。▲5八玉と▲7九玉を合わせた1.2%の確率でまともな将棋にならないと考えるとなかなかなものである。ディリクレノイズがない状態でこれなので実際はもう少し高い確率でダメになっていてもおかしくはない。

 他の状況での角交換に対しては角を取り返す手で100%占められる場合が多かったが、場合によっては角を取り返さない手にも探索が割り当てられる場合もあった。

f:id:tokumini:20190714120155p:plain
検討欄左から2列目がニューラルネットの出力方策、3列目が探索結果の方策。▲6九玉に0.1%の確率が生じている

 これは右辺の形が多少異なっていても同様であった。興味深い点としては▲6八銀と上がっている場合には▲同銀が100%となるようだった。

f:id:tokumini:20190714121234p:plain

 王手であるかどうかによって合法手の数が大きく変わることが影響しているのかもしれない。感覚的には合法手が少ないほうが学習しやすいのではないかと思われるのだが、合法手が少ないと悪手も探索され教師分布にずっと確率が残ってしまうのだろうか。

 原因はともかく、あまりにも行動価値が低い手は選択しない方が良いと考えられる。そのような方法としては

  1. 最良の行動価値より一定以上価値が低い行動の選択確率を0にする
  2. 行動選択に利用する分布を行動価値にソフトマックス関数を適用したものにする

などが考えられる。「方策=行動価値にソフトマックス関数をかけたもの」とすることは、たとえば芝浦将棋Softmaxが行っている。また、行動価値ではなくアドバンテージ(状態価値と行動価値の差分)についてはよくわかってはいないが理論的などうのこうのがあるらしい。

Evaluation Curve

 上の結果から悪手が混じっている割合が多く、評価値と最終的な勝率が乖離してしまっているのではないかと考えた。よってevaluation curve(各評価値における先手から見た最終的な勝率)を描画してみることにした。評価値は[-1,1]を1000倍した[-1000, 1000]で出力しており、それを50ごとに40区間へ分割して各区間での最終的な勝率を集計した結果が次のようになる。

f:id:tokumini:20190712102225p:plain

 状態価値(つまり収益の期待値であり、適切に線形変換すれば勝率になる)として学習をしているため線形のようになることは正常であり、特に変ではないと思われる。

評価値差分の絶対値

 統計的には評価値通りの勝率になっているが、評価値がなだらかに推移していない可能性があると考えた。1手先の評価値との差分の絶対値について50間隔で分類して出現割合をプロットした。

f:id:tokumini:20190712172703p:plain

 グラフの推移からすると750から1000あたりの割合がやや多めに思える。先に挙げた頓死のように0付近から-1000付近へ遷移する悪手が多いのかもしれない。比較対象がないのでこれがまずい数なのかがよくわからないが、雑に読み取ると0.1%ほどの確率で1000点以上の変動が起きると考えられる。1000手に1手、つまり13局に1回ほどの割合で大悪手が発生しているとなると多いようにも感じられる。

各段階での指し手の傾向

 趣向を変えて指し手の傾向についての推移を調べた。4611局を学習の進行に応じて40段階(各115局)に分けてそれぞれで初手の割合をプロットしたものが次となる。

f:id:tokumini:20190712140047p:plain

 早い段階で▲2六歩や▲7八金などが多くなっており、居飛車っぽい将棋をすぐ学習しているのではないかと思われる。一方で全体的にどれか一つに指し手が偏っているように見える。偏る指し手は変わっているのでノイズが小さいということでもなく、どちらかといえばc_{puct}が小さすぎるということなのだろうか。根拠のない勘としては、もう少しなだらかに指し手の割合が変化していった方が良いのではないかと感じられる。リプレイバッファが小さすぎて同じようなデータばかり学習している可能性もあるかもしれない。

 他にも行った方が面白そうな解析案があれば教えていただけると気分次第でやったりやらなかったりします。

ELF OpenGo: An Analysis and Open Reimplementation of AlphaZeroを読んだ際のメモ

出典

 International Conference on Machine Learning 2019に採択。arXivには2月ごろに投稿されていたので以前もちらっと読んだことはあったが、一応再確認。

概要

 AlphaZeroのオープンソースによる再実験を行い、学習や推論における挙動について分析

詳細

実験設定

  • 自己対局中は常に温度1(つまり探索回数に比例した確率で行動を選択)
    • Miacisでもこうしている。理論的な正当化に必要な気がしたのでこうしているが、実際終盤の精度がどうなっているのかは未確認
  • c_{puct} = 1.5 (arXiv版AlphaZeroの定式化を利用)
    • 手元で\logを使うScience版AlphaZeroの定式化は試してみたが、あまり性能向上が見られないので大差ないのかなという印象
  • リプレイバッファサイズ 500,000ゲーム
    • 囲碁の平均手数を200手くらいとすると約20Mデータとなるか。Miacisでは1Mにしているのだが、小さすぎるかもしれない
  • 自己対局中は1,600探索
    • 単純に2倍の計算資源(あるいは時間)が必要になるのでここを増やすのはきつい
  • 256フィルタ, 20ブロック
    • 本当にこんなに巨大なネットワークを使う必要があるのかなというのは疑問なのだが
  • 学習率は0.01から始めて0.5Mステップ経過ごとに1/10(全学習ステップは1.5M)
    • AlphaZeroも学習率0.2から始めているとあるけど、実は囲碁では0ステップ後に学習率を1/10するとあるから0.02スタートではある(Science版)。チェス、将棋だと10倍も大きい学習率で始めて良いというのが直感的には納得し難いが、そういうものなのかもしれない
  • バッチサイズは2048
    • AlphaZeroに比べて1/2だがステップ数を2倍にしているのでほぼ同等の学習になっているのだろう
  • ステップあたりの生成量と学習ミニバッチサイズの比は約13:1
    • Miacisでは1:4くらいでやっている。ここがかなり効いてくるのかもしれないとは思う

学習推移の分析

性能

f:id:tokumini:20190711134123p:plain

  • (a)最初の方にValue損失が0に近くなっている
    • Valueの評価が偏ってどちらかが勝つデータしかなくなるため
    • 先手が勝つデータと後手が勝つデータの割合を一定にすることで解決
    • 将棋では起こりにくいことかもしれない
  • (b)対戦相手を固定した場合の勝率推移
    • 結構分散が大きく、学習率を小さくしても分散は小さくならない
  • (c)プロ棋士棋譜との一致率はすぐ飽和するので当てにならない
学習の段階性とシチョウの学習

f:id:tokumini:20190711134228p:plain

  • (a)(b)終盤の方から徐々に学習が進んでいくという仮説に対してやや否定的な結果
    • 中盤と終盤で学習速度はあまり変わらず、序盤も過学習せいらしい(ここはよくわからなかった)
  • (c)シチョウの予測(盤面全体に関わり手数が多いため難しい)は学習後半のモデルでも不十分
    • 探索回数を増やしても改善しきらない

パラメータ探索実験

c_{puct}

f:id:tokumini:20190711134535p:plain

  • 1.5が良さそう
バーチャルロス

f:id:tokumini:20190711134614p:plain

  • 1が良さそう
探索回数による性能の変化

f:id:tokumini:20190711134654p:plain

  • 持ち時間を2倍にしたときの性能の上がり方が先後で異なる
  • ベースの探索回数を増やすと先手は2倍にしても勝率が上がらなくなる
    • これは囲碁特有の問題かと思わないでもないが
  • プロトタイプとの対局によると基本的に探索回数2倍でEloレート+200
    • ここもゲームに依存する性質かもしれない

Discussion

 AlphaZero型学習の問題点など

  • 学習に必要な対局数が膨大
  • シチョウが学習できていない
  • 性能が不安定
    • 学習率を下げるとむしろさらに不安定に→ほとんど変わらないモデルによる同じような対局ばかりになってリプレイバッファ内に多様性がなくなることが問題?
  • 終盤から徐々に学習されていくわけではなさそう

所感

 AlphaZeroの学習はとにかく膨大な量を必要とする点が実験していく上で非常につらいので、何はともあれ高速化をしなければ話にならないという気持ちが強い。その点で終盤から徐々に学習されるわけではなさそうという指摘は大きいものなんじゃないかと感じられる。手元での学習推移や学習途中のパラメータにおける指し手の傾向を見ても、どちらかといえばPolicyの偏りが原因で(強化学習の意味での)探索が上手く進んでいない可能性はありそうに思える。ディリクレノイズによるランダム性の与え方をもう少し工夫できないかなと考えたいところだが、探索を促進する内発的動機づけとかそちらの論文を読んでみるのが良いのだろうか。

AtCoder Beginner Contest 133

結果

 E問題までの5完で157位。パフォーマンス2118でレーティングは1854 → 1883 (+29)。F問題が難しい(というか重実装だった)影響でEまで早く解けていればそこそこな順位になった。始まる前から疲れていて不安だったがなんとかなってくれて良かった。

A問題

 そうですね。

 提出

B問題

 根号取ったものが整数になるか判定するところでやや悩み、結局普通に2乗が超えるまでループで回してみて一致する整数があるか判定した。計算量は確かめてないけど小さめだったからなんとかなるだろうという勘。解説PDFを見るにそれで良かったようだ。

 提出

C問題

 R - Lが2019より大きいかどうかで場合分け。小さい場合にループ中で普通に掛け算してから剰余計算してしまったがL,Rが大きいとまずいので制約に救われた。手癖で全ての整数型をll(int64_t)で確保するという脳死ムーブが強すぎるのでメモリ量で痛い目を見たい。

 提出

D問題

 適切にぐちゃぐちゃやっていけばなんやかんや式が立ちそうだなとは思ったが全然上手くやれなくて呆れながら解いていた。山1の右半分へ流れる量を変数においてヒュッとやるのが最終的にはわかりやすかったか。

 提出

E問題

 わりと何も考えず再帰関数の中でダメな条件を順番に弾いていくとなんとかなった。これが早く解けたのが順位的には大きかったけどよくわからないままに通ったという感じでやや釈然としない。

 どうでもいいことだけど、エッジを辿る場面では次のノードをnext命名することが多いんだけど普通にstd::nextが存在するのでやめたほうが良さそうだなとAtCoderシンタックスハイライトを見ていて思った。

 提出

F問題

 パッと見で最小共通祖先を使うんじゃないかなという感じで、考えていくとなかなか惜しいところまではいく。しかし各色について各ノードまでに辺が何本あるかを保持するとO(N^2)になるのでいやー難しいと思っているうちに時間が経ってしまった。このあたり疲労感が強くて椅子に座っていられず寝転がって(つまり紙とペンを使わず)考えていたもの響いたか。

 必要な情報をメモしておいてDFSしながら答えていけばなんとかなるかもしれないとは思ったけど実装が非常にやばいことになりそうで手を付けるか迷っているうちに残り20分くらいになる。そこから書き出したが時間切れで終了。

 解説PDFを見て結構方針としては合ってそうだった。ほぼ想定した書き方をしてACする。AtCoderで150行近く書くのやば。

 日頃変数はmainスコープの中で書き始めるので再帰関数を外に書こうとすると変数をグローバルに置き直す作業が必要になったりするのがちょっと嫌。なので最近は単純なDFSならstd::stackを使って書いているんだけど、色情報を一つ持って更新しながらやっていくには再帰関数で書く方法しか思い浮かばかなかった。main関数の中にラムダで書いてみたけど、これもどうだろうか。

 最小共通祖先はこれで検索して一番最初に出てきたページをほぼそのまま写経した。原理は全然わかってない。ライブラリを整備する元気もあまり出ず。マクロとかスニペットとか自動サンプルチェックとか、そういうのも入れた方が良いんだろうなとは思いつつ、しかし最近はむしろusing ll = int64_t;すら消したいよなという気分にすらなっていて……。

 提出

思考時間とレートの関係

要約

 Miacisではおおむね思考時間を2倍でレート+100となる。MCTSのスケール性もαβ探索と比べてあまり変わらないのではないか。

背景

 AlphaZeroの論文(arXiv版)には1手の思考時間とレートの関係が図で表されている(Figure 2)。以下に将棋の方だけを切り抜いたものを示す。このAlphaZeroは40,000NPSほどのものであり、基準としているソフトはelmo(1手の思考時間40msec)である。

f:id:tokumini:20190626181852p:plain

 uuunuuun氏はこの図から思考時間を10倍にするとレートが800伸びるという関係を読み取っている。対局数は少ないが実験も行われている。

 またAlphaZeroの論文(Science版)では、1手の思考時間固定ではないが、思考時間を対戦相手に比べて短くした際の勝率が棒グラフで示されている(Fig. 2B)。これは58,000NPSでの結果と書かれている(Table S4)。

f:id:tokumini:20190626172925p:plain

 将棋についてこの棒グラフの幅から勝率を読み取ってレート推移を作ったものが以下のグラフになる。

f:id:tokumini:20190626183451p:plain

 こちらでは、特に比が1/3以上の領域において、思考時間10倍でレート+160ほどとなっている。あまり伸びが良くないように思われる。

 Science版の方では比が1のとき、持ち時間3時間+1手ごとに15秒追加なのでもともと持ち時間は多めである。1手の思考時間として残り時間の1/20を使うとあったため、次のような思考時間になっている。

f:id:tokumini:20190701095624p:plain

 1/100の持ち時間でも序盤は1手数秒あり、NPS自体も上がっていることを考えると、冒頭のarXiv版論文で示されたグラフの右側にやや重なるような位置関係なのではないかと思われる。

 elmo側はエンジンで定められた持ち時間制御をそのまま用い、これは1手1秒のelmoに対して98.85%(R+773.7)だったとある(Table S5)。これらの結果から適当に縮尺を合わせて貼り付けると次のようになる(位置関係はかなり適当なのでイメージ程度に)。

f:id:tokumini:20190701145242p:plain

 もとのグラフがどのように計算して出されていたものかわからないが、スケール性に関してはやや怪しく、特に持ち時間が長くなるとそこまで伸びないのではないかと思われる。実際にarXiv版ではMCTSがαβ探索に比べて持ち時間に対するスケール性が良いのではないかという主張があったが、Science版では(私が確認した限り)なされていない。

 このような事実を念頭に置いて、自作の将棋ソフトについても思考時間とレートの関係を推定した。

実験

 前回得られたパラメータを用いて技巧2(深さ制限9, 10)と持ち時間を0.25秒、0.5秒、1秒、2秒の4種類についてそれぞれ500局対局を行った。http://www.uuunuuun.com/englishから技巧2(深さ制限9,10)のレートをそれぞれ2663, 2808として推定されたレートを次に示す。

f:id:tokumini:20190701100814p:plain

 大雑把に見積もって思考時間2倍でレート+100という結果となった。

所感

 αβ探索でも異なるソフトに対しては思考時間2倍でレート+100とある。

 C_{PUCT}など調整が不足している可能性はあるだろうが、MCTSでもαβ探索でもスケール性に関しては大差ないのではないかというのが現状の推察となる。

AtCoder Beginner Contest 132

結果

 E問題までの5完で365位。変な勘違いばかりして解くのが遅く、全然ダメだった。

A問題

 すっきりとしたやり方がわからなくて結局std::mapに各文字の出現回数を詰め込むというオーバーキル気味なことをやった。解説PDFにあるソートして比較が一番スマートなのかな。

 提出

B問題

 いつも開始直後は問題の読み込みが遅くて、B問題から解き始めれば回避できるのかなと思ってこちらから解き始めたがあまり違いはなかったか。

 提出

C問題

 ソートして切れ目を考えるだけ。ちゃんと考えを詰めきってから短いコードを書くようにできたのでそこは良かったと思う。ここまではそこそこ順調だったんだけど……。

 提出

D問題

 「同じ色のボールは区別が不可能」という文字を目は認識していたのに脳は認識してくれなくてずっと区別できる状態での解法を考えていた。区別できる状態での解法をひねり出すのにも時間がかかり、実装したら全然サンプルが合わないところでようやく気付いてまた考え直してということでひどかった。こんなのコンビネーション計算するだけなのに時間をかけてしまい、順位がめちゃくちゃ悪くて冷や汗が出始める。

 提出

E問題

 まず有向グラフだということに気づいていなくて時間がかかり、その後もその混乱を引きずって隣接にはコスト1で行けると思い込んだままよくわからない解法を考え続けていた。残り27分くらいのタイミングで一度落ち着こうと思って問題文を眺めなおすと頂点を拡張するいつものダイクストラということがわかってようやく解けた。これがすぐ見えないのは完全に練習不足。提出時点でE問題を解いている人の数がめちゃくちゃ多くて冷えていたけど、ノーペナだったおかげか意外と順位はひどいことにならなくて軽傷で済んだのは良かった。

 提出

F問題

 O(NK)のDPを書いてじっと睨んでいたが残り10分ちょいでは全然見えてこなくて終了。解説PDFを読んで、まぁそれはそうだと思ったけどこれを本番中に思いつける気がしない。実装も難しくて割った数でまとめる際にその数に何個なるかを事前計算しておかないと扱いきれない抽象度だった。難しい。

 提出

長時間学習の結果/選手権以降にやったことのまとめ

要約

 2週間弱かけて1Mステップの学習を行ったところレート2600程度になった。パラメータとWindows向けバイナリはGitHubで公開している。

背景

 第29回世界コンピュータ将棋選手権以降、一通り試したいことはやったのでここで一度長時間の学習を行った。選手権時からの改良点をまとめると以下のようになる。

 雑に見積もってレートは+770となる。選手権時点では技巧2(深さ2)に対して勝率71%、レートにして1946.5だったので、だいたいR2700程度になると予想した。

実験設定

 ランダムに初期化したパラメータから1Mステップの強化学習を行った。

学習

項目
バッチサイズ 128
学習率 0.015(固定)
オプティマイザ Momentum(0.9)
TD(\lambda)の\lambda 0.75
優先度付き経験再生の\alpha 2.0
引き分けとする手数 512
学習スレッドのスリープ時間 1ステップごとに1秒
リプレイバッファサイズ 2^{20}
1局面あたりの探索回数 800
C_{PUCT} 2.5
Residualブロック内のCNNのチャンネル数 64
Residualブロックの数 10

 学習に使用したマシンはGTX1080を2枚搭載したものであり、データ生成速度は33.8 pos / secであった。スリープ時間が1秒、バッチサイズが128なので、1ステップあたりに生成する量に対してバッチサイズが4倍ほどであり学習データの重複は多めだと思われる。

検証損失

 floodgateの2016年の棋譜からレート2800以上同士の対局のみを抽出し、そこからランダムにサンプリングした409600局面についてPolicyとValueの損失を計算した。Policy損失の計算では棋譜上で指された手を教師信号とし、Value損失の計算では最終結果を教師信号とした。

検証対局

 100Kステップごとに得られたパラメータを用いて深さを制限した技巧2(定跡オフ)とそれぞれ500局の対局を行った。検証対局で使用したマシンはRTX2080tiを1枚搭載したものであり、探索速度は初期局面で10K NPSほどになる。Miacis側の持ち時間は0.25秒とした。対局は256手で引き分けとし、引き分けは0.5勝0.5敗として勝率を計算した。

実験結果

 学習にかかった時間は約302時間(2週間弱)であった。

検証損失

f:id:tokumini:20190625132252p:plain

 予想できていたことだが、1Mステップでもまだ収束しきっていないように見える。以前実験した通りバッチサイズと学習速度はほぼ比例するため、バッチサイズ4096で700KステップのAlphaZeroと同等の学習をするには、バッチサイズ128にした場合22.4Mステップが必要になる。AlphaZeroとは手法やモデルの大きさが違うことやそもそもAlphaZeroも後半350Kステップはほぼレートが伸びていないことを考えれば、この半分から1/4程度で許してもらえないかと考えたいところだが、それにしても5Mステップくらいは回し続けないといけないかもしれない。学習率の減衰をどう入れるかも悩ましいところである。

検証対局

 100Kから500Kステップまでは深さ4~6, 500Kステップ以降は加えて深さ7とした技巧2と対局を行った。図中で示す技巧2のレートはhttp://www.uuunuuun.com/englishに記載されているものとなる。

f:id:tokumini:20190626114658p:plain

 損失推移同様、まだ収束しきっている様子ではない。小さいネットワークを使っているのでそこまで伸びないとは思うがもっと長時間学習させてみた方が良さそうだ。

 本来はどの深さ制限の技巧で測っても全く同じEloレーティングが得られることが理想なのだが、実際には相性の問題や計測誤差があるため完全には一致しない。特に深さ4に対しては500K時点で勝率が90%を超えているため、信用度の低い測定になっているかもしれない。

 平均値では1Mステップ時点でR2618.1となる。深さ4に対しての計測で高めに出ていることを割り引いて考えて、だいたい2600といったところだろうか。予想してた2700よりはやや低いが、かなり雑に見積もっていたことからすればむしろ驚くくらいの伸びではある。

 気になる点としては、700Kステップ時点で一度レートが落ちていることと、900Kステップ時点で深さ6に対してだけ相性が悪いことがある。対局を見ていたところ、やや指し手に偏りがあり同じような戦型ばかりになっているのではないかと感じた。先日山岡さんが指摘していたように、データ生成時にルート局面以外のノードについて探索情報を再利用していることが影響している可能性もある。

AtCoder Beginner Contest 131

結果

 E問題までの5完。

内容
順位 292nd / 5123
パフォーマンス 1869
レーティング 1861 → 1862 (+1)

A問題

 特になし。

 提出

B問題

 脳みそを使いたくなかったので問題文の通りまず総和を計算して各iに対して絶対値の差が小さくなるものと探索してそれを出力するということを愚直にやった。絶対値が一番小さいものを選ぶのが最適とかそういうことでできるのはそうだろうけどそこで時間かけるのとどっちが速く解けたかは微妙なところか。

 提出

C問題

 問題を細かく分解していく感じが楽しくて妙にコメントを丁寧に書いてしまった。閉区間で実装してしまったのが少し微妙だったか。

 提出

D問題

 リアルタイムシステムの講義でEarliest Deadline First(EDF)というやつをやったなぁというのを思い出しながら解いた。

 提出

E問題

 最初は全てのノードを一列に並べた状態からなんとかできないかとか考えていたけどどうにもならず。スター型のグラフが最大になるっぽいことに気づいて、そこから減らしていく方針が思いついてからはすぐだった。

 提出

F問題

 方針としては間違ってなかったと思う。最終的に点が置かれる位置の数を列挙して、そこから最初のN個を引く。ただ最終的に点が置かれる位置の数を列挙する部分が上手くできなかった。概ね共通するグループのXの数×Yの数で出すというところも間違ってはいなかったんだけど……。各yに属するxの集合を取って、そのxに属するyの集合の和を取るということで集合のマージテクを使う方針でやっていたがWAもTLEも出るので全然ダメだった。

 解説PDFを読んで普通にDFSするだけと把握してAC。言われてみればそれはそうなのに思いつかない不思議。

 提出

Learning Action Representations for Reinforcement Learningを読んだ際のメモ

出典

 International Conference on Machine Learning 2019に採択

読んだ理由

 前回に続いて行動の表現を学習する手法についてのものがICMLにあった。特に昨日の論文が行動ログから事前学習という形のものだったのに対して、より強化学習の学習ステップに明示的に組み込まれているようだったので読んでみた。

概要

 行動決定を(1)行動表現空間への方策計算(2)サンプリングされた表現から行動への復元 という2ステップに分ける手法を提案。行動空間が大きい場合に対する強化学習で性能が向上する。普通の方策勾配法に組み込むことができるので汎用的に適用できる。

詳細

 全体としての方策を\pi_o、表現部分への確率分布を示す方策を\pi_iとして、行動を次のように2段階で決定する。

f:id:tokumini:20190614185200p:plain

 式としては次のように行動決定する。

$$ E_t \sim \pi_i(\cdot|S_t), \qquad A_t = f(E_t) $$

\pi_iを固定した際のfの学習方法

 まず前提として二つの連続した状態が与えられた際の行動推定は、行動の表現を介して次のように表せる。

$$ P(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} P(A_t|E_t = e)P(E_t=e|S_t, S_{t+1}) \mathrm{d}e $$

 右辺の二つの要素をそれぞれ\hat{f},\hat{g}としてパラメータを持つ関数で近似することを考える。\hat{f}はそのまま表現から実際の行動への復号関数fの推定として推論時にも用いるが、\hat{g}\hat{f}を学習するためだけに用いるものとなる。推定値は次のようになる。(以下式番号は論文中のものと揃えた)

$$ \hat{P}(A_t | S_t, S_{t + 1}) = \int_{\varepsilon} \hat{f}(A_t|E_t = e)\hat{g}(E_t=e|S_t, S_{t+1}) \mathrm{d}e \tag{3} $$

 これらの式をカルバックライブラー情報量で評価する。

$$ D_{KL}\left(P(A_t | S_t, S_{t + 1}) || \hat{P}(A_t | S_t, S_{t + 1})\right) = -\ln \mathbb{E} \left[ \left(\frac{\hat{P}(A_t | S_t, S_{t + 1})}{P(A_t | S_t, S_{t + 1})} \right) \right] \tag{4} $$

 この式の最小化を考えると、分母は定数なので関係なくなる。結局得られた遷移の3つ組(S_t, A_t, S_{t + 1})について損失関数は次のようにすれば良い。

$$ \mathcal{L}(\hat{f}, \hat{g}) = -\mathbb{E}\left[ \ln\left(\hat{P}(A_t | S_t, S_{t + 1}) \right) \right] \tag{5} $$

 報酬は関係しないので遷移からそのまま教師あり学習を行うだけとなる。

 (付録D)実際には表現eについての積分にかかる計算量を抑えるため、積分を取り払って

$$ \hat{P}(A_t | S_t, S_{t + 1}) \approx \hat{f}\left(A_t | \hat{g}(S_t, S_{t+1}) \right) $$

として近似する(これはどの程度正当性があるのだろうか。かなり大胆な近似をしているように思える)。\hat{f}(a|\hat{g}(s, s'))

$$ \hat{f}(a|\hat{g}(s, s')) = \frac{\exp{\frac{z_a}{temp}}}{\sum_{a'} \exp{\frac{z_{a'}}{temp}}} , \qquad z_a = W_a^{\mathrm{T}} \hat{g}(s, s') \tag{22} $$

とする。tempは温度変数(はてなブログの数式モードではギリシャ文字tauが表示できなくて困った)。W \in \mathbb{R}^{d_e \times |\mathcal{A}|}は各列が各行動のd_e次元の表現となる行列。W_a^{\mathrm{T}}は行動aに対応する列を抜き出して転置を取ったベクトル。つまり\hat{g}が予測する表現と今までに学習した表現の内積になっている。

fを固定した際の\pi_iの学習方法

 単純に方策勾配法を用いて学習する。特に全体方策\pi_oではなく内部方策\pi_iに対するパフォーマンス関数の微分で方策勾配法を考えればよい。復号関数fが確定的な関数ならば $$ \frac{\partial J_o(\theta, f)}{\partial \theta} = \frac{J_i(\theta)}{\partial \theta} $$ となるためである(証明は付録B)。これによりf^{-1}を計算する必要はなく、内部方策\pi_iに対する状態価値関数v^{\pi_i}(s)を考えてパフォーマンス関数 $$J_i(\theta) = \sum_{s\in\mathcal{S}} d_{0}(s) v^{\pi_i}(s) $$ に対する微分を考えれば良くなる。(付録D)内部方策\pi_iとして実験ではガウス分布を仮定してその期待値を近似するようなニューラネットワークを学習させた。

同時学習

 以上の結果から次のようなアルゴリズムで学習を行えば同時に学習していくことができる。

f:id:tokumini:20190614171905p:plain

 1行目の部分では、最初にランダム方策による行動から行動表現部分だけを多少学習させる。

実験

迷路タスク

f:id:tokumini:20190614182615p:plain

 星がゴールの位置。n方向に独立なアクチュエータがあり、可能な行動としては全部で2^n通りになる。

実験結果

f:id:tokumini:20190614182650p:plain

 普通のActor-Criticと比較して、nが大きいほど提案手法を入れた場合に性能が伸びやすい。つまり行動が多い場合に有効。

得られた表現

f:id:tokumini:20190614183457p:plain

 左の図はデカルト座標における各行動の遷移先であり、右は表現空間での各行動の座標。左右で同じ行動には同じ色が与えられている。つまり右の図で近い色は近い場所に集まっていることから、同じような行動をまとめることができていると思われる。また特定の方向で最大限移動するような方策がそれぞれ縁にあって区別しやすいように表現が学習できている(?)。

現実世界の推薦システム

 ビデオチュートリアルの推薦とマルチメディア編集ソフトの推薦。ユーザの使用履歴・満足度からMDP環境を作り、そこにおける報酬を最大化するタスク。前者は1498個、後者は1843個の行動(選択肢)が存在。

f:id:tokumini:20190614183645p:plain

 提案手法を入れた方が性能が良く、学習も速い。

所感

  • 言われてみれば自然なやり方に思えるが、実際のところ近似が上手くいくのかどうかが怪しいと感じるところもないわけではない
  • 特に内部方策はガウス分布で近似されており、多次元空間の確率分布はモデル化が難しそうだがもう少し表現力が高そうなものを用いたい気もする
  • 自分の将棋プログラムでは9 \times 9 \times 27 = 2187種類の行動から選択するように実装しているため、だいたい同じくらいの行動の量で性能が上がるなら試してみる価値はありそう。AlphaZero形式の方策学習が方策勾配法とどのような関係にあるのかは理解できていないが、AlphaGoなどでは明示的に方策勾配法が使われていたので応用はできるはず