バッチサイズと性能の関係

コンピュータ将棋

前書き

　AlphaZeroが4096という大きなバッチサイズで学習しているのに対して、Miacisは64という小さいバッチサイズでの学習を行っている。AlphaZeroに比べて使える計算資源が少ないためデータの生成速度が小さく、バッチサイズが大きいと同じデータを何度も学習することになってしまい学習が上手く進まないのではないかと予想しているからである。今回はバッチサイズの違いによる性能の変化を実験により確かめてみた。

実験

　バッチサイズと学習率以外の条件は全て揃えて、カテゴリカル分布を出力するモデルについて200kステップの学習を行った。学習率はバッチサイズが4096のとき0.2(AlphaZeroの設定)、64のとき0.01とした。これは以前の実験から良いと考えられた値である。記事内の「バッチサイズに比例させるのが良い」という説から計算できる値0.2 \times \frac{64}{4096} = 0.003125よりは大きい値で設定している。その他パラメータ、実験設定も先の記事に準ずる。

　実験結果を次の表に示す。

バッチサイズ Policy損失 Value損失 技巧2(深さ1)に対する勝率 総学習時間 生成局数
4096 3.81 0.829 12% 62.4時間 125,600
64 3.01 0.781 63% 86.6時間 173,400

　バッチサイズが大きいと損失が大きいままになっており、実際に対局を行っても性能は悪化していることがわかる。バッチサイズを大きくすると学習に時間がかかるため、その間にActorが動く時間も増え、全体として生成される局数自体は増えている。それにも関わらず性能が悪化していることから、バッチサイズを大きくすることが悪影響を及ぼしていると考えられる。

今後の展望

リプレイバッファサイズとの関係

　本来はバッチサイズを大きくした分、リプレイバッファのサイズも大きくしなければならないのかもしれない。メモリ量の問題もあるためバッチサイズに比例するだけ大きくできるわけではないが、検証してみるべき要素ではあると思う。

　リプレイバッファサイズはバッチサイズとの関係を抜きにしても様々な検証をする価値があるパラメータである。Oracle Developersの記事では徐々に大きくしていく方式が取られており、そのような工夫も一考の余地がある。

小さいバッチサイズでの学習

　バッチサイズを64よりももっと小さくすることで小規模な計算資源しかない環境でも良い学習ができる可能性がある。その際に問題になるのはニューラルネットワーク内部で使われているバッチ正則化であり、バッチ正則化はバッチサイズが小さくなると性能が悪化することが知られている。それを改善する手法としてBatch Renormalization(日本語解説スライド)やWeight Standardization

という手法がある。これらの手法を採用することでバッチサイズを小さくしつつ上手く学習を進めることができるかもしれない。

【WCSC29】個人的に興味を惹かれたアピール文書集

コンピュータ将棋

　すでにuuunuuun氏が書かかれた全チームの簡単なまとめや、やねさんによる見どころ紹介がありますが、ここでは個人的に面白そうだなと思ったものについて妄想レベルの私見を交えながら触れていきたいと思います。自分がディープラーニング系のソフトを開発しているのもあってそちらに偏っているかもしれませんがご了承ください。

たこっと

　新しい特徴量を考えているということで面白そうです。ニューラルネットワークを利用しつつのものでありながらKKPARと名付けられているのでNNUEに近い感じではあるんでしょうか。

　あとは最適化手法としてAdaBoundを実装するとありますね。実際Optimizerの違いによる性能の差ってどの程度のもんなのかなぁと多少疑わしい気持ちで見ている面もあるわけですが、上手くいったら面白いなとは思います。

elmo

　ReLUを使うニューラルネットワークならなんでもHeの初期化で大丈夫だと勝手に思っていましたが、NNUEに初期化の問題があるとは知りませんでした。バイアスを0ではなく小さい正の値にするとかで解決する問題でもないんですかね。NNUE型のソフトには一切触ったことがないのでこの辺の挙動がよくわからないというのが正直なところです。

　兄弟局面の比較から評価値をいじるのは探索との兼ね合いという面が強くなっており、強化学習の枠組みに上手く混ぜていけるのかなぁというのが少し迷っているところです。まぁそもそも評価値を状態価値として考える(強化学習の枠組みで考える)ことにどこまで必然性があるのかも微妙なのかもしれません。

　NNUEへのCNN取り込みについては特に詳細が書かれていないので全然見当違いの理解をしているかもしれませんが、特徴量の入れ方、結合の組み方などを工夫すればそのようなことができるかもしれない？ と少し思いました。

習甦

　評価値推移をフィードバックして推定された勝率の割引報酬を考える強化学習とのことですが、個人的には将棋の手数(せいぜい300手程度)で割引率を考える(1未満にする)必要があるのかどうかは疑問です。特に「絶対に勝ちだけど手数自体はかかる」ような局面に対して手数による割引をかけると不当に低い報酬と考えてしまうのではないかと心配しているのですが、現実的にはそういう局面は少ないし別にどうでもいいという可能性はありそうです。あるいは評価値が一定以下になった場合に投了を行うと問題ないのかもしれません。

dlshogi

　学習データ生成時の詰み探索の処理とかそういう細かい部分で完成度が高いという印象です。Pollicyの学習もREINFORCEの方が良いというのはそうなのかもしれません。

　ミニバッチサイズが64~1024で徐々に増やすというのは、学習率を上げる代わりにミニバッチサイズを上げた方が良いという論文を意識されてのことなんでしょうかね。学習率の方も下げてはいるようですが。

　dlshogiは一致率を指標としていることが多いように思えますが、損失よりこっちの方が良い指標なんでしょうか。自己対局による検証はコストがかかるのでこれで済むなら大きいのですが。

ねね将棋

　フレームワークとしてCNTKを使っているようで、僕はPyTorchのC++APIを使っているのですが結構苦労が多く、CNTKが安定しているならその方がいいのかもしれません。そもそもC++でネットワーク部分を書くことに拘る意味があるのかも怪しいところですが。本番でp3.16xlargeを使うということはtensorコアも有効活用できているということなんでしょうかね。

　評価値部分が2チャネルというのは少し不思議です。評価値と勝敗を別に予測する効果がどの程度あるものかすぐにはわかりませんが、学習を安定させられる効果があったりするのかなと思っています。手元での実験でもPolicyに比べてValueの学習は上手く進まないことが多いと感じていて、AlphaZeroを改良するならValue側を多少工夫するのが手っ取り早いかなという印象です。

芝浦将棋 Softmax

　モンテカルロ・ソフトマックス探索を採用しているという点が面白いと思います。細かい定義はもちろん違うんですが、ニューラルネットワークでPolicyを計算するとき、だいたいQ値にソフトマックス関数をかけているだけのように思えることもあります。実際にQ関数と方策の間に関係があることを示した話もあり、このあたりが統一的視点から眺められれば面白いです。MCTSとαβ探索は適当な仮定を入れれば一致するんじゃないかなとかは妄想しており、モンテカルロ・ソフトマックス探索もそこに加わる一種として記述できそうな気もします。

762alpha

　Flowboardの説明がよくわかりませんでしたが、なるほど局面のデータ構造を工夫するという案も当然ありますね。

　良い評価関数に期待される性質として挙げられるものも興味深いところです。ベイジアンフィルタには詳しくないので学習時の工夫における妥当性はいまいちピンとは来ませんが、一般化して学習時のみに使う対戦相手を用意するというのはありな話だとは思います。

Windfall

　正方形ではないカーネルを考えるのも確かにやってみたいことの一つではあります。角の利きを考えると斜めのカーネルもあった方が良いんでしょうか。それを上手く実装できるのかどうかはわかりませんが……。

　ネットワークを深くしながらの逐次的な学習ができれば良いんですが上手く実装する方法があまりわかっていません。Define by runのフレームワークならわりと素直にできるんでしょうか。

st34

　「局面の評価と詰みの評価で異なる評価関数を使用」という点が面白いと思いました。以前囲碁の方で補助タスクを入れた方が性能が良くなるという論文についての記事を上げたんですが、将棋だと詰みの有無を補助タスクとして与えることで同じような効果が得られないかなと考えたりします。詰みのある確率を出力できれば学習の補助だけではなく実践の探索時でも利用ができそうなので悪くないタスクなんじゃないかと勝手に考えていますが、実験などはまだしていません。

うさぴょん外伝

　入力情報の圧縮がすごそうです。10k時点での一致率が最終的な性能とほぼ同等という点も興味深く、確かにほとんど同じような条件で行っているなら馬鹿正直に最後まで回していく必要もないのかもしれません。

　そして真に興味深いのは追記以降。これは行動の表現を考えているということにも近いのだと思います。行動表現の獲得を評価値との学習に結びつけたこの構造は注目に値すると思います。得られた行動表現で似た行動が近い表現になっているのかどうかが気になります。この行動表現空間への写像として方策関数とかを考えられないものでしょうか。あるいは環境モデルにおいてこの行動表現で遷移するとか……。

　完全に自分の興味が先行してしまいましたが、これはかなり面白い仕組みだと思います。将来的にはDNN系将棋ソフトのスタンダードになってもおかしくないのではないかと考えているところで、ぜひとも今回だけでなく発展していった形を見たいところです。

おまけ1:Miacis

　手前味噌にはなりますが、Miacisも評価値の確率分布を考慮する少し珍しいプログラムになっています。単に確率分布を考えて見た目が面白いというだけではなく、それがちゃんと評価関数の精度向上(+450程度)につながっており、なおかつ探索でも有効利用できている(+R80程度ですが……)というのがささやかな自慢ポイントです。GUIなどは作っていないので将棋所のテキスト部分で簡易的な表示をすることしかできませんが、会場に来られる方はぜひ様子を見に来ていただけると嬉しいです。

おまけ2:GPGPU勢の使用フレームワーク

　個人的に興味があったので明示的に使用フレームワークを書いていたソフトだけ抽出しました。多種多様です。cuDNNのAPIを直接叩くのが一番迫力あると思っています。

ソフト名 フレームワーク
dlshogi Chainer, cuDNN
ひまわり Tensorflow
Crazy Shogi cuDNN
ねね将棋 CNTK
Miacis PyTorch(C++API)
Windfall PyTorch(C++API？)
AobaZero OpenCL
Google Colab TPU将棋 Tensorflow

追加学習による性能向上の検証

コンピュータ将棋

　今までは再現性や比較の観点から毎回ランダム初期化したパラメータから学習を行っていたが、WCSC29も迫ってきたということで最も強いパラメータに追加学習することで性能が伸びるか検証を行った。

　今まで最も性能が良いパラメータは評価値をカテゴリカル分布で出力するモデルを200kステップ学習したものとなる(アピール文書)。これをさらに200kステップの学習を3回追加で行った。つまり計800kステップの学習を行ったことになる。

　floodgate(2016年)のR2800以上同士の対局を検証データとした損失のグラフは次のようになった。

f:id:tokumini:20190428143636p:plainf:id:tokumini:20190428143643p:plain
左:Policy損失　右:Value損失

　わずがだが学習を重ねるほど損失が下がっている。Value損失は200kステップごとに(つまり学習をやり直すたびに)多少損失が上がっており、リプレイバッファでのデータのたまり方などが影響していると思われるが、詳しいことはわからない。

　Gikou2の探索深さを2に制限したもの(R1791)と対局することで性能の検証を行った。

累計学習ステップ数 勝率 相対レート
200k 53.5% 24.4
400k 52.0% 13.9
600k 60.2% 71.9
800k 71.0% 155.5

　200kから400kにおいて一度下がってしまってるが、これは100局という少ない局数での検証なのでブレの範囲内だと思われる。全体として学習を進めた方が勝率が上がっていっており、学習すればするほどまだ伸びる余地がありそうだ。また最後の200kステップではLearnerのスリープ時間を長く取ることで擬似的にActorの数を増やしている。そこでの伸びが大きいことも含め、やはり計算資源があればあるほど良いと結論付けられる。

おまけ:詳細な実験設定

　備忘録を兼ねて詳細な実験設定を記しておく。まず計4回の学習でのパラメータは次の表のようになる。

項目 値
Residualブロック数 10
CNNのフィルタ数 64
\lambda 0.925
バッチサイズ 64
学習率初期値 最初の3回は0.01、最後の1回は0.005
学習率減衰 100kステップ経つタイミングで1/10

　学習率が複数回の学習を通してどのような変化をしていたかをグラフとして残しておく。

f:id:tokumini:20190428143633p:plain

　また最初の3回はLearnerで1ステップ学習するごとに1秒の、最後の1回では2秒のスリープ時間を挟んだ。その間はActorがデータを生成することだけが行われるため、擬似的にActorの数を増やすことになる。学習を行ったマシンは2080tiを2枚搭載したものであり、2枚とも生成に当てているときは46.0 pos / secほどの生成速度となる。

方策とディリクレノイズの比率を変更した学習

コンピュータ将棋

　Miacisではメモリの関係上、指し手の教師信号として実際に指された手をOnehotベクトルとしたものを利用しており、そのためか方策が偏りやすい傾向にある。

　AlphaZeroの学習アルゴリズムでは、各探索でルートノードにおいてディリクレノイズDと元の方策\piの内分を取ることで探査を促進している。

$$ \pi' = (1 - \epsilon)\pi + \epsilon D $$

　Miacisの学習でも今までは元論文の通り\epsilon = 0.25としていたが、この\epsilonを大きくすることで方策がバラけないか試してみた。\epsilon = 0.5として学習を行った結果、200kステップ学習後の検証損失は次のようになった。

\epsilon = 0.25 \epsilon = 0.5
Policy損失 3.27 3.20
Value損失 0.882 0.876

　損失としてはわずかに改善が見られた。

　学習後のモデルが初期局面で示す方策について、主要な指し手についての確率を比較すると次のようになった。

指し手 \epsilon = 0.25 \epsilon = 0.5
▲２六歩 80.1% 78.2%
▲７八金 11.3% 3.6%
▲７六歩 2.6% 7.2%
その他 6.0% 11.0%

　偏りはやはり見られたが、その他の指し手についても値を見ると全体に少しだけ値がついており、わずかだが狙い通りの学習ができている。

　１手１秒で100局の対局を行うと\epsilon = 0.5で学習したものは\epsilon = 0.25で学習したものに対して勝率37.5%であった。散り方がランダムでは棋力としては弱くなってしまうようだ。この自己対局では序盤30手を探索した回数の割合を確率として指すことでランダム性を確保しており、そこで悪い手を指す確率が高くなっているのかもしれない。

　上の実験は普通のAlphaZero(つまりTDLeaf(λ)において\lambda = 1とした場合)として実験を行った。念の為\lambda = 0.9でも同じ結果になるか検証した。

\epsilon = 0.25 \epsilon = 0.5
Policy損失 3.26 3.13
Value損失 0.937 0.900

　損失はやはり\epsilon = 0.5とした方が小さくなった。しかし１手１秒で100局の対局を行うと勝率は26.5%となりやはり弱くなっている。ランダム手数を30手から10手へと小さくして対局を行うと勝率は36%となり、序盤での悪手が減った結果勝率が改善されたが、それでも全体として弱いことは確かなようだ。

AtCoder Beginner Contest 125

競技プログラミング

結果

　23分33秒で全完、122位だった。C問題で少し時間がかかってしまったが、順位表を見ているとD問題を先に解いている人も多く、難しめではあったのかもしれない。100位以内の壁は厚い。

A問題

　まぁA問題だし素直に割るだけなんだろうなーという感じで実装しながら脳内で確認する動き。余りを考えるのは苦手。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B, T;
    cin >> A >> B >> T;
    cout << B * (T / A) << endl;
}

B問題

　これはさすがに入力取りながら答えを求められる程度の問題だと思ったら最初にVがN個連続、そしてCがN個連続という形式の入力だったので結局一度受け取ってから別のforループで答えを求めるいつものパターンに。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;

    vector<ll> V(N), C(N);
    for (ll i = 0; i < N; i++) {
        cin >> V[i];
    }
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += max(V[i] - C[i], (ll)0);
    }
    cout << ans << endl;
}

C問題

　A_iを抜いた最大公約数が求まれば良いとはすぐ思ったが、愚直に計算するとO(N^2)かかってしまう。計算量を落とす方法がすぐにはわからなくて方針が間違っているのかと二分探索とか素因数を一つ一つ考えていくとか疑い出したが、累積和っぽいイメージでA_1, \dots A_{i - 1}の最大公約数とA_{i + 1}, \dots, A_{N}の最大公約数をあらかじめ計算しておけば、これらの最大公約数を取ればいいだけということに気づいて勝ち。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<ll> B(N), C(N);
    B[0] = A[0];
    for (ll i = 1; i < N; i++) {
        B[i] = gcd(B[i - 1], A[i]);
    }
    C[N - 1] = A[N - 1];
    for (ll i = N - 2; i >= 0; i--) {
        C[i] = gcd(C[i + 1], A[i]);
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ll p = (i == 0 ? C[i + 1] : i == N - 1 ? B[N - 2] : gcd(B[i - 1], C[i + 1]));
        ans = max(ans, p);
    }

    cout << ans << endl;
}

　B_iを[1, i]の最大公約数として計算してしまったが、こういうのも右側は開区間で取った方が実装がきれいになりそうだ。範囲系のものは大抵[i, j)として定義してしまうので問題ない気がするし、こうした方が区間を取るミスも少しは減らせそうか。

　解説PDFを見たら、GCDを変えない初期値としてB_0 = 0としていた。なるほど確かにgcd(X, 0) = gcd(0, X) = Xとなるのは自分の実装でも計算してみるとわかる。当たり前なんだろうけどこれは勉強になった。

D問題

　いかにもDPですという顔をしている問題に見えた。そういうつもりで考えていくとi番目のものを考えるときに直前で操作を行ったかどうかの2通りを考えれば良いということはすぐに見えるものなので、細部を詰めて実装して難なくAC。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<vector<ll>> dp(2, vector<ll>(N + 1, 0));
    dp[1][0] = INT_MIN;

    for (ll i = 0; i < N; i++) {
        //操作する
        dp[1][i + 1] = max(dp[0][i] - A[i], dp[1][i] + A[i]);

        //操作しない
        dp[0][i + 1] = max(dp[0][i] + A[i], dp[1][i] - A[i]);
    }

    cout << dp[0][N] << endl;
}

　他のDPでもそうだけど、直前だけに依存するなら無駄に過去の情報を保持する必要もない。今までは考えやすいように(メモリ使用量が大丈夫なことを確認して)冗長でも長さ分取るようにしていたが、そろそろ必要なところだけを残すようにした方が良いかなとも思う。

　解説PDFを見たら、最終的に負のまま残るのは負であるものが奇数個のとき1個、偶数個のとき0個なので簡単に計算できるとあってそれは全く気づいていなかった。解いているときにすぐDPに向いてしまって問題の考察をサボっているという感じは確かにあったが、こんな簡単な性質を見落としているとは。やけにD問題解いた人多いなと思ったのはこういうからくりだったのか。できればこういう解法が浮かぶような考察をしていきたいと思っているのでこれは反省点。すぐ知っているアルゴリズムに帰着させようとしすぎてはいけない。

Recurrent World Models Facilitate Policy Evolutionを読んだ

論文

出典

　David Ha and Jürgen Schmidhuber, “Recurrent World Models Facilitate Policy Evolution,” Advances in Neural Information Processing Systems 31, 2018.

　arXiv:https://arxiv.org/abs/1809.01999

　World Models:https://arxiv.org/abs/1803.10122

概要

　環境モデルをVAEとRNNを用いて学習

詳細

提案システムの全体像

　入力画像をVAEで表現に変換し、それをRNNに入力していく。制御部分(C)は表現zとRNNの隠れ状態hを入力とし、行動を出力する。

VAE

  • 入力画像(観測情報)o_tから状態表現z_tを獲得。

MDN-RNN

  • 状態表現z_tと行動a_tを受け取って次状態の表現z_{t + 1}を混合ガウス分布として予測するRNN
    • この仕組みは既存の手法

Controller

  • 状態表現z_tとRNNの隠れ状態h_tを連結したものを入力
  • 線形関数で方策決定a_t = W_c[ z_t h_t ] + b_c
  • パラメータ数が少ない線形関数なので勾配法によらない最適化が可能

実験

実験1:Car Racing

  • 真上視点の画像を入力に車を運転するタスク
  • 学習手順
    1. ランダムな行動で10,000回試行しデータを収集
    2. Vを学習:収集したデータに出てきた画像を再構成
    3. Mを学習:学習したVと収集データからP(z_{t + 1}|a_t, z_t, h_t)を学習
    4. Cを学習:学習したV,Mから入力を得て、実際の環境から得られる報酬を最大化

  • M(から得られる隠れ状態h)を使わないと低性能(下から2,3段目)
  • VとMを両方使うことで高性能(最下段)

実験2:Viz Doom

  • 敵モンスターが撃ってくる火の玉を左右移動で避けるタスク
  • 学習した環境モデルのみを用いて学習
    • Mモデルに「プレイヤーが玉に当たったかどうか:d」を予測する出力を追加
  • 学習手順
    1. ランダムな行動で10,000回試行しデータを収集
    2. Vを学習:収集したデータに出てきた画像を再構成
    3. Mを学習:学習したVと収集データからP(z_{t + 1},d_t |a_t, z_t, h_t)を学習
    4. Cを学習:学習したV,Mを用いた仮想環境で生存時間を最大化するように学習

  • 仮想環境のランダム性\tauを上げると遷移が不安定になり難易度上昇
    • 不完全な環境モデルへの過学習を抑制→学習中のスコアは落ちるが実スコアは向上

Discussion

  • 環境モデルを学習できることはコストの観点から有用
    • シミュレーション上で学習した結果を現実世界に転用する研究(4, 33)を補完
  • VAEは一般的な(再構成に有用な)特徴を獲得
    • タスクを解く上で有用な特徴量を取れるとは限らない
    • 人間はタスクに関連した特徴を学ぶ(65)
  • 上達しないと観測できない状態があると今回の手法では不十分
    • 方策の学習と環境モデルの学習を同時に行う必要性
      • 環境モデルの学習に有用な情報を得る制御(83)
      • 好奇心、内的動機づけを用いた探索(61, 64, 77, 80, 81)
      • 情報を探す手法(23, 86)
      • 新しい探索を奨励する手法(47)
  • VAE&MDN-RNNの表現力の限界
    • Catastrophic Forgettingの問題(16, 43, 69)
    • より大きいモデル(27, 89, 93, 97, 98)や記憶モジュール(19, 107)を使うことによる表現力向上の可能性
  • 単純なRNNだと1ステップごとのシミュレーション以外不可能
    • 時空間の細部を無視した抽象的思考や階層的計画が重要
      • RNNをサブルーチンに持つCを用いる研究(83)
      • CとMを一つのネットワークに融合する研究(84)
      • PowerPlay(82, 91)
      • Behavioural Replay(79)

所感

  • モデルのみを用いた学習で、モデルに過剰適合したCheatingが起こるという話(4.2節)が面白かった
  • Discussion部分が興味深く、ここで挙げられていた論文は一通り目を通したいところ
  • 結局Cへの入力に使っているのは状態表現とRNNの隠れ状態だけなので先読みを明示的に行う方法も考えたい
    • 次状態予測部分をRNNでモデル化しなければならない必然性があるのかどうか

Tenka1 Programmer Contest 2019

競技プログラミング

結果

　C問題だけの1完で711位だった。青あたりのレート帯だとC問題早解きゲームと化していて、24分(1WA)では良い順位を望むべくもなく。レート変動は1748→1720(-29)。

C問題 Stones

f:id:tokumini:20190421144421j:plain

　最初はメモの前半のように文字列を「B...BW...W」の繰り返しと考えて、これらを個別に見て少ない方を全部反転すれば良いと思って1WA。これだとたとえば「BBBWBWWW」のとき、前半4文字「BBBW」ではWの方が少ないので4文字目をBへ、後半4文字「BWWW」ではBの方が少ないのでBをWへという操作になるが、結果として得られるのは「BBBBWWWW」でBWが残ってしまっている。

　ジャッジが詰まっていたのもあって提出の後結果が出るまでにかなり時間がかかった。D問題を考えていたが戻って考え直して、最終的に「...WB...」という形になるしかないのでこのWBの切れ目を全探索すれば良いと気づく。無駄に累積和の配列を構築して範囲を考えて……とかやっていたら混乱してしまい実装に時間もかかった。WAを出してしまった焦りもあったんだと思う。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    string S;
    cin >> N >> S;

    vector<ll> b(N + 1, 0), w(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        if (S[i] == '#') {
            b[i + 1] = b[i] + 1;
            w[i + 1] = w[i];
        } else {
            b[i + 1] = b[i];
            w[i + 1] = w[i] + 1;
        }
    }

    ll ans = INT_MAX;
    for (ll i = 0; i <= N; i++) {
        ans = min(ans, b[i] + w[N] - w[i]);
    }
    cout << ans << endl;
}

　最初の方針は確かに不安な感じもあったが、この程度の不安感なら通ることもあるという判断で提出してしまった。せめて「B...BW...W」が2回繰り返されるケースはやるべきだったし、大小の組み合わせで

  • BBBWBBBW
  • BBBWBWWW
  • BWWWBBBW
  • BWWWBWWW

の4通りくらいは考えるべき。怪しい解法に対する敏感さというのも実践感覚の一種だと思っていて、最近あまり問題を解いていないから鈍っているのだろう。

D問題 Three Colors

f:id:tokumini:20190421150433j:plain

　最初いくらか性質を考えて、まずはパッと思い浮かぶDPを疑う(青線上部)。感覚的には間に合わないんだけど、具体的にどういう計算量になるのかはっきりと示せなくてひょっとしたら(最大値の制約とかで枝刈りを入れれば)通るんじゃないかと思ったりもする。

　あとはRの値を全探索して残りをG,Bに振り分けるという形で解けないか考えていた(青線以下)。Rを特定の値にするときにどれを使うかはDPで求まりそうだと思ったがG,Bへの振り分けが上手くいきそうにない。大小関係に仮定を入れて対称性から考えるにも等号が入ったりするとめちゃくちゃになるなぁというところで進まなくなってしまった。そもそも場合の数を考えられていないので全然ダメな方針だった。

　残り時間が少なくなったところで、とりあえず最初のDP方針で解けてしまうのだったら後で悔しいので実装して提出。当然TLE。下の方針でも実はRの範囲が狭いからなんとか間に合うとかそういうことがあるのかもしれないと思いつつ実装しているところで時間切れ。解けそうな雰囲気があまりしなかった。

　振り返ってみても根本的にメモの量が少ない。しかし具体例をいじるタイプの問題でもないと思うので考察の進め方がよくわからなかった。

　解説を見るとまず「R, G, B のうち一番大きいものが S/2 以上となるような塗り分け方の個数を求めて全体から引くことを考え」ることに思い至っていないので初手からダメだったようだ。条件に合わないものを引く考え方があまりできていない気がする。

　解説だとさらっとDPでできると書いてあるが、実装がよくわからなかったので他の人の提出をだいたい写す感じでAC。これは難しいなぁ。

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
    constexpr ll MOD = 998244353;

    ll N;
    cin >> N;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    ll sum = accumulate(a.begin(), a.end(), (ll)0);

    vector<vector<ll>> dp1(N + 1, vector<ll>(sum + 1, 0));
    vector<vector<ll>> dp2(N + 1, vector<ll>(sum + 1, 0));

    ll ans = 1;

    for (ll i = 0; i < N; i++) {
        //全通りは3のN乗
        (ans *= 3) %= MOD;

        //rが0ならそれまでのものはg or bに振り分けられていた→2のi乗
        dp1[i][0] = (i == 0 ? 1 : dp1[i - 1][0] * 2 % MOD);

        //dp2はgしか使わないので1で初期化
        dp2[i][0] = 1;

        for (ll j = 0; j <= sum; j++) {
            //a[i]をr以外に足す
            //dp1ではg or bに足す(2倍される)
            (dp1[i + 1][j] += dp1[i][j] * 2) %= MOD;

            //dp2ではgに足す(1倍のまま)
            (dp2[i + 1][j] += dp2[i][j]) %= MOD;

            if (j + a[i] > sum) {
                continue;
            }

            //a[i]をrに足す
            (dp1[i + 1][j + a[i]] += dp1[i][j]) %= MOD;
            (dp2[i + 1][j + a[i]] += dp2[i][j]) %= MOD;
        }
    }

    for (ll i = (sum + 1) / 2; i <= sum; i++) {
        ans = (ans + MOD - dp1[N][i] * 3 % MOD) % MOD;
    }

    if (sum % 2 == 0) {
        //重複して引きすぎたものを戻す
        ans = (ans + dp2[N][sum / 2] * 3 % MOD) % MOD;
    }

    cout << ans << endl;
}

AlphaZeroに対するTDLeaf(λ)の適用 ~実験編~

コンピュータ将棋

　前回はTDLeaf(\lambda)の理屈からAlphaZeroにおいて探索した値を用いる方法を検討した。今回はそれを基に強化学習を行った結果を記す。

損失による評価

　floodgate2016年・R2800以上同士の棋譜に対する損失計算によって評価を行った。

f:id:tokumini:20190413151233p:plain f:id:tokumini:20190413151246p:plain

　\lambda = 0.95, 0.925, 0.9の3つの値について試してみたが、どの値についても傾向は概ね似たものとなった。

　まずPolicy損失については\lambda = 1とするよりも速く減少したが、最終的な値はほぼ変わらなかった。それぞれ1回しか学習を試せていないので、単純に\lambda = 1のときの学習で良くない乱数を引いたというだけの問題かもしれない。

　Value損失もまた\lambda = 1とするよりも速く減少したが、途中から徐々に上がり始め、最終的な値は悪くなってしまった。

　TDLeaf(\lambda)は探索した値を使うブートストラップ手法なので、終盤から学習が進んでいき徐々に序盤へ伝播していく。実際に\lambda = 0.9とした場合と\lambda = 1.0の場合について、1万局目に生成した対局の評価値グラフを示す。評価値は状態価値を1000倍したものであり、[-1000, 1000]の範囲で表される。

f:id:tokumini:20190413161911p:plainf:id:tokumini:20190413161915p:plain
左:\lambda = 0.9 右:\lambda = 1.0

　\lambda = 0.9とした場合では序盤はほぼ0の値となっているが、\lambda = 1.0の場合は序盤からいくらか値がついていることがわかる。

　\lambdaを1未満にした場合、学習初期では終盤だけが信頼度の高い教師情報によって少し学習されることになり、損失はなだらかな減り方をするものと考えられる。逆に\lambda = 1の場合は序盤についても最終的な結果から教師情報を与えるので学習初期でも値がつくが、それが適切であるとは限らないため損失が上がってしまうのだと予想される。

　最終的な性能差については、学習終わり頃の対局データを見てみたところ\lambda = 0.95, 0.9の場合初期局面に400など大きな値がついていた。ブートストラップの影響により一度偏った値になると修正が効かないのではないかと考えられる。しかし\lambda = 0.925の場合は初期局面における偏りは特に見られず、この説が正しいかどうかは疑わしい。

対局による評価

　損失が本当に棋力と相関しているかどうかはわからないため、実際に1手1秒で100局対局させることで性能を評価した。\lambda = 0.9で200kステップ学習したものを

  1. \lambda = 1.0で200kステップ学習したもの
  2. \lambda = 0.9で100kステップ学習したもの

の2つと対局させた。損失から見るとこれらは

学習内容 Policy損失 Value損失
\lambda = 0.9で200kステップ 3.26 0.94
\lambda = 1.0で200kステップ 3.27 0.88
\lambda = 0.9で100kステップ 3.28 0.89

となっており、Policy損失はおおむね同じでありValue損失に差があることから一番上のものよりも下二つの方が棋力が高いと予想される。

　\lambda = 0.9で200kステップ学習したものから見て対局結果は次のようになった。

対戦相手 勝率(%) 推測レート差
\lambda = 1.0で200kステップ 62 85.0
\lambda = 0.9で100kステップ 73 172.8

　予想に反してValue損失が大きいものが一番強い結果となった。学習が進むにつれて損失は悪化していたが性能は良くなっているようだ。また\lambda = 1とした場合よりも性能が良くなることもわかった。

　レート1200前後といったレベルでも損失が棋力を表す指標として信頼できないという事実は重大だ。自己対局はコストがかかるが、1手1秒ではなくノード数による制限などをしてでも対局から性能評価するべきかもしれない。

AtCoder Beginner Contest 124

競技プログラミング

結果

　29分56秒で全完。137位だった。簡単なセットだったのでなかなか順位は伸びず。

A問題

　std::maxにinitializer_listを渡す(ということをしているのだという理解で良いはず)。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B;
    cin >> A >> B;
    cout << max({ 2 * A - 1, A + B, 2 * B - 1 }) << endl;
}

B問題

　最大値を保存しておけば良いのだなと。こういうの入力取る時にそのまま計算できそうだなと思うんだけど手癖で分けでしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> H(N);
    for (ll i = 0; i < N; i++) {
        cin >> H[i];
    }

    ll ans = 0, h = 0;
    for (ll i = 0; i < N; i++) {
        if (H[i] >= h) {
            ans++;
            h = H[i];
        }
    }

    cout << ans << endl;
}

C問題

　黒始まりか白始まりかを2通り試すだけでメモを取るまでもなく。しかしelseを使わず無駄な書き方しているなぁ。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;

    ll ans1 = 0, ans2 = 0;
    for (ll i = 0; i < S.size(); i++) {
        if (S[i] == ('0' + i % 2)) {
            ans1++;
        }
        if (S[i] == ('0' + (i + 1) % 2)) {
            ans2++;
        }
    }

    cout << min(ans1, ans2) << endl;
}

D問題

f:id:tokumini:20190413223101p:plain

  1. 問題の性質を少し考える
  2. DPを疑う
  3. 二分探索を疑う
  4. 問題の性質から答えに気づく

　という感じの流れだった。二分探索を考えようと思ってメモに「二分探索を考える」って書いた瞬間に「(選ぶ)K (個)はかためた方が良い」っていうところに気づいて単純なO(N)だということがわかった。しかし累積和で脳が混乱してしまうタイプの人間なのでわりと実装に苦労した。フリップするK個の区間について、もともと1である区間はその両脇まで取らないといけないというところをもう少し道筋よく考えられたら良かったが。

　0,1をまたぐような区間のフリップはダメだと勝手に思い込んでいたけど別に操作としては可能だということに実装途中で気づいて焦ったが、そういう取り方は無駄なので考えなくて良さそうと思った。証明はしていないのでただの勘。WAが出たらちゃんと考えなおそうと思って出して通ったのでそれで良しの精神。

　尺取り法はだいぶ馴染みがないので全然思い浮かばない。実装したことも1,2回しかない気がする。二分探索でもいけるのか。まぁそうかな。やり方はいろいろありそう。解法が手広く見えたら良さそうだが、高望みでもある。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    vector<ll> a[2];

    char target = '0';
    ll num = 0;
    for (char c : S) {
        if (c == target) {
            num++;
        } else {
            a[target - '0'].push_back(num);
            num = 1;
            target = (target == '0' ? '1' : '0');
        }
    }
    a[target - '0'].push_back(num);

    if (a[0].size() <= K) {
        cout << N << endl;
        return 0;
    }

    if (a[0].size() != a[1].size()) {
        a[1].push_back(0);
    }

    //累積和
    vector<vector<ll>> sum(2, vector<ll>(a[0].size() + 1, 0));
    for (ll i = 0; i < a[0].size(); i++) {
        sum[0][i + 1] = sum[0][i] + a[0][i];
        sum[1][i + 1] = sum[1][i] + a[1][i];
    }

    ll ans = 0;
    for (ll i = 0; i <= a[0].size() - K; i++) {
        ans = max(ans, sum[0][i + K] - sum[0][i] + sum[1][i + K] - (i == 0 ? 0 : sum[1][i - 1]));
    }
    cout << ans << endl;
}

AlphaZeroに対するTDLeaf(λ)の適用 ~準備編~

コンピュータ将棋 論文

TDLeaf(\lambda)の出典:Jonathan Baxter, Andrew Tridgell, Lex Weaver, "TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search," Proceedings of the Ninth Australian Conference on Neural Networks (ACNN'98), Brisbane QLD, February 1998, pages 168-172

　TDLeaf(\lambda)とは1998年からある古い手法であり、簡単に言えばTD(\lambda)を探索した値を使って行うものである。

TD(\lambda)

　TD(\lambda)とは、強化学習でよく用いられる時間差分学習の一種であり、後に続く状態の価値を\lambdaで重みづけながら教師情報として利用するものである。以下ではボードゲームのように報酬が最終状態でのみ与えられ、割引率が1であるような状況を前提とする。時刻tにおける状態s_tについて、それに対する教師情報y_tは各状態の価値v_tを用いて次の図のように計算される。Tは終端ステップ、zは最終結果に基づく報酬を示す。

　

　式として書くと

\displaystyle y_t = \lambda^{(T-t-1)} z + (1 - \lambda) \sum_{\tau = t + 1}^{T-1} \lambda^{\tau - t - 1} v_{\tau} \tag{1}

となる。これを目標に現在の状態価値を修正していけば良い。たとえば自乗誤差 (y_t - v_t)^2 を考えて勾配法で学習するなどの方法が考えられる。

　多くのボードゲームではTがそこまで大きくなることはないので影響はないかもしれないが、注意点として式(1)を愚直に計算すると各y_tを計算するのにO(T)かかるので全y_tを求める計算量はO(T^2)となってしまう。しかし式(1)はよく見ると

\displaystyle y_t = \lambda y_{t + 1} + (1 - \lambda) v_{t +1} \tag{2}

　と書けることがわかるので、後ろから計算していけばy_{T - 1}, y_{T - 2}, \dots, y_{1}がO(T)で求まる。式(2)を見てもわかるように、要するにy_{t+1}とv_{t + 1}の内分を取っていることになる。

TDLeaf(\lambda)

　TDLeaf(\lambda)ではTD(\lambda)を探索を用いた手法へと拡張した。基本的には上のTD(\lambda)でのvを探索した値で置き換えるということになる(GA将ブログなど参照)。

　論文ではαβ探索に対しての適用が議論されており、学習する状態も探索した葉にあたるノードを用いているが、必ずしもそのようにする必要はないと感じる。特にモンテカルロ木探索へ応用することを考えると、平均化しているので探索で得られた値に対応する葉のノードが一意に定まらない。学習する状態は探索を始めた根にあたるノードとしても良いと思われる。(余談ですがTDLeaf(\lambda)をモンテカルロ木探索へ応用する論文を見つけられていません。ご存じの方がいましたら教えていただけるとありがたいです。)

　その場合ある局面s_tについて探索した値v'_tもTD(\lambda)で考慮する値としたい。つまり上の図が1ステップずつずれるような計算になる。式(2)で示した教師情報をO(T)で求める工夫と合わせて、結局次の図のような計算をすれば良い。

　式として書くと

\displaystyle y_t = \lambda y_{t + 1} + (1 - \lambda) v'_{t} \tag{3}

であり、このy_tを基に状態s_tにおける(探索をしない)価値v_tを更新する。

　ここでAlphaZeroの学習法はTDLeaf(\lambda)において\lambda = 1としたものだと捉えることができる。探索した値には全て1-\lambdaがかけられるので、\lambda = 1とすれば最終結果のみを考慮することになるためである。

　AlphaZeroのように最終結果だけを用いるのではなく、探索結果も使った方が学習が速いことはOracle Developersの記事で検証されている。ここでは最終結果と探索結果の平均や内分が取られている(elmoの学習方法とほぼ同じである)が、TDLeaf(\lambda)の観点からすると\lambda \lt 1とすることで探索結果を取り入れることができる。次回に続く。