AtCoder Grand Contest 037

結果

順位   393rd / 2317
パフォーマンス   1841
レーティング  1885 → 1881(-4)

 800点のC問題を通せて喜んでいたけどレートは下がるのか。

 AtCoderをやっている上でmerom686氏のレートを超えるというのを一つ目標としてきていたのだけど、今回提出せず撤退もできたmerom686氏が最後C問題出してWAになってレート大暴落が発生しており、なんか超えてしまった。自分のレートも下がっているのでひどく微妙な感じだ。こういう事故っぽいのではなぁというのもあるし、そもそも黄色くなっていない時点で論外というのもそう。はい。漫然と黄色を目指します。

A - Dividing a String

 3文字以上の塊は出てこなさそうだなと直感で判断してDPをし始めた。初期化とか遷移での添字とかいろいろ手間取りつつWAも出しつつなんとか通したという感じでまったくスマートではない。

 提出

B - RGB Balls

 コンテスト中には解けなかった。A問題解いた直後に30分くらい考えてわからなかったので順位表の様子を見てC問題へ行った。C問題を解いた後戻ってきたけど方針すらさっぱり立たない感じで時間切れ。サンプルが見るからに掛け算をしてくださいという出力になっていることはわかったけどなにをどう数えつつ掛けていけば良いのかさっぱりわからなかった。今日解いてみたけど、解説PDFはなんだかよくわからなくて、とりあえずわりと貪欲っぽくやっていくとなんか数が合って通った。類問出されても解ける気がしない。

 提出

C - Numbers on a Circle

 後ろからやっていくということに気づいて、配列の中から最大値のインデックスを取り出すというところにやや悩んだ挙句セグメント木を持ち出してくるということをやった。冷静に考えればstd::priority_queueで十分なのに。まぁ将棋ソフトの方でセグメント木を使った最小位置の取得というのは書いていて、それをコピペするだけだったので時間の短縮にはなっていたかもしれない。

 B_i = A_iとなった場合に最大値として再び取り出すことがないようにセグメント木上では0にしておく変な実装になってしまい、初期化の部分でそれを忘れて2WAほど。綺麗な実装がよくわからなかった。

 提出

AtCoder Beginner Contest 137

結果

順位   462nd / 5218
パフォーマンス   1685
レーティング  1906 → 1885(-21)

 D問題までの4問しか解けなくてひえーって感じだったけど失敗に優しいAtCoderなので。

A - +-x

 素直なA問題でやりやすかった。

 提出

B - One Clue

 こういうの境界のあたりでバグらせそうで非常に怖い。

 提出

C - Green Bin

 各文字列について各26文字の出現回数を記録したstd::vectorstd::mapに詰めていく。こういうSTLSTLを突っ込むみたいなSTLを信じ切った解法だと内部的な振る舞い(メモリがどうなっているのかとか)がさっぱり想像できなくて不安だけどできるものはできる。

 提出

D - Summer Vacation

  M - i日目には遅延が i日以内のものから最大のものを選びたくなった。報酬の遅延日数で昇順ソートして、std::priority_queueに詰めながらやっていくと通る。ここまでは結構順調に解けていたのだが……。

 提出

E - Coins Respawn

 85分ずっとこの問題に取り組んで結局解けず。原因は簡単で、ベルマンフォード法とワーシャルフロイド法が頭の中で混じってしまい、ベルマンフォード法は O(|V|^3)だからダメだよなぁと早々に切ってしまったから。ダイクストラを適当にいじってなんとかする方針でずっと考えてハマり続ける展開になってしまってはもうダメ。

 こういう勘違いを、コンテスト中の振る舞いを変えることで回避することができるのかよくわからない。頭の中だけで切らず文章として残そうとすれば気づけただろうか。しかし「メモを丁寧に取ろう」みたいな心がけに頼ってなんとかしようとするのはどうせ数回でまたもとに戻ってしまうと経験上わかっているので良くない。メモを取るのが嫌な理由として紙にペンで文字を書くのが遅いという点はあるし、パソコンで書くのはありかもしれない。グラフとか図とかは書きづらいので思考部分のみにはなりそうだけど。

 あとはもっとWeb検索を用いたほうがいい。今回詰まっている間は一回も検索してなくて、コンテスト終わった後にふと「負の閉路」で調べてベルマンフォード法をちらっと見ただけであーこれは……という感じになったので。基本的に自分の頭で考えてなんとかなることはそんなに多くない。

 まぁコンテスト中の振る舞いというよりは、どちらかというとアルゴリズムの知識があやふやだった、訓練不足だったというところが大きいとは思う。あまり競技プログラミングをがっつりやっていくという気分ではないのでこうやってコンテストでやらかして覚えるということになっていくのだろうけど。

 提出

F - Polynomial Construction

 今日1時間ほど考えてみたけどさっぱりわからなくて解説を見てAC。根本的に考察の方針として「 b_0 O(p)で決めて、次に b_1 O(p)で決めて……」みたいな考え方ばかりを探っていたのでこういうなんかひねり出すみたい解法にはさっぱり近づけない。難しい。

 提出

AtCoder Beginner Contest 136

結果

順位   315th / 5109
パフォーマンス   1843
レーティング  1913 → 1906(-7)

A - Transfer

 一度間違えてサンプル3の入力を提出欄にコピペして出してしまったがCEになったのでペナルティは付かなかった。あぶねー。

 提出

B - Uneven Numbers

 整数を Nまでループしてstd::stringに変換してサイズを偶奇判定。std::to_stringがどんな実装になっているかは知らないけどまぁ桁数くらいの計算量だろうしそれなら間に合うはずという判断。最大ケースもサンプルにあったし。

 提出

C - Build Stairs

 右から見ていって左の方が高ければ一つ削る。まだダメならNoだし良ければ次へとやっていく。無駄な分岐も作ってしまったしあまり綺麗なコードになってないな。

 提出

D - Gathering Children

 サンプルを手で考えているとR...RL...LとなっているRLの部分に最大1の差で集まるんだなということがわかるので、あとは偶奇を冷静に考えていると解けている。解説PDFのダブリングによる解法は典型っぽいので覚えておいた方が良さそうだなぁ。

 提出

E - Max GCD

 総和が不変ということにはすぐ目が向くが、その先の考察が進んでいかない。というのも O(N \sqrt{N \max{A}})が間に合わないと勘違いしていて、しばらくして Nは小さいからこれでいけるということに気づいて約数列挙→最低操作回数計算という流れで解けた。 O(N\log N \sqrt{N \max{A}})になるのでやや不安だったけどこれが余裕なんだな。

 途中でちらっと見たとき解いている人が少なかったので難しいのかと思ったけど解けてみたらあまりそうでもなく、ACした後に順位表みたら順位がひどかった。最初のはF問題の欄を見間違えていたのかな。

 提出

F - Enclosed Points

 残り30分くらいしかない状況で入ったのでやや諦めつつの考察だったけど、しばらくして「ある点が何回囲われるか」という視点で考えれば解けそうだと気づく。 x,yの範囲が広いので座標圧縮して、 xでソートしてセグメント木で yの位置を取りつつ、重複して数えるのを除いて……というのを10分程度で実装できるわけもなく終了。

 後日解いた感じでもあと30分は必要そうだった。実行時間が1336msecもかかっているし、コードも140行を超えていてもっと簡単に書けそうな気はするんだけどよくわからない。

 仕組みが変わってからのABCは特に時間が足りないことが多いしライブラリの重要性が増していると思う。座標圧縮くらいさっとやれなければな。

 提出

Temporal Difference Variational Auto-Encoderを読んだ際のメモ

出典

 International Conference on Learning Representations 2019に採択。

所感

 長くなってしまったので最初に所感を。

 初めて読んだときはなんだかよくわからず挫折してしまったけど、4.2節あたりの気持ちをちゃんと読んでみると多少わかってきた。詳しい式変形はよくわからないままだがTD誤差と言いたくなるのはそうかもしれない。

 確かにジャンプ予測は実現できたら面白いものの一つだと思う。しかし、Predictronとかもそうなのだけど、この手の環境モデルは時系列データの遷移を予測するだけで自分の行動を考慮できていないので、実践的には使い勝手が悪そう。結論の節で「プランニングへの応用を目指している」と書いてあるし当然こういった問題を認識していないわけはないが。

 各タイムステップで行動選択が可能であると考えると、単純に状態系列に行動も含めれば上手くいくわけではないだろう。個人的には行動自体の表現を考えて抽象化することで漫然とした(長いタイムステップの)行動を考えられるようになるのではないかと考えているが。

 将棋的に言うと「金銀を盛り上げていけば模様がよくなりそう」とか「飛車を振って美濃囲いにすれば勝ち」とかそういう方針的なものを……ってそれはむしろ階層的強化学習とかの分野なのかもしれない。どちらかというと「▲2四歩△同歩▲同飛△2三歩▲2九飛」を一気に飛ばせるとかそういう話か。しかしポリシーが偏っていれば1手ごとの展開でもそこまで計算時間のロスは大きくないだろうし、やはり観測が完全なドメインではあまり活きない話なのかもしれないとも思ったり。

概要

 以下の3つの特徴を持つ環境モデルとしてTD-VAEを提案

  • 状態の抽象表現を獲得
  • 状態の不確実性を表現する信念を形勢
  • 複数ステップ一気にジャンプする遷移を予測可能

1 Introduction

  • 強化学習における部分観測環境
    • 不確実性の表現が可能である必要性
    • 記憶を持つエージェントならモデルフリー手法でも可能?
      • 報酬のような教師信号では不確実性を学習するのは難しい/遅い可能性
  • 望ましい性質
    • データの抽象的な状態表現を学習し、観測レベルだけでなく状態レベルで予測
    • ある時点までの観測値を全て考慮した符号(信念状態)を学習
    • 複数ステップを一気にジャンプする予測が可能
  • これらの要求を満たすものとしてTD-VAEを提案

2 モデルに要求されること

2.1 隠れ状態空間の構築

自己回帰モデル
  • チェインルールを用いたモデル化{}

$$ \log p(x_1, \dots, x_T) = \sum_t \log p(x_t | x_1, \dots, x_{t - 1}) $$

  • RNNを用いると隠れ状態 h_t = f(h_{t - 1}, x_t)でデータに文脈を付与して予測を行うことになる
  • 観測空間でそのまま予測をするのでデータの圧縮した表現を学習できない
状態空間モデル
  • 潜在変数を用いて状態間の確率的遷移をモデル化

  • \boldsymbol{z} = (z_1, \dots, z_{T})を状態系列、\boldsymbol{x} = (x_1, \dots, x_T)を観測系列としたとき同時確率を次のようにモデル化

$$ p(\boldsymbol{x}, \boldsymbol{z}) = \prod_t p(z_t|z_{t-1})p(x_t|z_t)$$

  • 事後分布 q(\boldsymbol{z}|\boldsymbol{x})による下限によって学習(VAEと同様)
  • \phi_tを、\boldsymbol{x} = (x_1, \dots, x_T)をフィルタリング、平滑化する関数とすると事後分布は自己回帰的に分解可能(これ自明? よくわからなかった)

$$ q(\boldsymbol{z}|\boldsymbol{x}) = \prod_t q(z_t | z_{t - 1}, \phi_t(\boldsymbol{x})) $$

  • 変分下限(よくわからん。VAEの式変形を調べないとダメそう)

$$ \log p(\boldsymbol{x}) \ge \mathbb{E}_{\boldsymbol{z}\sim q(\boldsymbol{z}|\boldsymbol{x})} \left[ \sum_t \log p(x_t|z_t) + \log p(z_t | z_{t-1}) - \log q(z_t | z_{t-1}, \phi_t(\boldsymbol{x})) \right] $$

2.2 信念状態のオンライン生成

  • 過去の系列は十分な表現力を持つ変数 b_t = b_t(x_1, \dots, x_t)によって近似できるとする

$$ p(x_{t+1}, \dots, x_{T}|x_1, \dots, x_t) \approx p(x_{t+1}, \dots, x_{T}|b_t ) $$

  • RNNだと隠れ状態 h_t b_tに相当

  • 状態空間モデルでは潜在変数 z_tを媒介

$$ p(x_{t+1}, \dots, x_{T}|x_1, \dots, x_t) = \int p(z_t|x_1, \dots, x_t) p(x_{t+1}, \dots, x_{T}|z_t) dz_t $$

  • 上の式と同様に p(z_t|x_1, \dots, x_t) \approx p(z_t|b_t)と近似できるとする

  • 古典的な状態空間モデルではこのような b_tは考えられてこなかった

    • 事後分布を自己回帰的に計算する q(\boldsymbol{z}|\boldsymbol{x}) = \prod_t  q(z_t | z_{t-1}, \boldsymbol{x})と、 z_tの周辺事後分布に関するいくらかの不確実性がサンプル z_{t-1}にリークする可能性がある(とは?)
    • サンプルは確率的なので、 z_tに関する全ての情報を(x_1, \dots, x_t)から得るために、 z_{t-1}を再サンプリングする必要がり、順々に z_{t-2}から z_1まで再サンプリングする必要がある
    • (この2点が何を言わんとしているのかあまりよくわからなかった。なんとなく b_tを考えた方が良さそうという気分は読み取れたが……)

3 系列TD-VAEのための信念状態ベースELBO

  • 状態空間モデル p(\boldsymbol{x}, \boldsymbol{z}) = \prod_t p(z_t|z_{t-1})p(x_t|z_t)を考える
  • 目標はデータの対数尤度\log p(\boldsymbol{x})最大化
    • 自己回帰的に分解して\log p(\boldsymbol{x}) = \sum_t \log p(x_t|x_{\lt t})
    • 所与の tに対して、条件付き尤度 p(x_t| x_{\lt t}) z_{t-1} z_{t}で条件付け
      • 尤度の変分下限は

$$ p(x_t| x_{\le t}) \ge \mathbb{E}_{(z_{t-1}, z_t) \sim q((z_{t-1}, z_t)|x_{\lt t})} \left[ \log p(x_t|z_{t-1}, z_t, x_{\lt t}) + \log p(z_{t-1}, z_t | x_{\lt t}) - \log q(z_{t-1}, z_t | x_{\le t}) \right] $$

  • ここで
    • 状態空間モデルにはマルコフ性が仮定されるので p(x_t | z_{t-1}, z_{t}, x_{\lt t}) = p(x_t|z_t)かつ p(z_{t-1}, z_t|x_{\lt t}) = p(z_{t-1}|x_{\lt t})p(z_t | z_{t-1})
    •  q(z_{t-1}, z_t | x_{\le x})を自己回帰的に分解して q(z_{t-1}, z_t | x_{\le x}) = q(z_t|x_{\le t})q(z_{t-1}|z_t, x_{\le t})

$$ \therefore p(x_t| x_{\le t}) \ge \mathbb{E}_{(z_{t-1}, z_t) \sim q((z_{t-1}, z_t)|x_{\lt t})} \left[ \log p(x_t|z_t) + \log p(z_{t-1} | x_{\lt t}) + \log p(z_t|z_{t-1}) - \log q(z_t|x_{\le t}) - q(z_{t-1}|z_t, x_{\le t}) \right] $$

  •  p(z_{t-1}|x_{\le t - 1}) q(z_t | x_{\le t})は時刻が異なるだけ
    •  b_t = f(b_{t-1}|x_t) z_tに対する信念状態の符号として p_B (z|b)で近似
    • 同様に z_{t-1}の平滑化事後分布を q(z_{t-1}| z_t, b_{t-1}, b_t)として表現
  • 最終的に損失関数は

$$ -\mathcal{L} = \mathbb{E}_{z_t \sim p_B(z_t|b_t), z_{t-1}\sim q(z_{t-1}|z_t, b_t, b_{t-1})} \left[ \log p(x_t|z_t) + \log p_B(z_{t-1}|b_{t-1}) + \log p(z_t|z_{t-1}) - \log p_B(z_t|b_t) - q(z_{t-1}|z_t, b_{t-1}, b_t) \right] $$

4 TD-VAEと飛躍状態モデリング

4.1 TD-VAEモデル

  • 離れた2つのタイムステップに対応するために3章で示したものを改良
  • モデルの全体図

f:id:tokumini:20190803122158p:plain

  • 損失関数は前章のtt_2に、t-1t_1に置き換わって、

$$ -\mathcal{L}_{t_1, t_2} = \mathbb{E}_{ (z_{t_1}, z_{t_2}) \sim q(z_{t_1}, z_{t_2} | b_{t_1}, b_{t_2}) } \left[ \log p(x_{t_2}|z_{t_2}) + \log p_B(z_{t_1}|b_{t_1}) + \log p(z_{t_2}|z_{t_1}) - \log p_B(z_{t_2}|b_{t_2}) - q(z_{t_1}|z_{t_2}, b_{t_1}, b_{t_2}) \right] $$

4.2 TD-VAEの直感的背景

 時間 t_1までに得た全ての情報から将来の時刻 t_2の状態を予測したいとする。時間 t_1までの観測情報は b_{t_1}に圧縮されている。また観測 x_tの背後にはマルコフ性を満たす隠れ変数 z_tがあるとする。

 今時刻が t_2であるようなエージェントを考える。このエージェントは信念モデル p_B(z_{t_2}|b_{t_2})からサンプリングすることによって隠れ状態を推測することができる。状態 z_{t_2}は観測値 x_{t_2}を伴うはずなので、まず p(x_{t_2}|z_{t_2})を最大化したくなる(損失関数第1項・再構成誤差)。そして b_{t_2}を通じて x_{t_2}の情報がリークしすぎないように変分ボトルネックペナルティとして - \log p(z_{t_2}|b_{t_2})を最大化したくなる(損失関数第4項・気持ちはわかる気がするが、この定式化が正しいのかはわからない。意味合い的には尖りすぎないようにする効果が出る? 式変形で出てきた者に対する解釈ということなのだろうか。あと論文中では第2項と書いてあるけど第4項だと思う)。

 そして t_2における状態が t_1における状態から予測できて欲しい。まず t_1における状態がなんであったのかを予測する必要がある。これは単に b_{t_1}を使って求めるよりも x_{t_1 + 1}, \dots, x_{t_2}の情報を使った方が良い予測ができそう。よって q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})という平滑化分布を考えてこれにより z_{t_1}を予測する。この z_{t_1}を用いてジャンプモデル p(z_{t_2} | z_{t_1})を最大化する(損失第3項)。

 最後に平滑化分布と b_1だけで求めた分布の距離を最小化する(これがTD誤差っぽい部分だと思う)。多分平滑化分布の方が良い予測ができるはずで、それを b_1だけから求められるようになると嬉しいので。これは p_B(z_1|b_1) q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})のKL距離を考えて展開すると \log p_B(z_1|b_1) - \log q(z_{t_1} | z_{t_2}, b_{t_1}, b_{t_2})(第2項と第5項)が出てきそう(だけど正確にはよくわからない。 p_B(z_1|b_1) z_1について積分するはずだけどそれは上手く消えるのかな)。

 これらの損失の和を考えると上のような式になっている。

4.3 TD学習との関係

 強化学習だと状態について収益の分布を考える。多くの場合、状態価値や行動価値として収益の期待値だけを近似する。場合によっては収益の分布そのものを近似しようとすることもある(Categorical DQNなど)。

 TD-VAEでは収益ではなくて状態の分布 p_B(z_t|b_t)を近似することになる。 t_1時点における状態を t_2における予測値でブートストラップ的に学習するので時間差分(Temporal Difference)的な学習である。

5 実験

5.1 部分観測ミニパックマン

  • 実験内容:自分自身の周囲 5 \times 5しか見えないパックマン(の表示を簡単にしたやつ)において観測系列をモデリング
  • 比較手法
    • フィルタリングモデル:  q(\boldsymbol{z} | \boldsymbol{x}) = \prod_t q(z_t | z_{t-1}, b_t), \mathrm{where}\, b_t = \mathrm{RNN}(b_{t-1}, x_t)
    • 平均場モデル:  q(\boldsymbol{z} | \boldsymbol{x}) = \prod_t q(z_t | b_t), \mathrm{where}\, b_t = \mathrm{RNN}(b_{t-1}, x_t)
    • TD-VAE(ジャンプなしの連続モデル)
  • 評価指標
    • ELBO(低いほど良い)
    • テストセットにおける負の尤度(低いほど良い)
  • 結果

f:id:tokumini:20190802143455p:plain

  • 平均場モデルが最も性能が悪く、つまりただ単に b_tを信念状態として扱うだけでは性能が悪化することがわかる。TD-VAEによる工夫を導入することで b_tを正しく信念状態として扱うことができるようになる。

5.2 ムービングMNIST

  • 実験目的:ジャンプ予測が可能であることの実証
  • 実験内容:横移動するMNISTの画像を予測
  • 手法時刻 tからロールアウトした結果を出力
    1. 時刻 tまでの観測から b_tを計算
    2.  z_t p_B(z_t | b_t)からサンプリング
    3.  z = z_tから始めて z \leftarrow z' \sim p(z' | z)によって zの系列を取得
    4.  p(x|z)によって zの系列から xを復元
  • 結果

f:id:tokumini:20190802145208p:plain

5.3 ノイズ付き調和振動子

  • 実験目的:観測の情報が少ない場合でも状態予測が可能であることの実証
  • 実験概要:ノイズの多い
  • 階層的TD-VAEを利用
    • 集約部分で積んだLSTMを使う?
  • 結果

f:id:tokumini:20190802145356p:plain

5.4 DeepMind Labでの実験

  • 実験目的:より複雑なドメインでの性能検証
  • 実験概要:DeepMind Lab環境において画像のジャンプ予測を実行
  • 各モジュールにCNNを用いたモデル(Figure 8)を使用
  • 実験1:最初に3つの z_1, z_2, z_3をサンプリングし、これらとこれらからジャンプした後の潜在変数を復元

f:id:tokumini:20190803112200p:plain

  • 直接復元では z_1, z_2, z_3はどれも同じように見えるが、遷移した後の状態は異なる

    • 見かけの観測の背後にある状態の違いを認識できている
  • 実験2:ロールアウトの実験

f:id:tokumini:20190803112617p:plain

  • 複数ステップのジャンプ予測を行っても回転や前進の遷移を上手く捉えられている

AtCoder Beginner Contest 135

結果

ユーザ名 tokumini
コンテスト名  AtCoder Beginner Contest 135
順位  327th / 4583
パフォーマンス   1795
レーティング  1925 → 1913 (-12)

 難しかった。

A問題

 見た目が難しくてびびった。

 提出

B問題

 脳みそを使わない力のこもった三重ループを投げつけた。

 提出

C問題

 証明とかよくわからないけど貪欲にやっていけばできるっしょ! というノリ。最大流で考えるのかぁ。

 提出

D問題

 桁DPっぽい雰囲気も感じたけどその方針にはあまり深入りせず考えていたらDPっぽい遷移が見えたので実装し始める。しかしいつも通りちゃんと詰めてはいないので書いてからサンプル合わないし遷移の式がよくわからんという感じになって二度手間になるやつ。

 意識はしていなかったけどDP配列を2つ分しか用意しない省メモリの実装になっていた。普通に「dp[i][j] := 先頭 i 文字として考えられるもののうち,13 で割ったあまりが j であるものの数」とした方が混乱せずに済むのでそうしていれば良かったのに。初期化のところも汚くてひどい実装になってしまった。

 提出

E問題

 なにこれ難しすぎる。X,Yが小さくて回り道しなければいけないサンプル1と、貪欲に近づいてから最後調整するだけでは最適にならないサンプル3のコンビネーションが強くてなにもわからなかった。マンハッタン距離なので45度回転みたいなご利益もわかっていない念仏を唱えてみたりもしたけど別になにも起こらず。

 解説PDFを見てもはぁそうですかという感じで実装に数時間かかった。個人的には行き方のパターンA, Bで分類するよりもX + Y \lt Kかどうかで分類したほうがわかりやすかった。

  X \ge Yとするように変換し忘れていたり負の数の剰余を取っていたりとバグらせまくってひどい有様に。自分の提出ページが2ページまでいってしまった。きつかった。

 提出

F問題

 コンテスト中は開きもしなかった。順位表も見ていないのでどのくらい解かれているのかも知らないけど、もしF問題が簡単めでみんなそっち解いているとかだったらパフォーマンスがひどいことになっていただろうな。別に簡単ではなかったようで良かった。

 30分くらい考えてみたけど全然わからなくて解説を見てAC。Zアルゴリズムで検索できるというのも知らなかったしグラフに落としてからもなんだか芋臭い実装しかできなくてしっくりこない感じがある。難しい。

 提出

価値のソフトマックス分布を教師としたAlphaZero学習

要約

 価値のソフトマックス分布を行動選択および教師分布として利用することで学習が2倍から3倍程度速くなった。

背景

 前回、生成している棋譜を分析したところ、評価値を大きく損ねる悪い手が多く選ばれすぎていると感じられた。この原因として探索回数をもとにした分布によって行動選択をしていることが考えられるため、代わりに価値にソフトマックス関数を適用したものを用いるように変更して実験を行った。

用語の定義

 「ソフトマックス分布」で検索してもあまり用例が出てこないので適切ではないのかもしれないが、とりあえずこの記事では実数ベクトルに対してソフトマックス関数を適用したものをソフトマックス分布と呼ぶことにする。ここでソフトマックス関数には温度tというパラメータがあるものとして、ベクトル\boldsymbol{Q}に対応するソフトマックス関数適用後のi番目の要素の確率p_i

$$ p_i = \frac{\exp(Q_i / t)}{\sum_j \exp(Q_j / t)} \tag{1} $$

と定義する。tは大きくすればするほどQ_iの値によらずどれも等確率で選ばれるようになっていき、逆にtを小さくしていくとQ_iの大小関係がより強調されるようになる。

実験設定

 AlphaZero式の強化学習を行った。細かい設定はこの記事を参照のこと。

 各局面で800回の探索を行った後、式(1)のように価値のソフトマックス分布を計算して行動選択分布や教師分布として用いた。価値は[-1,1]の値をとり、温度はt = 0.01とした。

 次の3パターンについて比較を行った。

名前 行動選択分布 Policy教師分布
従来 探索回数に比例した分布 探索回数に比例した分布
選択のみ 価値のソフトマックス分布 探索回数に比例した分布
選択/教師 価値のソフトマックス分布 価値のソフトマックス分布

 (注)探索回数に比例した分布とは各行動についての探索回数を探索回数の総和(今回の場合だと800)で割ったものである。

$$ p_i = \frac{N(s, a_i)}{\sum_j N(s, a_j)} $$

 従来手法の結果としては新規に実験を行ったわけではなく前回得られた結果をそのまま用いた。

実験結果

  • floodgateの棋譜に対する損失

f:id:tokumini:20190726150627p:plainf:id:tokumini:20190726150633p:plain
左:Policy損失 右:Value損失

 価値のソフトマックス分布を使う手法はまたそこまで学習を回せていないが、同じステップ時点の従来手法よりも良い性能になっていることがわかる。特に「選択/教師」では従来手法で2Mステップ回した時点の結果よりもすでに良い結果となっている。

  • Gikou2(深さ8)と1手0.25秒で500局対局した結果から推定されるEloレート

f:id:tokumini:20190726164312p:plain

 実際の棋力としても「選択/教師」が同ステップ時点での比較では最も良い性能となっている。学習途中なので最高到達点が上がっているかはまだ不明だが、少なくともここまでの段階で学習が2~3倍は高速になっている。

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

 学習ステップ数や棋譜を保存する間隔等が違うので公平な比較にはなっていないが、参考程度に眺めると一応傾向は見られた。

 まず手数は次のようになった。

手法 平均 中央値 最大値 最小値
従来 75.7 74 317 14
選択のみ 110.6 107 512 25
選択/教師 107.3 104 512 32

 全体的に手数が伸びており、512手に到達したことによる引き分けもいくらか見られた。一般的に強いソフト同士の対局の方が手数は長くなりやすいと言われている。

 もちろん「強い⇒手数が伸びる」が成り立っていても「手数が伸びている⇒強い(良い棋譜を生成している)」とは言えないが、無理やり手数を伸ばさせる工夫を他に入れたわけでもないので傍証にはなっているのではないかと感じる。

 別のデータとして、1手進んだ局面での探索結果と現局面での探索結果の差の絶対値の統計を調べると次のようになっている。

f:id:tokumini:20190726150812p:plain

 探索回数に比例した分布で行動選択をやめることで評価値が大きく動くことが少なくなったことがわかる。これも根拠はない話だが、基本的にはあまり大きな変動がない方が良い棋譜なのではないかと思われる。

所感

 個人的な感覚では、将棋は可能な指し手の集合において悪手の割合が高いゲームであり、さらに「何度か探索した結果悪手だと判明する」頻度が高いのではないかと感じる。そのような場合に探索回数に比例した分布で行動選択をすると価値を大きく損ねる手が多く選ばれすぎるのではないか。これはゲームに依存する性質の可能性はあり、たとえば囲碁で価値のソフトマックス分布を使ってもあまり性能は伸びないかもしれない。

 またもとから30手を超えた場合には探索回数最大の行動を選択するようにしているならこの変更による恩恵は少ないかもしれない。個人的にはできるだけ恣意的な切り替えは避けたいのでこれで同じ結果が得られるならこちらで良いのかなと感じる。

 この変更に伴うパラメータの調整を考えると、価値のソフトマックス分布を使う方法では方策に対する依存性がやや弱まると思われるのでディリクレノイズが不要になったりしないだろうか。悪い手を指さないことと、いろんな指し手を試してみることのバランスを上手く調整することが学習の高速化で重要な点に思える。

余談

 Eloレートを計算する際の対局においても、同じ対局が何度も行われないように30手までは探索回数を正規化した分布に従って指し手を選択している。対局を見ていると30手までで大きく形勢を損ねていることもあり、価値のソフトマックス分布に修正すると見た目のレートはやや改善する可能性もあると感じた。本質的な改善ではないのであまり気も進まないが……。

AtCoder Grand Contest 036

結果

tokuminiさんのAtCoder Grand Contest 036での成績:254位
パフォーマンス:2080相当
レーティング:1906→1925 (+19) :)
Highestを更新しました!

 B問題を自分としては素早く解けたがC問題に歯が立たなくて座っているだけの時間が長かった。

A問題

 一つを原点に置いて良いことに気づかず、長方形から3つの三角形を引くことを考えて時間がかかった。

f:id:tokumini:20190722150522j:plain

 いやこれだって左右反転してX軸方向にずらせば一つは原点になるんだが……。気づかないときは気づかない。

 立式したら引き算が出る影響でSの大きさでも場合分けしまくるひどいコードになってしまったし考察の方針が悪すぎた。直接公式が思い出せずとも外積で計算できるってことは知っているんだから一つは原点に置いて良いというのは当たり前に近いなぁ。

 提出

B問題

 サンプルが多めなので異常なひらめき系ではないのかなとかメタ読みを挟みつつサンプルを手で解いていたところ、同じ数字が出るところまでで消えるからその次へ辺を張って……

f:id:tokumini:20190722150749j:plain

という感じで上図が出て周期性がありそうだなと実装開始。考察を詰めきらずに実装を始める無謀さは人よりありそうだと思っていて、今回はそれが良い方へ作用したか。本番でのコードのわりにはそこまで見通し悪くないような気がするしWAも出さなかったのでなんとか。

 提出

C問題

 なんか図形的に格子点の一部を除外する感じかなぁと考えていたが、普通に必要十分条件を出して数え上げる問題だったのか。しかし解説PDFを読む限り、条件を出せてもそれを数え上げる方法をひねり出すのも難しそうだし、これは難しい。

 ほぼ解説通りのコードで通したけど、2で割った余りを出すつもりが1で割った余りを計算していてWAを出しまくりきつかった。サンプルにMが奇数の場合がないという罠。

 提出

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}が小さすぎるということなのだろうか。根拠のない勘としては、もう少しなだらかに指し手の割合が変化していった方が良いのではないかと感じられる。リプレイバッファが小さすぎて同じようなデータばかり学習している可能性もあるかもしれない。

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