Marathon Match 142 参加記 - ヴァルの開発記

問題概要

10x10～30x30のグリッド上にプレゼントが置かれており、画面外から湧く複数のエルフを操作してプレゼントを拾って画面外に持ち去るとスコアがもらえる。プレゼントを守るAIが動いていて、グリッド上に木箱を置いてエルフを妨害してくる。エルフは木箱を拾い、持ったまま移動することができる。拾った木箱やプレゼントを再び置くことはできない。

木箱を置くAIにはMarathon Match 131で作られたものが使用されているらしい（私はmm131には参加していないので、そっちの詳細は分かりません。）

結果

暫定４位（システムテスト待ち）

考察

まずはBFSかダイクストラで１人ずつ最短経路でプレゼントに向かって進む実装をするのがよさそう。これをやってみると分かるが、あと２歩でプレゼントに届くというところで１歩先に木箱を置かれるとプレゼントには絶対にたどり着けない。これを解決するために、以下の画像のような動きを考える。この場合、相手は①の場所に木箱を置くことはできない。もちろん②の場所に木箱を置かれるとこの動きはできなくなるが、幸いにもそのような木箱の置き方はあまりしてこなかったのでこれがかなり効いた。

やったこと

※以下に書くスコアはローカルでseed=1から100ケース回したときのスコアの合計です(途中から1000ケース)。TopCoder上で表示されるスコアとは異なります。

[Score: 370581]

・プレゼントを持ったエルフ、木箱を持ったエルフ

　→BFSで箱を避けつつ最も近い画面外へ移動する

・何も持っていないエルフ

　→BFSで箱を避けつつ最も近いプレゼントへ移動する。そのような経路が無ければ箱へ移動する。

[Score: 406833]

・プレゼントの横で箱を持った場合その場で待機する。他のエルフはそのエルフを横にどかして進む。

　木箱持ちエルフがプレゼントの横ではない場所にいる場合、画面外に移動する。

[Score: 424120]

・BFSをダイクストラに変えて、木箱へ移動する重みを1000にする。

・「閉じ込められたプレゼント持ちエルフ」をプレゼントと同じとみなす。そうすることで、他のエルフは木箱を拾って救出する動きをする。

[Score: 425443]

・最後の１個のプレゼントをN*Nターン経過するギリギリまで運び出さない。（その間に相手が木箱を置いたらそのぶんスコアが増えるため）

[Score: 450258]

・木箱持ちエルフは横にプレゼントが無くてもその場に立ち止まり、画面外に木箱は持っていかない。→プレゼント横以外に木箱を置いて広範囲を囲うようなAIに対して有効だった。

・何も持たないエルフの経路を改善。木箱の上を通過する場合はその場所の周囲２マス以上が空きマスであるような経路を優先する。もしそこで木箱を拾った場合、周囲２マス以上が空きがあると次のエルフが通るときに避けやすいから。

[Score: 466145]

・木箱持ちエルフは相手AIが箱を置いたことがある場所へ移動する。→箱を置く場所がある程度決まっているAIに対して有効だった。

[Score: 471159 (1000ケースで計測: 3653118)]

・複数の木箱持ちエルフが同じ場所を目指すのを避ける

以下、スコアは1000ケースで計測

[Score: 3687011]

・ダイクストラの経路計算で木箱持ちエルフを踏んで移動するコストを1から10に増やした。これにより「木箱持ちエルフをどかして移動する」が発生する回数が減って、木箱持ちエルフがいるべき場所にいれるようになった。

[Score: 3729222]

・木箱持ちエルフが他のエルフのために道をあけるとき、入ってくるエルフが進みたい方向以外の方向へ優先的に避けるようにする。

[Score: 3748153]

・もうプレゼントに到達できない木箱持ちエルフは邪魔になるだけなのでグリッドの外へ逃がす（到達できない判定は、木、木箱、自分以外の木箱持ちエルフを通行不可のマスとして判定）

[Score: 3769886]

・木箱を通過する経路を選択するとき、すぐ隣にプレゼントがある木箱を優先的に経路として選択する。　→木箱を乗り越えたら必ずプレゼントがもらえるから。プレゼントまで距離があるとその道中に木箱を置かれて道を塞がれる可能性がある

・プレゼント持ちエルフは、木箱持ちエルフだけでなく何も持たないエルフもどかして移動する

・プレゼント持ちエルフは他のプレゼント持ちを引き連れて移動する。　→複数のプレゼント持ちエルフが木箱に囲まれた場合、固まって移動することで脱出するとき一気に全員で脱出できる

[Score: 3828602]

・id=4の相手AIはエルフが近づくまで木箱を置かない。さらに１ターンに１つずつしか木箱を置かないので、画面端にエルフを貯めて一気に攻めることでほとんど木箱に妨害されずにプレゼントを回収できる。

感想

Gridゲーム楽しい。

mm参加は約３年ぶりでしたが、良い成績を出せて嬉しいです。