ハル研究所プログラミングコンテスト2010
今回もリアルタイムで記録しておく。途中にICPC(およびJava Challenge)が挟まるので。
11月後半
- とりあえず問題に目を通してみる。典型的なマルチエージェントシステムの問題に見える。あとスコアが絶対評価なので、大きいテストケースでより頑張る必要がある。
- このコンテストの特徴的なところは、「標準ライブラリ使用禁止」と「グローバル変数の使用禁止」。前者は自前で書けばよいものの、後者はつらい。同じような計算を繰り返すことになりそうな気がする。
- 今回は長期間のコンテストなので、visualizerもきちんと自前で用意する。それなりの実行速度も欲しかったのでOpenGLで書いてみた。visualizerを書き終えてからソルバを書き始める。
- まずは方針を考える。いろいろ手段が考えられるけど、取りあえず最小費用流で書き始めてみる。
- ローカルで190秒位のコードが出来上がったのでsubmitしてみる。スコア0が出て愕然。
- 配列の長さは完全に固定長じゃないとダメらしい。さらにTLEを検知しないようにすると26000点位のスコアが出る。こんなに遅いとは一体…。
- とにかく、確実にTLEしないような単純なコードを書いてみる。4近傍に砂糖があったら食べて、それ以外は最も近い砂糖に近づくような単純なもの。これで60000点近く出て!?となる。ローカルのスコアはその半分以下なのに…。
- とりあえず高速な解法でないと全く間に合わないので評価関数を導入する。少し評価関数について復習しておこう。
- 長所は実装が楽であること。様々な要素のうちどこがクリティカルであるか検出するのが楽。計算時間の見積りも楽。情報のやりとりができないというルールにも適している。
- 短所は単純すぎて高スコアを望むのは難しいこと。
- つまりコンテストの終盤直前までは評価関数でどこに力を入れるべきか判定して、最後にその部分に全力投球するのが良いのかもしれない。
- 同じ砂糖に大量に群がらないようにする、などの処理を加えてパラメータをいじると75000点位でて上位10位に入る。
- 次に砂糖が降ってくる場所にも近づくようにすると80000点位。
- 10近傍程度までは距離をマンハッタン距離ではなく幅優先で求めると82000点位。
- 次に砂糖が降ってくる場所の評価を高くする(既に存在する砂糖塊とほぼ同じ)にすると85000点位出て1位になる。
12月前半
- パラメータをちょっといじってみるもなかなかスコアが上がらない。なぜ？。
- とりあえずICPCがあるのでしばらく放っておこう。ただし順位表は最大のヒントなので毎日目を通すようにする。
- 1位のスコアが2位に5000点位の差をつけている。点数も突然3000位伸びてたので何らかのブレイクスルーがあったはず。
- というかさすがに90000点はおかしい。1ゲーム平均3000点なんてローカルと比較すると明らかに異常。ということで向こうのテストケースを調べるコードを投げてみた。
- 蟻の数や砂糖塊の数は特に変わりないけど、砂糖粒の体力が明らかに低いことが分かった。平均4.3らしいので、体力の上限が7〜8くらいになっているものと思われる。実際にローカルでも体力の上限をそのように設定すると向こうと同じ位のスコアが出た。
12月後半
- 蟻が砂糖に踏み潰されにくいよう手を加えた。
- 各砂糖塊に均一に群がるための評価関数を書き直すと得点がそこそこ上がった。88000点くらい。
1月前半
感想
- 基本的には自分の好みの問題で、参加していて楽しかった。
- テストケース固定は好みではない。Marathon Match形式の方が健全な気がする。
- 特定のテストケースに対して過剰学習しているようでちょっと。
- しかもテストケース30個はあまりに少なすぎる。
- 実行環境が普通の計算機と違うのはそれはそれでおもしろかったのだけど。
- サーバーに負担をかけるのを厭わないのであればも2000点位上げる方法はあった。それでも1位には届かないけど。
- 具体的には、蟻の個数と砂糖塊の個数が特定の値のときだけ動作するようにすれば、各テストケースに対して最適なパラメータを探索することができる。
- これが、"特定のゲームに依存したチューニングを行うことを禁止します"に触れるかどうかは微妙なところだと思う。
- 評価関数は無難ではあったけど、終盤はパラメータ調整位しかやることがなくなってしまった。
- 32ビット分情報を使えるのに、実質半分しか使えていなくてもったいない。
- 投稿回数95回。ちょっと多すぎて反省。テストケース固定だから仕方ない気もするけど。
