utsubo’s blog

競技プログラミングとか.

競技プログラミングをだらだら5年くらいやってみて

特に対象読者も決めていないクソポエムです。
思いついたことから書いてるので、まとまっていません。

競技プログラミング自体の説明はこの辺を読んでください。
競技プログラミング - Wikipedia

竸プロは青春

私も途中全くやってない期間とかはあるものの大学時代のかなりの時間を竸プロに捧げたと思います。さすがにゲームとかニコ動の時間の方が長いですけどね。

卒業という良い節目なので、竸プロを通して振り返り、何を学んだかなどをだらだら書こうと思います。

竸プロとの出会い

私が竸プロを始めたのは学部1年の後期くらいからです。
その頃は今ほど竸プロは知られてなく日本のコンテストサイトとして有名なAtCoderがちょうど出来た頃だと思います。

当時の私は、プログラミングに関して授業レベルでは困ることはなかったのですが、外に出たら通用しないのだろうなと漠然とした不安を抱えていました。
そこで、目標にするためと自分のレベル感を測るために、プログラミング系のコンテストを漁っていたときに見つけたのが、竸プロでした。U-20プロコンとかも出てみたかったのですが、アプリを作り切るのは私には無理でした。
(余談ですが、プログラミングでやりたいことがないなら、とりあえず自分の興味に応じてコンテストに出るのが良いと思います。竸プロに限らず、セキュリティ、データ分析、障害対応とか色々な分野のものがあるのでね。http://cocodrips.hateblo.jp/entry/2015/10/11/114212)

初出場コンテストはtopcoderなのですが、レートは942でした。
全体のレート平均のちょい上くらいなので、初めてでこれは結構自分賢いんちゃうと思ったのと同時に、僕はこの程度じゃないだろ(?)と続けるしかなくなりました。
“ある種の”頭の良さを評価されるので、闇が深い。
普通に数学パズルとしても好きだったので、長く続けることになりましたね。

ここまで長続きした趣味は、中学時代にハマってたゲーム以来なのですが、要因として初期段階で周りにやってる人がいなかったのも大きかったと思います。
プライドだけ無駄に高い人間なので、大学とかで同時期に始めた人がいて、負けてたら続けてないですね。おそらく。ライバルがいてめっちゃ成長したって人もいるし、なんとも言えないけど。

自分とのマッチングや周りの環境など色々あるので、この時期に自分に合ったものと出会えたのはなかなか幸運だったなと思います。

それからしばらく

滑り出しはまずまずだったものの、それから1年くらいはレートが全く上がりませんでした。あまりに悔しくてコンテスト終了後に泣いた覚えがあったりなかったり。

この1年くらいが一番情熱があった時期で、再帰を理解できるまで散歩とか、深夜でもコンテストに出るとか、授業中も問題を解くとかやってました。なんだかんだ”やってる感”があって楽しかった。

やってる感に浸って、コンテスト中に解けなかった問題を解き切らずに放置していたのが、伸びなかった原因だと思っています。復習が嫌いなので…
体系的に勉強する必要はないけど、復習はしっかりすべきでしたね。

現状のレベルでは、解かなくて良い難しい問題も存在して、その辺の見極めが難しいですね。
最近は、公開されている解説を読んで意味不明な問題は飛ばす方針でやっています。(この辺は数学系の本も同じだと思っていて、難しすぎる本は飛ばします。)

数年振りに解いてみると解ける問題もあったりしたので、諦めは結構肝心だと感じます。
遮二無二解くことより、適切な難易度の問題を解くのが重要だと思うのですが、適切な難易度の問題を探すには、結局沢山解かないといけない…

思考法

一応、だらだら続けている内にtopcoder, Codeforces, AtCoderでは青コーダー(中堅くらいの実力?)になれました。
これまでに解いた問題数は、900問くらいみたいです。

続ける中でアルゴリズムやデータ構造の知識が増えたのはもちろんなのですが、雑に言うと昔より頭が良くなったと感じます。
頭の良さにもいくつかあると思うのですが、特に問題を整理する力、考察力が向上したと思っています。

私は、下の2つプロセスを意識して問題を解いています。
① 問題の性質を書き出す
② 性質の考察を進める、複数の性質を組み合わせて解けないか考える

①については、例えば、「判定問題として考えると…」、「この部分は貪欲に解けるから…」、「小問題が解けていると仮定すると…」とかです。
こういう具体的なアルゴリズムにまでは至らない考察や、”部分的に問題を解いていく”のが、少し得意になったと思います。前は一気に解ければ解ける、そうでなければ解けないみたいな感じだったので。

②は、問題が複雑になってくると必要だと感じています。難易度としては、AtCoderで500点くらい、これ以上難しいと私も解けないんですけどね。

部分的に問題を解いた後に、全体が解けるように穴を埋めていきます。穴を埋めるには、部分的な考察を広げていく中で、不足している考察をひらめくしかないと思っています。
天啓が来ないで行き詰まると「ここまでは解けてるから考えなくて良い。」みたいな独り言をよく吐きます。考える必要のある部分に集中してるんですかね。

この辺の反復練習から、どこまで理解できていて何を考えないといけないのか整理する能力が上がったと思います。
僕はこれが非常に苦手で既知の部分を何度も考えて空転することがいまだに多いです。

まず、これが苦手だとに自覚したのは最近で、こういうのは得意だと思っていたので、自覚できただけ良いと思っています。
競プロに限らず、大きな問題に直面した時に、小問題に分割できず、フリーズしてしまう癖があるので矯正していきたいですね。

竸プロerは自己評価が低い

に関して二言三言。

知性で殴り合ってる感が強く、レートという形で定量的に能力が測れてしまう竸プロなので、卑屈になってしまうのかなぁと思っています。レート以前に解けなかった問題が異常な速さで大勢に解かれていると悲しいし、悔しいですよね。

定量化しないでいた自分の弱さとか無能さと向き合うことになるので、私のような自分のことをそこそこ賢いと思っている人間には、ちょっとつらい。

こんなのやってるの頭が良い人しかいないんだから、ヘコむ必要は全くないのですが、足ることを知るというのは難しいですね。

悔しさ駆動精進も捗るので、卑下の全部が全部悪いとは思いませんが、ほどほどにね。これは自戒も込めて。

学生を終えて

学生時代を振り返ると競プロがなければ本当に何もせず終えていそうだったなぁと思います。
会社見学やインターン、オンサイトのコンテストなど競プロ経由で様々経験させて頂きました。
学内でLTやったり、ハッカソンやったりしたけど、それも結局、”私は”競プロを通してそういうものがあると知ったのでね。
果ては就活も競プロのおかげと言って過言ではない。

振り返ると、競プロにもっとドハマりした方が良かったかなという想いと、色々と技術的な事やそれ以外も広く浅くやったこのままでもまぁ悪くなかったという想いが半々です。
けど、青コーダー止まりであれば、もう一つ何かしらで青コーダー相当の武器を作った方が気持ち的にも有利に進められそうだったなぁというのが就活等々を終えての所感です。(技術力に限らずコミュ力でもアピール力でも本当に何でも良いのですが)

これから社会人になりますが、学んだことを活かしつつ、けどこだわり過ぎず、バランス感覚を持って視野を広く、色々やっていきたいと思います。

まだ、何か吐き出しきれてないものが見つかれば追記します。
以上、読んでいただきありがとうございました。

P.S.
競プロに情熱ある風でここまで書いてきましたが、最近は熱も冷めてきて何か他のおもちゃを探しているところです。

2018年振り返りと2019年の目標

はじめに

振り返りの時期が来たので振り返ろうと思います.
年々年間記事数が減っていて,そのうち振り返りと目標しか中身がなくなりそう.

2018年振り返り

1~3月

就活に苦しんでいた.自分が何もかも中途半端なのを呪った.

あとは,昨年に引き続き学内でライトニングトークとか開いたりしてた.
コンテンツはしっかりしていたと思うがあんまり人は来なかった.
まぁ地道に盛り上げていきたいですね.

4~6月

この辺で就職先を決めた.
周りが終わりかけてきて焦って就活を辞めたのだが,
今落ち着いて考えても雰囲気は好きだし,まぁ間違ってた選択ではないと思う(働いてみないとわからないが).
単純に能力不足感が否めないので,死なないように勉強していきたい.

あとRubyのMatzさんの特別講演とか聞きに行ったり,
自分のキャリアパスについて割と考える月だった.

7~8月

MUJINのコンテストに出たら会社見学させて貰えた.
ご飯が美味しかった(小並感).英語できるようになりたい.

夏コミ3日目にサークル参加した.
2回目の参加だったので,落ち着いて参加できた.
冬コミも参加登録したが,地獄を見ることになることをこのときはまだ知らない.

9月

某大の松尾研の強化学習講座に出ていた.
講座とかに出てもちゃんと復習しないと何も身につかねぇなと言う感じ(当たり前)

10月

はじめての国際会議(in 宮崎)に参加した.
発表自体は不安でかなり練習したので問題なかったが,質疑応答がゴミだった.

帰ってきて落ち着く暇なく,2月開催の国際会議に提出する原稿を書いていた.
これも無事acceptedされたので,来年ギリシャに行けるようになった.嬉しい.

11~12月

冬コミの原稿と修論で激焦り.
冬コミは準備がギリギリになってしまい配送が間に合うか怪しい(12/30現在)
なんとか届いてくれー

修論は余裕を持って仕上げようと思っていたのに,まるでダメ.
早く終えたい.

まとめ

2018年の目標と達成度はこんな感じ

1~4月:研究と機械学習の勉強をメインに. → △

  • 機械学習は何かしらの成果物をブログに上げる. → ✕
  • 研究は海外学会発表に行く → ○

5~8月:英語ガチ勢になりたい(夏に海外インターンとか行ってみたいので) → ✕

  • TOEIC 800点以上 → TOEICを受けていない

9~12月:研究のまとめとやりたい勉強. → ○

まずまず.
やるべきことはしっかりやれた感がある.

2019年の目標

  • 競プロと英語と数学の勉強は無理のないペースで続ける
  • 強化学習をじっくり勉強する
  • 社会人を生き延びる
  • 何か新しいことに挑戦する

一つずつ焦らず無理のないペースでゆっくり自分のできることを増やしていきたい.

最大フロー問題(循環フロー問題)の双対をとる

はじめに

近似アルゴリズム(V.V.ヴァジラーニ)の12章に最大フロー問題とその双対問題が載っているのだが、どのように変形したらその双対問題の式が得られるのか結構悩んだ。
そこで、未来の自分のために最大フロー問題から双対問題を導出する過程をまとめておく。

最大フロー問題と双対問題

最大フロー問題についてはリンク最大フロー問題 - Wikipediaを参照。

まず、近似アルゴリズム(V.V.ヴァジラーニ)では下記のように定式化されている。
一般的な最大フロー問題に、 tから始点 sへ容量が無限大の仮想的な辺を加え、循環フロー問題として考えている。
そうすることで、 sでもフロー保存則が成り立つ.また、このとき目的関数では、仮想的な辺を流れるフロー f_{ts}を最大にすることになる.

f:id:utsubo_21:20180518230556p:plain:w600

制約式の意味は

  1. 辺を流れるフロー量が容量を超えない。
  2. フロー保存則(頂点に入ってくるフロー量より出ていく量の方が大きい)

これの双対を取ると下式になるとのこと。

f:id:utsubo_21:20180518230853p:plain:w600


実際に主問題を式変形をして、双対問題を得てみる。

双対をとる

まず、双対問題とは主(最大化)問題の上界を求める問題といえる(詳しくは後述)。
主問題の制約式の1つ目の両辺に d_{ij}、2つ目の両辺に p_iを掛ける。

f:id:utsubo_21:20180518231614p:plain:w600

(3a)と(3b)の和は、 d_{ij} p_iの設定によっては、主問題の上界となる。
この上界を d_{ij} p_iを上手く設定して最小化するのが、双対問題である。
(4) = (3a) + (3b)

f:id:utsubo_21:20180520120544p:plain:w600

上式が上界になる条件は「(4)左辺の f_{ij}の係数の和が、主問題の目的関数の f_{ij}の係数より大きい」であり、これが双対問題の制約式となる。

(4)(=(3a)+(3b))の左辺の f_{i,j}の係数について考える。

(3a)で f_{ij}は、 d_{ij}f_{ij}がある。

(3b)では、頂点 iと頂点 jについての不等式で必ず現れる(元はフロー保存則を表す式なので)。
頂点 jには、フロー f_{ij}が流れこむはずなので、 p_j f_{ij}が必ず存在し、
頂点 iには、フロー f_{ij}が出ていくはずなので、 -p_i f_{ij}がある。

よって、双対問題の制約式は、
f:id:utsubo_21:20180518233809p:plain:w300
となる。(主問題の目的関数に f_{ts} + \sum{0 f_{ij}}があると考えれば右辺はわかる。)

目的関数は(4)の右辺を最小化することであり、制約式は(5)なので整理すると、
f:id:utsubo_21:20180518234427p:plain:w600

ここで、目的関数では、 c_{ts} d_{ts}が出てくるが、
 c_{ts}は無限の容量を持つと定義したので、 d_{ts}は0以外の値を取れないことが自明にわかる。
そのため、最初に出てきた双対問題の式とこの式は一致する。

双対問題は主問題の下界(上界)を求める問題

例えば、下記の最大化問題で考える。
f:id:utsubo_21:20180520124631p:plain:w400


この問題の制約式の和を取れば、
f:id:utsubo_21:20180520130419p:plain:w300

上式の左辺は、係数の関係から最大化問題の目的関数より大きい。( x_iは非負なため)
f:id:utsubo_21:20180520130603p:plain:w250

よって、制約式の関係から、解が 20で上から抑えられることがわかった。

もう少し一般化して考え、制約式の両辺にそれぞれ非負な数 y_1,y_2を掛けた和を取る。
f:id:utsubo_21:20180520125315p:plain

 12y_1 + 8y_2が上界になるのは、 x_iの係数の関係により、下式を満たすときである。
f:id:utsubo_21:20180520125606p:plain:w150

この条件を満たした上で y_iを調整することで、 12y_1 + 8y_2を最小化すれば、上界を最適解に近づけることができる。(実際は最適解と一致する)
それが双対問題である。
f:id:utsubo_21:20180520130042p:plain:w300

あとがき

間違っているところ多そうなので突っ込み貰えると嬉しいです。
双対の取り方とその意味がやっとわかりました。
いちいちLaTeXiTで数式の画像を生成して貼って、さらにサイズ調整とか面倒だったので、LaTeXで全部書いてpdfで上げればよかったと思いました。

「Linuxのしくみ」を読んで

はじめに

gihyo.jp
を読みました。

感想

低レイヤ寄りのことを知りたかったので読み始めました。
基本的な用語でも分かってないことがあったので為になりました。
この仕組みで複雑なアプリケーションが動いてるの凄すぎて気持ち悪い。

7章ぐらいから飽きてきてあんまりきちんと読めていないので、そのうち読み直します。
次は、OSの作り方でも読もうかと思います。

メモ

ただのメモ。

1,2章
3章 プロセス管理
4章 プロセススケジューラ
  • スループットとレイテンシ
  • プロセスのスケジューリング(niceで優先度設定ができる)
5章 メモリ管理
  • taskset(cpu指定(それ以外にも色々機能がありそう)),time,ps(時間計測,ユーザ/カーネルモード)
  • OOM killer(Out Of Memory)(メモリが足りなくなった時に適当に要らなそうなやつをkillする機能、vm.panic_on_oom)
  • プロセス毎に 物理メモリに割り当て→ページテーブル(カーネルのメモリ上)作成(mmap)
  • mmap()でページ単位で確保→mallocは内部でそれを切りわけて使っている
  • 無駄なメモリ確保を防ぐデマンドページング(カーネルが初アクセス時に物理メモリへ割り当てる)
  • Copy On Writeとは何か(fork()システムコールの時に仮想記憶が役に立っている、fork後が書き換えられた時にコピーする)
  • OOMの救済にSwap、メモリ↔ストレージのスワップ領域
  • メジャーフォールト(ストレージへのアクセスが発生)←こっちが重い、マイナーフォールト(ストレージへはアクセスしない)
  • ヒュージページ(ページテーブルのメモリを減らす機構、まとめるページ単位を大きくまとめる)
  • トランスペアレントヒュージページ(自動でヒュージページと通常モードを切り替える、Ubuntu16.04ではデフォで有効)
6章 記憶階層
  • ライトバック方式(所定のタイミングでバックグラウンドでメモリに書き込む)、ライトスルー方式(キャッシュラインがダーティになった瞬間にメモリに書き込む)
  • L3キャッシュはCPUで共有してたりする
  • 参照の局所性(近い場所の又近い時間でデータにアクセスすることが多いので基本的にキャッシュが働く)
  • キャッシュでは、物理メモリのページテーブル参照は高速化されない→Translation Lookaside BufferというCPUの機能がある
  • トランスレーション・ルックアサイド・バッファ - Wikipedia MMUがやってるらしい
  • ページキャッシュ(メモリ↔ストレージ)の話、こっちはキャッシュライン単位でなくページ単位で扱う(キャッシュメモリはCPU↔キャッシュメモリ↔メモリ)
  • ダーティページのライトバック周期はvm.dirty_writeback_centisecsパラメータで設定できる
  • or vm.dirty_background_bytesの割合が超えた時ライトバック発生
  • ハイパースレッド機能(よく分からんから後で調べる)
7章 ファイルシステム
  • 容量制限=クォータ(ディレクトリ、ユーザ、サブボリューム等ごとに制限が掛けれる)
  • ファイルシステムの不整合を防ぐ方式→ジャーナリングトランザクションみたいな)、コピーオンライト(アホほどコピーとる)
  • それでも駄目な時はfsck、だけど時間かかる割に望んだ結果にならないことが多い
  • キャラクタデバイス、ブロックデバイスとは?(よく分かってないから後で調べる)
  • tmpfs、メモリ上のファイルシステム、凄そうだけどこれもよく理解できてない
  • ネットワークファイルシステムWindows→cifs、Linuxnfs
  • プロセスの情報は/proc以下にマウントされたprocfsで分かる(top,freeはここから採取)
  • sysfsはprocfsの濫用を防ぐためにできた
  • cgroupでリソース(CPU、メモリ)使用量に制限を掛けられる
  • Btrfs、ファイルシステムのすごいやつらしい
8章 ストレージデバイス
  • I/Oスケジューラ(連続したセクタから読み出す)、先読み
  • SSDは電気的な処理なので読み書きが早い

あとでやる

  • sarの使い方をまとめる
  • ふつうのLinuxを読む
  • OSの作り方を読む

2017年振り返りと2018年の目標

はじめに

最近,何も書いていないなと思ったらもう年末だったので,振り返りでもしようと思います.

2017年の目標と達成度

年始にふんわり立てていた目標と達成度.

  • 競プロ:週に1問 → 問題を解くどころかコンテストにもほぼ出ていない.
  • 英語:TOEIC730点 → TOEICを受けていない
  • その他:機械学習コミケに出す → 機械学習◯、コミケ

2017年の感想

  • 割りと講義とかバイトとか遊び等で忙しくて,思うように動けなかった.
    • 気づいたら年末,年々年を取るのが早くなる
  • インターンにいくつか参加するとともに,比較的暇な学部3,4年生の内にもっと行くべきだったと思った.
    • 修士だと就活を視野に入れてインターンを選ばないといけないし,落ちた時に2回目のチャレンジができないため.
  • 学部生にやってきたことを使って,アウトプットをしていたなぁという感じ.
  • やりたいことを口にしていると協力してくれる人が結構いる.

2018年の目標

1~4月:研究と機械学習の勉強をメインに.

  • 機械学習は何かしらの成果物をブログに上げる.
  • 研究は海外学会発表に行く

5~8月:英語ガチ勢になりたい(夏に海外インターンとか行ってみたいので)

9~12月:研究のまとめとやりたい勉強.

Googleカレンダーを見ながら振り返り

1月

適当な学会に出す論文を書いていた.
あと,卒論も書いてたが,ほとんど前に書いたものを再利用したので,あんまやった気がしない.
卒論の発表にほとんど練習しないで望んだら,ぐだぐだ過ぎて怒られるかと思ったが,大丈夫だった.

そういえば,1~3月ぐらいまで36.8~37.5ぐらいの微熱が続いて辛かった.(医者に数回行ったが原因不明,恐らく副鼻腔炎
それとは別に顎のあたりにしこりがあって,微熱も続くし,死ぬんじゃないかと思った.(実際は,微熱とは関係なくガマ腫というらしい)

2月

毎週遊びの予定が入っているので,遊び呆けていた模様.(微熱が治らなかった原因の1つ)

大阪にも行った.夜行バス+微熱で死にそうだった.

3月

1月に出した論文に一応査読が付いていたので,直し.

先生のコネでF研究所で3週間のインターンシップ
内容は,詳しくはNDAで言えないが,仮想ネットワークの可視化してた.
知識0で行ったら,初日の説明会で知らない単語が無限に出てきてめちゃ焦ったが,割りとなんとかなった.まあまあ楽しかった.

3月末に卒業旅行で初の広島旅行に行った.
外国の方に「お前,日本人なのに広島も行ってないのかよ」みたいなこと言われたくなかったので,僕の希望で広島へ.
夜行バス+微熱で死にそうだった.

4月

何かをしてた形跡がない.3月まで疲れを癒やす1ヶ月.

5月

1月に投稿した奴のポスター発表のために北九州に行った(初めて本州以外の県に行った)
Yandex Algorithmの参加賞でTシャツ貰ってHappy:)

6~7月

インターンに数社落ちて悲しみにくれていた.
面接で落ちるの最高に精神に来る.

8月

コミケに初サークル参加.
友達4人と技術系記事の載った薄い本を書いた.僕はビットコインの仕組みについて書いてた(我ながら先見の明があると思う).
印刷所とか設営とか初めてなことだらけで大変だったけど,刷った30部が完売した時は感動だった.
冬コミも申し込んだけど,抽選漏れでした,残念!

9月

某社でインターン.やってきたことを評価してくれるし,かなり楽しかった.
初めて劇を見に行ったが,面白かった.

10~11月

アルバイトを新しく始めたら忙しくなってしまった.

DISCO presents Discovery Code Contestの本戦に出れた.
Ponanza開発者とプロ棋士の対談を聞きながら,もっと頑張らないといけないなと思っていた.

12月

学内でハッカソンを運営してた.小成功ぐらい.今後,大きくしていきたい.

Q-Learningで迷路を解く

はじめに

強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~

↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが,
読んでるだけで飽きてきたので,実際に実装してみました.
chainerRLとか使えば簡単にできるのだろうなと思いつつ,初めてなのでC++で適当に書きました.

Q-Learningとは?

詳しくは本を読むか,色々な人が解説記事を上げているのでそちらに.
ゼロからDeepまで学ぶ強化学習 - Qiita
強化学習で迷路を探索する - Qiita

方針

報酬 R(s_t,a_t)をゴールしたとき1,壁に移動したとき-1,その他0で設定.
探索する時の行動選択にε-greedyを用いていたのですが,上手く行かなかったため,
UCB1アルゴリズム*1を使って探索しました.

UCB1については下記リンク参照.
モンテカルロで二人ゲーム - ustimawのブログ

実装

実行環境
概要

競プロ形式で迷路を標準入力から読み込み.
高さH,幅Wの次の行から,各セルの情報が空白区切りで与えられる.(0:通路,1:壁,2:スタート,3:ゴール)

エピソード数(num_episodes=10000)の学習の後,1回テストが実行されます.

実行結果

テスト実行時の動画です.'x'が現在地を表しています.

Q-Learningの更新式についてメモ

説明できるほど理解できてないのですが一応.(中途半端かつ正確ではないです.)
状態 s_tの時行動 a_tを取った場合の価値関数 Q(s_t,a_t)がある.
 Q(s_t, a_t)を展開すると,期待報酬関数 Rと次ステップの価値関数 Q(s_{t+1},a_{t+1})の漸化式っぽくかける.

Q(s_t,a_t) = \sum γ^tR(s_t,a_t) = R(s_t,a_t) + γQ(s_{t+1},a_{t+1})


これを,Rイコールの式にすると,

R(s_t,a_t) = Q(s_t,a_t) - γQ(s_{t+1},a_{t+1})
となる.


報酬関数 R(s_t, a_t)を近似する関数 \hat{R}(s_t,a_t)と実際の報酬 r_tは,大体一致して欲しい.
そこで,誤差 \Delta R(s_t, a_t) \equiv \frac{1}{2} (r_t - \hat{R}(s_t,a_t))^2と定義し,これを最小化する.


最小化するように Q(s,a)を更新するために,TD法が提案されていて,これは大体勾配法.
TD法では, d = \frac{\partial \Delta R}{\partial \hat{Q}}として, \hat{Q}(s_t,a_t) = \hat{Q}(s_t,a_t) - \alpha dで更新.
 \alphaは学習率.


で, dは下式のように求まるので,
 d = \frac{\partial \Delta R}{\partial \hat{Q}} \propto -r + R(s,a)
近似価値関数は次の式で更新するといい感じになりそう.
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \hat{Q}(s_{t+1},a_{t+1}))

(正確にはここまでのQには肩に政策関数 \pi が乗ります.)


Q-Leaningでは
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \max_{a'}{\hat{Q}(s_{t+1},a'))}
で更新.

*1:雰囲気実装なので合ってない

IPアドレスを自動でGoogleスプレッドシートに書き込む(Windows10)

背景

学内や社内等のPCに接続したい時,IPアドレスが分からず困ることがしばしばあったので,*1
自動でIPアドレスGoogleスプレッドシートに書き込まれるようにしました.

構成

Windows 10 → Google Apps Script → Googleスプレッドシート
Google Apps Scriptが,Windows10からのGETに含まれるIPアドレスを受け取り,さらにGoogleスプレッドシートに書き込む

手順

サーバ側

まずは,GoogleスプレッドシートをGドライブから作成します.
この時,スプレッドシートのURLの{ここの文字列}部分がスプレッドシートのIDになっています.

https://docs.google.com/spreadsheets/d/{ここの文字列}/edit

次に,Google Apps Scriptを書いていきます.
Gドライブの右上の"新規"→"その他"→"Google Apps Script"で新規作成.

function doGet(e) {
  var id = '{スプレッドシートのID}';
  var sheet = SpreadsheetApp.openById(id).getSheetByName("シート1");
  var ipaddr = e.parameter.ip;
  sheet.getRange("A1").setValue(ipaddr);
}

上記コードでは,GETを受け取った時,"ip"に設定されているパラメータがスプレッドシートのA1セルにIPアドレスが書き込まれます.
そうしたら,"公開"→"ウェブアプリケーションとして導入"→"アプリケーションにアクセスできるユーザーを全員(匿名含む)に変更"→"更新"
として,WebAPIを公開します.

リモートPC側(Windows 10)

こっちがWindowsなので結構面倒くさかったです.
まず,IPアドレスをGETで送るbatファイルを作成しました.

set IPADDRPATH={batファイルがあるディレクトリ}\ipaddr.txt
ipconfig | find "IPv4" > %IPADDRPATH%
set /p myipaddr=<%IPADDRPATH%
curl {作成したWebアプリケーションのURL}?ip=%myipaddr:~38%

結構無駄ありそうですが,こんな感じで.
一度ipaddr.txtにipconfigからfindしたIPアドレスを入れ,そこから再度読み込んで"ip"のパラメータとしてAPIを叩いています.
最初に作成したスプレッドシートを確認すると,A1セルにIPアドレスが書き込まれていると思います.

後は,このbatファイルを定期的に実行するようにタスクスケジューラに登録します.
GUIからできるらしいのですが,上手くいかなかったのでコマンドプロンプトから設定.
ちなみに,/sc hourly /mo 6 で6時間に一回とかになるはず

schtasks /Create /tn "ipsender" /tr "{batファイルがあるディレクトリ}\ipsender.bat" /sc minute /mo 30

これで,30分に1回実行されます.ちなみに消す時はこう.

schtasks /Delete /tn "ipsender" 

感想

作ったもののあんまり学内PCにアクセスする機会がないし,
そもそもIPアドレスが滅多に変わらなくて悲しい.(ネットワーク整備みたいなのしたっぽいし,固定IPになってる節)

そのうち,学内/社内のWindows PCにリモートデスクトップ接続する話を書きます.

*1:DHCPで変わったり等々