HAL研究所 プログラミングコンテスト2010 に参加してきた
この記事を書き始めたのは、11月29日なので、実際には「参加中」だったりしますが。
足跡的なものとして、記録していきたいと思います。
11月29日
最初の一歩
まずは、ソースをダウンロードして、Visual C++ 2010 Express をインストールしました。
とりあえず実行できることを確認し、ソースコードを見てみると、デフォルトでは
- アリの上に砂糖があったら、食べる
- それ以外の場合、フィールドを走査し、最初に見つかった砂糖に対し、左右→上下の順で近づく
というコードだけでした。
砂糖を食べるコードをコピペして、上下左右の砂糖を食べるようにすると、
ローカルでは7564点、オンラインでは11468点になりました。
近い砂糖を食べる
今度は、対象のアリに近い砂糖を食べに行くようにしてみます。
すると、ローカルでは19282点、オンラインでは46740点となりました。
アリが既にお食事してる場所には行かない
これだけの状態だと、左右→上下でたどり着いた場所にアリがいると辿り着けないので、
その場合には、ぐるっと回って砂糖に辿り着くようにします。
すると、ローカルでは28367点、オンラインでは58191点になりました。
砂糖から最も近い4匹以外は、その砂糖に向かわない
フィールドの走査時に、対象セルの四方に砂糖があり、かつ、そのセルに進入可能であり、
更にそのセルから最も近い4匹のアリであるなら、移動するようにしてみた。
これで、ローカルでは35582点、オンラインでは70102点になりました。
11月30日
Next予想
NextSugarBlockから、次に降ってくる砂糖粒の場所が分かります。
なので、暇してるアリを、次に降ってくる砂糖粒の近くに適当に移動させておきました。
すると、オンラインは71274点に。
Nextが来るところには移動しない
下敷きにならないように、Nextが来る場所には移動しないようにしました。
オンラインは72294点に。
リファクタリング
ここで一旦、リファクタリングしました。
ソースコードも綺麗になり、見やすくなりました。
更に、バグがあったので、直しました。
すると、ローカルでは38307点、オンラインでは77629点になりました。
移動時に通れない場合、別ルートを検討
簡易的にではありますが、通れないときは別の方向に移動するようにしました。
ローカルは39286点、オンラインは78450点に。
Next予想の確定化＋移動が難しい場合にターゲットを切り替え
移動しようとしても、既にアリがいたり砂糖粒があって移動できないときに、
ターゲットを切り替えるようにしました。
これで、ローカルは40897点、オンラインは80755点になりました。
12月1日
手持ち無沙汰のアリの処理
食べる砂糖粒もなく、砂糖粒に向かうメンバーからも漏れ、
挙句の果てにはNextに向かうことすら叶わなかったアリの処理を、追加しました。
とりあえず、盤面を4つに分けて、一番過疎ってる地域に向かわせました。
これで、オンラインは80953点に。
砂糖粒に向かうメンバーの選出処理の変更
最初は、最も近い4匹のみを向かわせてましたが、
砂糖粒の量や残り体力を勘案して、向かわせる数を変動させてみました。
パラメータを試行錯誤することで、オンラインは82111点まで上がりました。
12月2日
試行錯誤
いろいろと考えた案を実装して応募するも、スコアが伸びず、ということの繰り返し。
特に、ローカルでは結構伸びたりしても、オンラインでは下がったり、ということが多かったです。
前日の、砂糖粒に向かうメンバーの選出処理を、Next砂糖粒に対しても実装してみると、
スコアががくっと下がってしまったり。
(手持ち無沙汰が増えてしまい、きっと無駄が発生していたのでしょう。)
過疎地域に向かうのではなく、初期位置を記憶しておいて、そこに戻るようにしたら
1万点近く下がったり。(非合理的だからですね。)
心機一転、一から作り直し
一度、全く最初の状態から、作り直してみたりもしました。
アプローチの仕方を変えて、
・今までのアプローチ
「存在する砂糖粒を探す→メンバーから漏れたら、Next砂糖粒→行けなかったら、過疎地域へ」
・心機一転
「存在する砂糖粒とNext砂糖粒にグループ分け」
結論からいうと、スコアが全然伸びませんでした。残念。
ちまちまと堅実に
もう一度、今までのソースコードをいじることにしました。
自身に隣接している砂糖粒に、潰されているアリがいたら、優先的に食べる
今までは、隣接している砂糖粒は、体力が少ないものを優先的に食べていましたが、
アリが潰されている場合は、体力に関係なく、それを食べるようにしました。
これで、オンラインは82234点 (+123点) に伸びました。
過疎地域に向かうときに、どれぐらいの間向かうのかを算出
今までは、過疎地域に向かうターン数を定数にしていましたが、
過疎地域までの距離から、どれぐらいの間向かうのかを変動させてみました。
これまた、パラメータをいろいろいじった結果、
オンラインは82461点 (+227点) まで伸びました。
12月3日
隣接セルの隣接セルに、潰されているアリがいたら、優先的に助ける
現在地の隣接セルに体力1の砂糖がなく、かつ、現在地の隣接セルに潰されたアリがおらず、かつ、
現在地の隣接セルの上下左右いずれかが移動可能であり、そのセルの隣接セルに潰されたアリがいる場合、
そのマスに移動して、優先的にアリを助けるようにしました。
この結果、オンラインの点数が 83340点 (+879点) と、大幅に伸びました。
砂糖粒に向かわせるアリの集団の最大数を、近隣5匹までにする
いくつかの数で試しましたが、5が最も結果が良かったので、5を採用しました。
結果、83736点 (+396点) となりました。
12月4日
この日はふるわず、スコアが伸びませんでした。
12月5日
Next砂糖粒に向かった際に、移動方向を記憶しておき、Next砂糖粒の隣接セルに到着しても、更に移動できるなら進む
要するに、電車の入り口に固まらずに奥まで進むようにしたようなイメージ。
83864点 (+128点) と、少し伸びました。
潰されそうなアリが隣接セルの隣接セルにいる場合、助けに行くが、アリの総数が35匹以下の場合、Next砂糖粒が降ってくる危険性があるなら、逃げる
や、ややこしい･･･。
84536点 (+672点)
砂糖粒を探す際に、砂糖粒ができるだけ固まっている場所を探すようにした
具体的には、隣接4マス＋その先＋斜め四方のマスなど。
若干重みを変化させつつ、86581点 (+2045点)
12月6日
この日はふるわず。
12月7日
Next砂糖粒に向かう際に、単純に向かおうとすると障害物があって行けない場合、行かないようにした
86756点 (+175点)
12月8日
忙しくなってきて、なかなか手がつけられないように･･･
12月9日
評価値を、条件によらず毎回更新するようにした
87255点 (+499点)
アリの総数チェックをはずした
うーん、時には伸びたコードを消すことも重要ですね。87997点 (+742点)
Next砂糖粒がたくさん固まっているところに向かうようにした
88204点 (+207点)
その後
やたらと忙しくなる→徹夜、泊まりが多くなりました。
また、年末年始にインフルエンザにかかってしまって、ラストスパートもまともにできず。
結果、やったらと古い点数のまま終わってしまいました。
(終了間際のランキングは、これまた用事が入っていたため、確認できず。10位以内、保てたのかなあ。)
追記 学生ランキングで8位だったようです。
感想
上位の点数を見ていると、壁があるように見える。
多分、この壁は、思いもつかないようなバッドケースか、あるいはグッドケースでいかに得点を伸ばすか、といったところで
大きく分かれるところがあるんじゃないのかなあ、とか考えてる。
結局、これといったトリッキーな案を取り入れることもなく、
かなり無難な考えを愚直に実装し続けた結果でコレなので、もっと時間をじっくりかけてやりたかったというのが本音。
やたら楽しいので、来年も参加しようと思います(･∀･)
