Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2010年06月06日(日) 第五回チームラボ天下一武道会

[]第五回チームラボ天下一武道会 第五回チームラボ天下一武道会を含むブックマーク 第五回チームラボ天下一武道会のブックマークコメント

f:id:tanakh:20100607043313j:image:w240

第五回チームラボ天下一武道会 : ATND

第五回チームラボ天下一武道会で優勝しました。

第三回に続いて二回目です(第四回も参加していましたが、あまりに成績が悪かったので、参加記書くの忘れてました…)。

問題

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位のプログラムは次の数の予測を決めうちの数でやっていたそうですが、レスポンスタイムが変わってから周りの正答率が若干下がったような感じだったので、履歴を用いて予測していた私のプログラムがうまく動いたのかなと思います。

感想

また優勝できて嬉しいです。今回はヘリコプターをもらいました。ありがとうございました。今回の課題は個人的にはかなり楽しめました。いろいろ要素は考えられますが、次のような感じでしょうか。

次回も近々あるそうなので、また参加させてもらえればと思います。面白いのを考えるのも大変かと思いますが、期待しております。

Connection: close