ハル研プロコン2016に参加しました
ハル研プロコンに参加しました。
www.hallab.co.jp
個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。
とりあえず自分のやったことを書いていきたいと思います。
貪欲パート
この後「ちょっと待てばレーザーでたくさん消せるならちょっと待つ」というのを入れましたが, これはうまくいきませんでした。
これについて考察すると, 例えば残り 3 個の小惑星があり, 1 つは非常に遠くにあって残りの 2 つはすぐ近くにあるとします。今打つと遠くにある一つのみを消すことになるのですが, ちょっと待ってから打つと近くにある小惑星が 2 つ消せるとしましょう。
そうすると, 元の方法では「遠くを消してからちょっと移動して 2 つ消える」だったのに対し, もう一つの方法では「2 つ同時にレーザー打ってから遠くにある小惑星に近づいてまたレーザーを打つ」となるので, 明らかに損をします。
- 近づく小惑星に関して, 端っこに近いやつほど近づきやすくする, で 68199
- レーザーも端っこ消しやすくすれば良くなるのでは, を勘違いして真ん中にあるほど消しやすくしたところ改善, で 67686
これについて考察すると, 今回の自分のアルゴリズムではなにかの小惑星に向かう動きしか考慮していないので, 宇宙船自体はずっと端っこにいたほうが有利っぽいことを考えるとレーザーは真ん中をたくさん消すほうが良さげだったということですかね。
探索パート
- 行先であり得そうなものを 2 通り拾ってくるようにする, で 62469
- ここでマグカップを確信しました。
- レーザーについてもあり得そうなものを 2 通り拾ってくる, で 61632
- 枝刈りを入れることでたくさん探索して 60117
- 枝刈りは, (今のターン) + (まだかかりそうなターン数) > (今までの最短ターン) だったら消す感じです。
- 時間で粘るようにする, で 59761
後は気合の高速化で探索範囲を広げました。ここまではめっちゃ楽しかったんですがこっからはあんまり楽しくなかったです。
最終的には 59136 ターンで finish しました。最後に確認したときは 4 位僅差で 3 位だったと思いますがどうなることやら。
上位陣の話を聞いたところ,
だったそうです。確かにこれだと高速化ゲーで楽しくなさそうですが, ビームサーチは「ターンでゲームを進めると評価関数つくりにくいなぁ」と思ってた自分にとっては「小惑星の壊れた数」でサーチを進めるのは頭の良さを感じました。なるほど。
できれば 3 位に入っててほしいです…
