第五回チームラボ天下一武道会
第五回チームラボ天下一武道会で優勝しました。
第三回に続いて二回目です（第四回も参加していましたが、あまりに成績が悪かったので、参加記書くの忘れてました…）。
問題
http://tam-lab.sakura.ne.jp/tenkaichi/
マルチプレイヤー数当てゲームのような感じでした。サーバがある数を保持しているので、その数を当てる。外れていた場合、大きすぎたのか小さすぎたのかが帰ってくる。正解した場合、スコアが1加算され、サーバが保持している数が1増える。ただし、サーバがレスポンスを返すのはリクエストしてから1秒後。さらに同時に張れるコネクションは2つまでという制限がありました。
当日の様子
バトルロワイヤルということで、問題解説中もすでにバトルは始まっています。すでに手動参加してる人が居るってことで、なかなか熱い感じでした。問題聴きながら手動で二分探索してみたら確かに50ぐらいまで既に増えているようでした。手で適当にクエリを投げながらどうするか考えて、とりあえず数当てゲームだったら二分探索じゃないかということで実装を始めました。
プログラムはHaskellで書きました。クエリはHTTPで投げるので、httpライブラリを使いました。適当にクエリを投げてみるところ、かなりの割合で503が出ました。その時はどうしてかわからず、そのまま進めていましたが、やはりどうしても効率が悪いのでちゃんと調べてみたら、どうやらhttpライブラリのシンプルAPIがコネクションをcloseしないらしい。手動でコネクションを用意するAPIを使うと、ようやくちゃんと動くようになりました。最初のほうあまりスコアが取れてませんでしたが、それで徐々にスコアが上がってきました。
二分探索で数を当てていたのですが、サーバの数字はリアルタイムでカウントアップしていくので、上限と下限の数をアドホックに少しずつ上昇させていくようにしていました。それでしばらくやっていたのですが、よく考えると、そうなってくると二分探索でやる意味がほとんどない。一回正解したらその一秒後に再度クエリを投げられるので、一秒間に他の人たちが正解を当てる回数程度インクリメントして送りつければいい。見た感じでは大体秒速3-4ほどだったので、それをハードコーディングして適当にインクリメントするだけのものに変更しました。
こうなってくると結局、問題は一秒間に他の人たちがどれぐらい正解するかというのをどれだけ精度よく予測するかというところに帰着されます。最初のほうは手で入れていましたが、周りのプログラムの精度がよくなってくるにつれてカウントアップも早くなるので、それに追従するためにちゃんと履歴から計算することにしました。
今回の問題の難しいのは、プログラムを改良している最中にも他の人のスコアはどんどん増えていくというところです。プログラムを動かさないと自分のスコアは伸びませんから、なるべく停止時間を短くしなければなりません。また、改良によって精度が下がるとトータルではかなり損をしてしまうので、プログラムを書き換えるのにかなり勇気が要ります。私は、コネクションが二つ張れるというのを利用して、常時二つプログラムを走らせるという戦略をとりました。ひとつのコネクションでそこそこ精度がいいプログラムをずっと走らせ、もうひとつでいろいろ実験して改良しているプログラムを走らせませます。改良の結果精度がそれなりに向上したら、ずっと走らせている方も切り替えます。こういうコネクションが二つというのを生かした開発が出来るのは面白かったと思います。他にも二つのコネクションを強調させながら効率をよくする戦略なども考えられますし、なかなか面白い制限だったと思います。
残り1時間ぐらいになった時、いろいろな地味な改良が実を結んだのか一位になりました。残り30分になるとスコアボードが隠され、さらにレスポンスタイムが半分になるとのことでした。残り30分の時点で2位との差が150ほどあったのですが、トータルの得点からすると5%ほどの差だったので、少し精度が悪いと十分逆転されそうでした。レスポンスタイムが半分になることを考慮して、プログラムを改良すべきかどうかなかなか難しいところでしたが、何もしないで負けたら悲しいので結局最後まで改良し続けました。予測する式を微妙にいじったりいろいろしていましたが、結局あまり精度は変わりませんでした。おそらくプログラムを止めていた分だけスコアは悪くなったと思います。
さてそれで、どきどきしながら結果発表を迎えたのですが、割といい感じのスコアで勝っていました。2位と3位のプログラムは次の数の予測を決めうちの数でやっていたそうですが、レスポンスタイムが変わってから周りの正答率が若干下がったような感じだったので、履歴を用いて予測していた私のプログラムがうまく動いたのかなと思います。
感想
また優勝できて嬉しいです。今回はヘリコプターをもらいました。ありがとうございました。今回の課題は個人的にはかなり楽しめました。いろいろ要素は考えられますが、次のような感じでしょうか。
- 問題が十分にシンプル
- 環境構築が容易(前回はHTTPサーバを立てる必要があったので)
- スコアボードがあった
- ラスト見えなくなって、それなりの緊張感
次回も近々あるそうなので、また参加させてもらえればと思います。面白いのを考えるのも大変かと思いますが、期待しております。
