Spring Challenge 2020の感想および方針
最近CodinGameにはまり始めたけせらせらです。
今回実は参加自体は2回目ですが、前回(OceanOfCode)はツイッターのFFの方々が次々とGoldに行く中自分だけSilver19位で止まってしまった上に、ただのルールベースのコードだったので、別にブログを書かなくてもよいか…という気分でした。
では、今回はすごいコードを書いたのかというとそうではありません。書いたものはdfs、bfs、と少し工夫した貪欲ぐらいだったと思います。
しかし、今回違うのは結果です。
なんと今回Gold96位でした！
ということで今回はそんなに難しいアルゴリズムを書かなくてもGoldに行けるよ！という意味合いも込めて記事を書きました。 ということで、
今回の概略
不確定情報には手を出さず（出せず…）確定情報だけでやりました。
一番リソースを割いたのが経路探索の部分で他はルールベースで書きました。
方針
・前計算
1. 各点間の距離
2. 各点の次数
3. 袋小路の検出
4. スーパーペレットの割り当て
1.2.はいろいろ使います。
3.についてですが、袋小路の場所と出入口を計算しました。これは主に敵のキルに使いました。
4.ですが、これはちゃんとやるとちょっと難しそうなのでやめ。妥協します。
最初は各パックからの最短距離を測って割り当てていたのですが、
それだとスーパーペレットの間に挟まれたパックが右往左往してペレットを取りに行くことになり効率が悪いです。なので、最短距離を測って一番短いパックを割り当てたペレットに移動、再びその場所からスーパーペレットの距離を測り一番短いパックを割り当てたペレットに移動、というように割り当てました。（恐らく最適ではないが最初よりはまし）
・経路探索
経路の評価は別で盤面を評価し、辿ったマスの合計で判定しました
経路探索はdfsで全探索しました。ですが、これはさすがに計算量がかかるので、深さは6-7位です。これでもGoldには行けました。
ただ、さすがに改善の余地があるので次の枝刈りを行いました。
1. 同じ点を3回以上通る場合はカット
2. その時点での最大値を取りこの先絶対にこの値を超えることがなければカット
これで探索の深さは10まで行くようになりました。
・盤面の評価
これはいろいろ試行錯誤した結果すごく簡素なものになりました。
1. 相手より近い場所は1.1倍
2. 終盤においてペレットが連結してる個数に沿って少し加点
3. 自分のパックの行き先周辺は減点
としました。
・敵のキル
これは前計算3.を用いて敵が袋小路に侵入したのを確認し次第 、袋小路の出入り口にどちらが先にたどり着くかで判定しました。
敵味方共に袋小路に入っている場合が心配になりそうですが、味方パックのゴールを相手の位置に設定しているので問題ないです。
曲がり角があっても見失うのは必ず曲がり角なので1回までなら必ず見つけてくれます。
しかし、袋小路に2回曲がり角があると見失ってしまう場合があります。その場合は、袋小路の先端に行くようにすれば取り敢えずおっけーです。（していませんでしたが…）
やりたかったこと
- 視界外のペレットの推測
- 敵位置推定
- 経路探索をビームサーチや焼きなましで探索
上の二つはやれば必ず強くなるのでスキルが追い付けばやりたかったです。さらに、この2つは関係性が強いので片方ができれば片方にも役立ちます。 やるとすれば、次数が3の点(T字路)においてTの横棒の部分に自分のパックがいれば見えなくなった瞬間に下に言ったことを判定できるみたいな感じ。 3つ目も練習すればできるものだと思うので、細々と練習していきます。
他の方の話を聞いて
- パックの経路探索を２フェーズに分けて味方の経路を邪魔しないようにする。
- SPEED中にペレットの状況を確認するため交差点で止まる
特に2つ目は実装が簡単なのでできたなーとおもいました。さらに、驚いたのが本質情報として交差点が2マス置きに設置されているためSPEEDのタイミングを調整すれば必ず交差点を確認できるという事実です。すごい…
感想
正直、自分の順位にびっくりしている状況です。
そして、自分の発想力でもそんなに悪い作戦ではなかったと感じたので自分の力でも通用する可能性は十分あるのかなと思いました。
ただ、実装したかったのにできなかったことがあるのは事実なのでこれからも精進したいです…
そして、CodinGameを始めようか迷ってる方！難しいアルゴリズムが書けなくてもGoldに行くチャンスはあるので参加してみましょう！！
