DeepLearningによる将棋の学習5~損失の配分を変更~

　前回はフィルタサイズを変更してもうまくいかないことを確認しました。

　個人的にはDeepLearningによる学習でValueの学習がなかなかうまくいかないという点が気になっています。マルチタスク学習をさせているので損失は指し手の一致具合とValueの一致具合の和を取っている

loss_op = tf.reduce_mean(tf.nn.sparse_softmax_cross_entropy_with_logits(logits=policy, labels=teacher_for_move)
                         + tf.nn.sigmoid_cross_entropy_with_logits(logits=value, labels=teacher_for_win))

のですが、ここの配分を変えてみることで何か知見が得られないかと考えました。

　小さいデータ(訓練用1000局、テスト用100局)でいくらか試してみたところ、Value側の損失を大きくしても(定数100をかけても)そこまでValue予測の質は改善されない一方、指し手予測の方はひどい性能になりました。

　もともとValueだけを学習するネットワークでもそこまでの精度になっていないことを考えると、これは当たり前なのかもしれません。

　一方で逆にValueの損失を小さくするとValue予測の方は多少質が悪化した一方で指し手予測の精度は上がったため、これで全データを使って実験してみました。正確にはvalue側の損失に0.1をかけて学習させました。

loss_op = tf.reduce_mean(tf.nn.sparse_softmax_cross_entropy_with_logits(logits=policy, labels=teacher_for_move)
                         + 0.1 * tf.nn.sigmoid_cross_entropy_with_logits(logits=value, labels=teacher_for_win))

　Residualブロック数は5、optimizerはSGD、early stoppingのpatienceは7で実験した結果が以下となります。

epoch	Loss	Move Accuracy	Value Accuracy
1	3.5121	0.2691	0.6114
2	3.0486	0.3111	0.6389
3	2.8629	0.3315	0.6432
4	2.7399	0.3454	0.6505
5	2.6606	0.3545	0.6572
6	2.6133	0.3587	0.6618
7	2.5537	0.3667	0.6635
8	2.5361	0.3689	0.6647
9	2.5160	0.3707	0.6698
10	2.4973	0.3730	0.6707
11	2.4876	0.3743	0.6689
12	2.4843	0.3759	0.6745
13	2.4760	0.3783	0.6731
14	2.4844	0.3774	0.6744
15	2.4794	0.3795	0.6742
16	2.4832	0.3790	0.6717
17	2.4864	0.3799	0.6747
18	2.4926	0.3797	0.6761

　学習に必要なエポック数は伸びていますが特に性能は上がっていません。損失の合計が小さくなっているので収束が遅いのは当然なのでしょうか。それならばValue側の損失の寄与も十分に意義あるものだった、ということになると思えます。

　学習自体が不安定なのではないかという説も自分の中で起こっています。同じ条件で何度も実験してみないと何も言えないのかもしれません。

　実験とは本質的に関係のないことかもしれませんが、ログファイルから表の作成、グラフの作成あたりは自動化しておいたほうが良さそうですね。山岡さんの本でもいくらか記述があったので、それを参考に頑張ってみたいと思います。

DeepLearningによる将棋の学習4~フィルタサイズの変更2~

　前回はフィルタサイズを5にして実験してみました。その結果性能は下がり、学習時間も多くなるということがわかりました。単純に考えれば増やしてもダメだということになるのですが、念のため今回はさらにフィルタサイズを7にして実験を行いました。結果は以下の通りです。

epoch	Loss	Move Accuracy	Value Accuracy
1	3.5894	0.3014	0.6561
2	3.2799	0.3346	0.6786
3	3.2016	0.3457	0.6791
4	3.2024	0.3553	0.6773
5	3.2453	0.3565	0.6728
6	3.4741	0.3611	0.6501
7	3.3973	0.3579	0.6676
8	3.5083	0.3570	0.6656
9	3.5896	0.3581	0.6662
10	3.6940	0.3570	0.6682

　今までの結果とまとめると次のようになります。

フィルタサイズ	Loss	Move Accuracy	Value Accuracy	1エポックあたりの学習時間
3	2.9753	0.3879	0.6853	約40分
5	3.1447	0.3643	0.6744	約47分
7	3.2016	0.3457	0.6791	約49分

　やはりフィルタサイズは3が良いようです。

DeepLearningによる将棋の学習3~フィルタサイズの変更~

　前回はブロック数を10、optimizerをAdamにして実験してみましたが良い結果は得られませんでした。

　今回はブロック数ではなくフィルタサイズを3→5に変更して学習させてみました。ブロック数は5、optimizerはSGD、patienceは7です。下の表が結果となります。

epoch	Loss	Move Accuracy	Value Accuracy
1	3.6433	0.2979	0.6583
2	3.2917	0.3352	0.6791
3	3.1746	0.3504	0.6803
4	3.1395	0.3576	0.6763
5	3.1447	0.3643	0.6744
6	3.1594	0.3686	0.6778
7	3.1695	0.3709	0.6735
8	3.2584	0.3708	0.6730
9	3.3467	0.3706	0.6707
10	3.3977	0.3705	0.6708
11	3.4479	0.3679	0.6675

　グラフとして描くと下の様になります。

　フィルタサイズ3のものに比べると以下のようになります。

フィルタサイズ	Loss	Move Accuracy	Value Accuracy	1エポックあたりの学習時間
3	2.9753	0.3879	0.6853	約40分
5	3.1447	0.3643	0.6744	約47分

　性能が悪化していることがわかります。また学習時間も伸びているため良いとこなしです。

　これを書く段階で気づきましたがoptimizerはフィルタサイズ3のときに合わせてNesterovにするべきでした。ここが統一されていない時点で今回の実験は比較に値しないものかもしれません。

　学習曲線の気になるところとしてはロスが下がらなくなったあともMove Accuracyは少し上がっていることでしょうか。しかしValue Accuracyは下がっているため、良い学習ができているわけでもなさそうです。

　この実験に限らずDeepLearningではValueの学習がなかなか難しいという印象を持っており、2駒関係などでそれなりな性能が出ることを考えると少し意外だと感じます。なにか実装を間違えているのではないかという気にもなりますが、山岡さんの本でもあまりValue Accuracyは高くなっておらず、これくらいなものなのかもしれません。

DeepLearningによる将棋の学習2~Adamによる学習~

　前回の続き。

　patienceを7にしてAdamでもやってみました。

optimizer = tf.train.AdamOptimizer(learning_rate=0.001)

　結果は次の通りです。

epoch	Loss	Move Accuracy	Value Accuracy
1	4.4521	0.2929	0.6807
2	4.1956	0.3232	0.6873
3	4.1133	0.3335	0.6898
4	4.0703	0.3424	0.6890
5	4.0683	0.3443	0.6880
6	4.1143	0.3480	0.6846
7	4.1600	0.3477	0.6800
8	4.1749	0.3476	0.6822
9	4.2409	0.3456	0.6787
10	4.2836	0.3483	0.6772
11	4.2952	0.3469	0.6761
12	4.3597	0.3464	0.6791

　5epochで損失が下がりきっており、収束は速いのですが、収束した値の性能はあまり良さそうではありません。

　またここから損失が再び下がっていくということはないように思えます。

　今までの結果をグラフ化すると

　となります。patienceが小さすぎるということはないのかなぁと思えるのですが、もっとやったら違うのかもしれません。またそもそも学習データ量が少なすぎる可能性もあり、たとえば2015年の棋譜を使う、あるいはやねさんが公開されている(まだ公開されているのでしょうか？)ものを使うなどのことをしなければならないのかもしれません。

DeepLearningによる将棋の学習1

　山岡さんの本を参考にtensorflowを用いてDeepLearningを用いた将棋ソフトを作ってみています。

将棋AIで学ぶディープラーニング

　ResidualNetを実装しているところなのですが、実装がまずいのかブロック数を増やすと上手く学習してくれないという事態が起こりました。現在の実装は以下の通りです。山岡さんの本をそのまま模倣しようとしているので、そうなっていない部分があったら指摘していただけると幸いです。

ch = 192
kernel = 3


def ResidualBlock(inputs):
    conv1 = tf.layers.conv2d(inputs=inputs, filters=ch, kernel_size=kernel, padding="same", use_bias=False)
    bn1 = tf.layers.batch_normalization(inputs=conv1, training=True)
    relu1 = tf.nn.relu(bn1)
    conv2 = tf.layers.conv2d(inputs=relu1, filters=ch, kernel_size=kernel, padding="same", use_bias=False)
    bn2 = tf.layers.batch_normalization(inputs=conv2, training=True)
    return tf.nn.relu(inputs + bn2)


def policy_value_func(features):
    # Input Layer
    # featuresのshapeは9×9マスが104チャネル ([-1, 9, 9, 104])
    input_layer = features

    # ResidualBlock
    conv1 = tf.layers.conv2d(inputs=input_layer, filters=ch, kernel_size=3, padding="same", activation=tf.nn.relu)
    res1 = ResidualBlock(conv1)
    res2 = ResidualBlock(res1)
    res3 = ResidualBlock(res2)
    res4 = ResidualBlock(res3)
    res5 = ResidualBlock(res4)
    res6 = ResidualBlock(res5)
    res7 = ResidualBlock(res6)
    res8 = ResidualBlock(res7)
    res9 = ResidualBlock(res8)
    res10 = ResidualBlock(res9)

    # policy_network用
    conv13p = tf.layers.conv2d(inputs=res10, filters=MOVE_DIRECTION_LABEL_NUM, kernel_size=1, padding="same",
                               activation=tf.nn.relu)
    policy = tf.reshape(conv13p, shape=[-1, 9 * 9 * MOVE_DIRECTION_LABEL_NUM])

    # value_network用
    conv13d = tf.layers.conv2d(inputs=res10, filters=MOVE_DIRECTION_LABEL_NUM, kernel_size=1, padding="same",
                               activation=tf.nn.relu)
    # 1次元化する
    flat = tf.reshape(conv13d, [-1, 9 * 9 * MOVE_DIRECTION_LABEL_NUM])

    # 全結合層
    dense = tf.layers.dense(inputs=flat, units=256, activation=tf.nn.relu,)
    # 出力値はスカラ1つ
    value = tf.layers.dense(inputs=dense, units=1)
    # サイズ1のベクトルになっているのでsqueezeで直す
    value = tf.squeeze(value, axis=1)

    # policyとvalueの二つを返す
    return policy, value

　学習はfloodgateの2016年の棋譜を山岡さんの本の通りに学習用3,711,167局面、テスト用414,677局面に分け、early stoppingをpatience = 3でやっています。

　5ブロックで行った場合の結果が以下

epoch	Loss	Move Accuracy	Value Accuracy
1	3.6427	0.3086	0.6702
2	3.2474	0.3481	0.6825
3	3.1120	0.3646	0.6899
4	3.0099	0.3765	0.6882
5	2.9835	0.3807	0.6913
6	2.9768	0.3865	0.6861
7	2.9753	0.3879	0.6853
8	3.0051	0.3903	0.6839
9	2.9959	0.3927	0.6816
10	3.0267	0.3927	0.6815

　10ブロックで行った場合の結果が以下のようになります。

epoch	Loss	Move Accuracy	Value Accuracy
1	5.0812	0.2416	0.6547
2	4.6445	0.2853	0.6804
3	4.4765	0.3042	0.6877
4	4.3976	0.3153	0.6901
5	4.3842	0.3237	0.6883
6	4.3915	0.3265	0.6866
7	4.3952	0.3267	0.6836
8	4.4427	0.3301	0.6837

　5ブロックのときと比べて損失が大きい段階で学習が終了しています。指し手の一致率も6%以上低いです。今冷静に見返すとやはりもっとpatienceを大きくするべきなのでしょうか……。

　上の二つの実験はoptimizerをNesterovありのmomentum

optimizer = tf.train.MomentumOptimizer(learning_rate=0.01, momentum=0.9, use_nesterov=True)

で行っており、普通のSGD

optimizer = tf.train.GradientDescentOptimizer(learning_rate=0.01)

にしたところ5ブロックの場合にやや劣る程度になりました。

epoch	Loss	Move Accuracy	Value Accuracy
1	3.9261	0.2829	0.6452
2	3.4671	0.3243	0.6741
3	3.2671	0.3472	0.6791
4	3.1414	0.3597	0.6859
5	3.0936	0.3697	0.6810
6	3.0394	0.3727	0.6882
7	3.0323	0.3789	0.6845
8	3.0575	0.3811	0.6798
9	3.0550	0.3833	0.6842
10	3.0771	0.3852	0.6813

　表にして最終結果をまとめると以下のようになります。

model	Loss	Move Accuracy	Value Accuracy
5ブロック(Nesterov)	2.9753	0.3879	0.6853
10ブロック(Nesterov)	4.3842	0.3237	0.6883
10ブロック(SGD)	3.0323	0.3789	0.6845

　patienceが小さいと鞍点にハマってしまうかどうかに大きく左右され、運次第になってしまうということでしょうか。それぞれ1回の実験だけではなんとも言えないという気もします。optimizerとの相性の問題だとするとかなり大変なことだなと思えるのですが、何はともあれもっと実験を重ねてみるしかなさそうです。

AtCoderRegularContest095 参加ログ

結果

　C,D,Eの3完で112位。後述するがE問題はほぼ不正のような解き方をしている。高順位となったが実力ではない。

　今回の結果によって青コーダーになれてしまったが、今後も精進を重ねていかなければいきたい。

C問題

　配列Aを違う配列BにコピーしておいてBをソートし、各A[i]に対してB[N / 2]かB[N / 2 - 1]を出力していけばいいだろうというところまで考えてコードを書き始め、条件分岐はサンプルに合うようにした。こういうところを最後まで考え切ってから実装し始めるか、サンプルに頼るかは悩むところ。なんとかWAなく4分50秒でAC。

D問題

　知識として、nに対してコンビネーションが大きくなるのはだいたいn/2個選ぶときであるというのは知っていたが、nに最大のものを選んでいいということに気づくのがちょっと遅れた。それさえわかってしまえば、と思って2分探索で出したがWA。別に10の5乗くらいなら全部舐めてしまえばいいなと気づいて21分41秒でAC。もうちょっとスマートに解いていきたい。

E問題

E: 必要条件がんばって書いて投げたら1ケースだけWAだったので、assertでHを二分探索してREとWAの切り替わりからHを特定して、そのケースだけNOを出力（最悪）

— はむこ (@hamko_intel) 2018年4月14日

　上の人と同じことをした。

　各操作において、行・列についてどの文字が何個含まれるようなものがあるかということは変わらない。よってそれをmapで取っておき、H,Wの偶奇に合わせてペアがうまく作れるか、そして真ん中が回文になるかという条件を考えた。上の通りこれは必要条件にすぎないのでダメだろうと思いつつ提出したらWAが1個だけだった。assertで範囲を絞りつつ、一応はなんで間違っているのかを考えていたが、最終的にはWAのケースを特定できてしまったのでそこだけ"NO"を出力するようにしてAC。6WAで74分17秒。まぁひどい解き方ですね。

　しかし他の人の提出を見ても乱択？ っぽいのとか焼きなましだったりとか、わりと想定とは違う解法がびゅんびゅん飛んでいるように思える。だからといってassert二分探索の罪が軽くなるわけではないが、まぁやっぱり制約が小さいといろいろ起きるのかなとも。

総括

　何はともあれ青コーダーになったのはなったのだ。これからはちゃんと青を安定させられるように頑張っていきたい。

将棋ウォーズで二段になったので採用している序盤作戦について書いてみた

ウォーズ二段になりました✌ pic.twitter.com/cHmysbJoUD

— sako@海底 (@kaitei_shogi) 2018年2月6日

　先日将棋ウォーズで二段になりました。将棋を始めたきっかけは電王戦FINALなので、将棋歴は約3年ということになりますね。ちょうど区切りも良いということで、今回は二段になったタイミングで採用していた序盤作戦についてまとめてみたいと思います。

　局面図もいくらか載せてみますが、手順とかは正確ではないことをご了承ください。

対居飛車

　相居飛車は基本的に横歩取り、角換わりを目指します。相手の変化によっては雁木や、その他力戦という感じになります。

1.角換わり

　角換わりは基本的に先手でも後手でも腰掛銀で４八金２九飛車の形を目指します。もちろん駒組の段階でも仕掛けを考えはしますが、大抵は図のように自陣を組んでから相手の形に応じて考えることになります。

　一番気分として楽なのは相手が５二金、８二飛車の形で４四歩と突いてくれている形(下図)で、これなら４五歩から仕掛けて良いんじゃないかなぁという感じです。形勢としては別に差はないとは思いますが、先攻できるならまぁ不満なしです。

　一番嫌なのは同型(下図)になることで、そうなるともう仕掛けがわからないので先手でも千日手やむなしの姿勢で、多少待機気味に玉を動かしたりして相手に隙ができるのを待つしかなくなります。しかし意外と千日手にはならないもので、こっちがバランス崩したり相手が崩したりしてなんだかんだ決着はつくものです。多分あまり僕の勝率は高くないと思います……。

　相手が早繰銀ならば腰掛けるのを急いで６五歩で相手の銀を追っ払う形(下図)を目指します。しかしこれ棒銀に切り替えられたりしたときにちゃんと受かるのかは自信がありません。

2. 横歩取り

　横歩取りは先手なら勇気流、後手なら斎藤流を目指します。といっても特に研究しているわけではないので、形とか狙い筋だけをちょっと真似している程度ですね。

　当然、勇気流は相手にやられることもあって、その時には飛車をぶつける作戦(下図)をやっています。これはプロで前例があったやつで、初出がどの対局かは知りませんが僕が記憶しているのは去年の羽生-村山戦ですね。一度だけ40手くらいこの前例をなぞりあう展開になったことがあり、その時は僕が先に手順を忘れていて負けにしたので、特に記憶に残っていますね。

　後手では斎藤流(下図)を目指します。斎藤流は神崎蘭子さんの将棋グリモワールを読んで知ったもので、まだちゃんと変化とかを全部覚えているわけではないんですが相手よりは多少知識はあって有利かなぁというくらいです。

　横歩取りの後手を持っていて気になるのはときどき８七歩と受けるのが早い(下図)人がいることですね。これは一応２四飛と回れば先手は歩で謝るしかなくて多少指しやすいと思っているんですが、まぁめちゃくちゃ有利というわけでもありませんか。

3.対雁木

　最近はプロの影響なのか、相手が角道を止めてくる居飛車力戦みたいな形がちょっと増えた気がします。しかしこれは叡王戦本戦の丸山-小林戦のように船囲い+早繰銀というような形にすれば互角以上の形勢で先攻できる(下図)ことが多いので特に不満はないという感じですかね。

　これは銀を２六と４六のどっちにあがるべきなのかなぁとかちょっと迷いますが、うーんまぁよくわかりません。

対振り飛車

　対振り飛車では対抗形が苦手なので相振り飛車を目指すようにしています。特に向飛車に振って相居飛車の左右反転した局面としてとらえていきたいところです。手数の関係で相振りにしにくい先手の時だけはちょっと対抗形も指すように変えつつあるタイミングで二段になりました。

4.対四間飛車

　先手だと3手目に２六歩と突いてしまうのが相振りを目指すうえでネックとなります。特に最近は雁木が増えたこともあって、角と左銀だけ動かされると雁木か四間飛車か判別できないことが多いく、困りどころです。雁木には居飛車を、四間飛車には相振りをやりたいのですが、どちらでも対応できるようにしても下図くらいが限界なので最近は諦めて対抗形をやるようにしています。２五歩まで指してしまうと相振りにはしづらい気がしているのですが、２六歩は許容しているのに一貫性がないかもしれません。

　とりあえず最近の対四間飛車先手番では対抗形、急戦を目指します。穴熊はさっぱり得意ではないので急戦で頑張ります。よくやるのは下図のような形で、飛車角銀桂でなんとか攻めていきたいところですが、やっぱり自玉が薄くて大変なことが多いですね。

　後手だとほぼ相振りにします。これは８四歩の一手を省略できることが多いからです(下図)。しかし雁木に警戒しつつの駒組となるので、厳密には相手に上手くやられると不利な展開になる気がしています。

　具体的には相手に囲いよりも攻めを重視されると嫌で、下の局面は５五銀が見えてても受からないような気がします。しかし個人的な印象としてはそこまでこうやられる頻度は高くなく、四間飛車を指すような人はあまりこういうことはしない性格なのかな……？ とか思います。

5.対三間飛車

　あまり三間飛車には当たらない気がしているんですが、結構やられて嫌な作戦ではあります。大抵は対四間飛車と同じように先手なら対抗形、後手では相振りを目指します。しかし後手で対四間飛車と同じように相振りを目指すと時々いきなり突っかけらて、そこでなんとなく７二飛車とぶつけるのが何度か経験した局面です(下図)。

　別に飛車交換する一手ではないと思いますが、今までのところは交換になることが多い感じですかね。こうなれば互いに飛車を持ち合っての戦いになるのでまぁ対抗形よりは好みの将棋になります。

6.対中飛車

　対中飛車でも相手の態度が早いなら相振り、そうでなかったら対抗形という感じになっています。対抗形になるのは大抵相手の後手ゴキゲン中飛車なので主に超速で対応します。対中飛車の相振りはツノ銀雁木のような形にしていきます(下図)。他のよくわからない相振りよりは隙がない感じに組めることが多く、これはこれで一局になっているという気がします。

7.その他振り飛車

　角交換振り飛車は対抗形にすることが多いのですが苦手な戦型ですね。

　向飛車も逆棒銀の筋をそのまま食らって負けるということを何度かやらかしている気がします。

　この辺のちょっと遭遇頻度が低い振り飛車は苦手で、対抗形の指し方、考え方が根本的に身についていないという気がします。

終わりに

　特に相居飛車ではプロが指す戦型を真似をするというのが僕の好みとなっています。対抗形はよくわからなくて変な相振りに逃げたりしていますが、三段を目指すとしたら対抗形をきちんと見つめ直す機会が必要なのだろうなぁと感じているところです。

　三段になれる気はさっぱりしないのですが、初段になったときも二段になれる気は全くしなかったなぁということを思い出すとそういうものなのかもしれません。

AtCoder Beginner Contest 079 参加ログ

結果

　0WA、56:02で全完の374位だった。C,D問題でしっかり時間かかってしまうのでまだまだ実力不足だ。

A問題

　stringで受けて判定するだけ。まぁしかし2分かかった。

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

int main()
{
    string s;
    cin >> s;
    if (s[1] != s[2]) {
        cout << "No" << endl;
    } else {
        if (s[0] == s[1] || s[2] == s[3]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

B問題

　なんか無駄に再帰を書いて、時間がかかるのでメモ化するという遠回りをした。普通にforループで良かったじゃん……。4分くらいかかった。

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

vector<long long> memo;

long long ans(int n) {
    if (n == 0) {
        return 2;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    return memo[n] = ans(n - 1) + ans(n - 2);
}

int main()
{
    int N;
    cin >> N;
    memo.resize(N + 1);
    for (int i = 0; i <= N; i++) {
        memo[i] = -1;
    }
    cout << ans(N) << endl;
}

C問題

　わざわざdfsなる関数を書いて全探索しにいく。8通りくらいならif文全列挙でいいっていうの、気が付かないんだよなぁ。dfs書くのに手間取って13分くらいかかった。

#include <bits/stdc++.h>
using namespace std;
string ans;
int a[4];

void dfs(int pos, string str, int sum) {
    if (pos == 4) {
        if (sum == 7) {
            ans = str;
        }
        return;
    }
    dfs(pos + 1, str + '+', sum + a[pos]);
    dfs(pos + 1, str + '-', sum - a[pos]);
};

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < 4; i++) {
        a[i] = s[i] - '0';
    }
    dfs(1, "", a[0]);

    for (int i = 0; i < 3; ++i) {
        cout << s[i] << ans[i];
    }
    cout << s[3] << "=7" << endl;
}

D問題

　ダイクストラ法っぽくやっていくことしか頭に浮かばなくて、しかし普通とは逆向き？ なのでかなり手こずる。35分以上かかってしまった。Nが小さいからワーシャルフロイドで一瞬なのになぁ。ただアルゴリズムを知っているだけで適切なタイミングで使えていない。もっと修行を積まないと。

　終わった番号を詰めていくvectorのendも使ってないので不要だろうし、ダイクストラ法っぽいものとして見たとしても出来がいいコードではない。最近まともに競技プログラミングやっていなかった分がそのまま表れているという感じ。電王トーナメントも終わったので、ちょっとは頑張っていきたい。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<int> > c(10, vector<int>(10, 0)), a(H, vector<int>(W, 0));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> c[i][j];
        }
    }
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            cin >> a[h][w];
        }
    }

    vector<int> min_cost(10, INT_MAX);
    vector<int> start, end;
    min_cost[1] = 0;
    for (int i = 0; i <= 9; i++) {
        if (i != 1) { 
            start.push_back(i);
        }
        min_cost[i] = c[i][1];
    }
    while (end.size() != 9) {
        int min_index = -1, min_value = INT_MAX;
        for (int i : start) {
            if (min_cost[i] < min_value) {
                min_value = min_cost[i];
                min_index = i;
            }
        }

        start.erase(find(start.begin(), start.end(), min_index));
        end.push_back(min_index);
        for (int i : start) {
            min_cost[i] = min(min_cost[i], min_cost[min_index] + c[i][min_index]);
        }
    }

    long long ans = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (a[h][w] == -1) {
                continue;
            }
            ans += min_cost[a[h][w]];
        }
    }
    cout << ans << endl;
}

コンピュータ将棋における勾配降下法の最適化アルゴリズム

　自分用メモ

　勾配降下法を用いてパラメータを更新していくときに、どういった更新式を使えばいいのか気になってきたのでいくつかのソフトについて調べてみた。

　ここではニューラルネットワークは除いて、3駒関係や2駒関係の特徴量を使っているソフトに絞って調べた。ボナンザメソッドと自己対局からの学習とでは事情が違う可能性もあるが、とりあえずは気にしないことにした。

　まず更新式の基本についてはここにあることで学んだ。このページの「どのオプティマイザを使うべき？」のところでは、スパースなデータに対しては学習率を適応させていく手法が良いとあって、つまりはAdaGradとかその派生形のことだと思う。3駒関係等の学習はスパースなので、それらの中から選んでいくことになるんだろう。

やねうら王

2017年11月16日時点では

// ----------------------
//        更新式
// ----------------------

// AdaGrad。これが安定しているのでお勧め。
// #define ADA_GRAD_UPDATE

// 勾配の符号だけ見るSGD。省メモリで済むが精度は…。
// #define SGD_UPDATE

// RMSProp風のAdaGrad
// #define ADA_PROP_UPDATE

という記述がある。RMSProp風のAdaGradというのはよくわからないけど、とりあえずいろいろ試されたらしい雰囲気は見て取れる。AdaGradはどんどん更新量が小さくなっていってしまうのが気になるんだけど、それが一番安定しているのか。

技巧

learning.ccによるとRMSPropを使っているみたいだ。

// 学習率の設定（RMSpropの設定）
constexpr float kRmsPropStepRate = 5.0f; // １回の更新で、最大何点まで各パラメータを動かすか
constexpr float kRmsPropDecay = 0.9975f; // どの程度過去の勾配を重視するか（大きいほど過去の勾配を重視）
constexpr float kRmsPropEpsilon = 1e-4f; // ゼロ除算を防止するために分母に加算される、非常に小さな数

とあるが、kRmsPropStepRateに対するコメントがよくわからない。単なる学習率ではない？ 勾配が正規化されているのだろうか(そんなことしていいのか？)

2017/11/20 追記。僕が勘違いしていた。AdaGradやRMSPropの挙動を全然理解していなかった。

また気になるところとしては、勾配の二乗和の指数移動平均を取っていくところで

  // 更新幅の設定（RMSprop）
    a = a * kRmsPropDecay + (g * g);
    const PackedWeight eta = kRmsPropStepRate / (a + kRmsPropEpsilon).apply(std::sqrt);

となっているのだが、RMSProp等の解説でよく見る感じでは
と計算しているのが多い気がする(内分を取っている？)。今回の勾配の二乗に(1 - kRmsPropDecy)をかけるかどうかというのは別に本質的な違いではない(展開してみると結局全体に(1 - kRmsPropDecay)かかるかどうかというだけな気がする)ようにも思えるけど、一番最初の更新でちょうどgが打ち消されるのがわかりやすいので技巧のようにするのが良さそうか。

　いやでも数式的な意味としてはかける方がそれっぽい気がする。最初の一回だけは特別扱いした方が良さそう？ 指数移動平均でググるととか書いてある。3なのはちょっとわからないけど、最初は特別視して良さそう(面倒か？)

Apery

learner.hppはあるけどlearner.cppはなくてよくわからない。learner.hppも別に学習用のクラスとかが定義されているわけじゃないし、何か別のファイルにあるのか公開されてないだけかな。

読み太

まだ電王トーナメントのソースは更新されてなくてWCSC27時点のコードだけどSGDとAdaGradが実装されているのは確認できた。読み太はどの程度やねうら王に近いのかがよくわかっていない。

shogi686

SDT5バージョンによるとAdaGradを使っているらしい。

その他

もうコンピュータ将棋からは引退されているけどAkiさんもAdaGradをすすめる記事を書いていた。ここの

線形モデルの学習に限った話。(特に、コンピュータ将棋の評価関数、進行度、実現確率とかでの経験に基づく話。)
非線形モデル(というかNN)の場合は挙動がそれほど素直じゃないので、指数移動平均を使うアルゴリズム(AdamとかRMSPropとか)の方が合っていると思う。

というのが気になる記述で、指数移動平均を使うかどうかっていうのはそこが問題だったのか。

疑問点など

　AdaGradは確かに挙動がわかりやすそうで扱いは楽に思える。しかし更新量がどんどん減少してしまうのがちょっと気になるっちゃ気になるところで、ある程度学習した重みに対して学習をしなおす場合、勾配の二乗和を前のものから取ってくるのと0から始めるのでも大きく結果が変わりそうなのがなんかしっくりこない。

　その点はRMSPropの方がまだいいかなぁという気もするんだけど、技巧しか採用していないというのがなんとも。逆に言えばあの技巧が採用しているんだからまったく合わない方法ではないんだろうけど。

　2駒と3駒の違いとか、自己対戦からの学習かそうでないかの違いなどが影響しているのだろうか。よくわからない。とんでもない高次元空間の関数を最適化しようとしているわけで、常識がどの程度通用するのかもわからない。

まとめ

　AdaGradでいいのでは。

コメントによる指摘(2017/11/19追記)

　darumaさんからAperyのボナメソ及びelmo絞り、nozomi、Squirrelについての情報も提供していただいたので下方のコメントも参照のこと。

CODE FESTIVAL 2017 予選B 参加ログ

結果

　A,B問題2完の741位。うーむC問題が解けないのはちょっと苦しいところか。精進が足りない。レート1535→1516(-19)

A問題

　後ろから8文字を削除するだけ。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string S;
    cin >> S;
    cout << S.substr(0, S.size() - 8) << endl;
}

B問題

　mapで各難易度について必要数と作成済数を記録していけば解けると思ったんだけど、先に必要な数を引いていくとREが出てしまった。mapだからデフォルトは0で、引いたらなにかおかしいことがあるのかな？ ちょっとよくわからなかったけど先に足すようにすれば通った。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    vector<int> D(N);
    map<int, int> mp;
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
        mp[D[i]]++;
    }
    int M;
    cin >> M;
    vector<int> T(N);
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
        if (mp[T[i]] == 0) {
            cout << "NO" << endl;
            return 0;
        }
        mp[T[i]]--;
    }
 
    cout << "YES" << endl;
}

C問題

　これが全然わからなかった。考察のとっかかりすらうまくつかめなくて、座っているだけの時間が多くなってしまった。明らかにN, Mが大きいので、まともな最短経路を求めてなんとかしていくわけではないだろうとは思った。そして、頂点の偶奇がちょっと怪しいかと思ってコードを投げてみたりもしたんだけど、片方だけ通すことすらできなかった。

　解説を読んだけど、まず2部グラフという用語の定義すらちゃんとわかってなかった。知識が圧倒的に足りない。