AHC008 に参加していました。
方針
大きく分けて「柵を配置する」「動物を捕まえる」の 2つのフェーズでゲームを進めていきます。
- 複数人で 1つのチームを作ってチーム単位で行動を行う
- 部屋の中に予め設定しておいた柵を配置する
- チーム単位で動物の捕獲を行う
チームの作成
1人でペットを追いかけても捕獲するのが非常に困難なので、複数人で対象の動物を捕獲します。人間の数にもよりますが基本的には 2チームに分かれて捕獲を行います。
人間の数によってチームのメンバー数と編成数は変化します。
- 5人 (3, 2)
- 6人 (3, 3)
- 7人 (4, 3)
- 8人 (4, 4)
- 9人 (4, 3, 2)
- 10人 (4, 3, 3)
柵の配置
今回はグリッドサイズが 30 * 30 で固定だったので、前もって柵を配置する場所を決めておいてそれに元に柵の配置を行います。 今回自分は全部で 11個の配置パターンを用意しました。
基本的には図のような配置になります
ポイントとしては主に以下の 2点になります
- 人が横移動するだけで捕獲が可能
- 犬、猫を捕獲するための通路の作成
その他の配置パターン
M = 5
M = 6
M = 7
Mが小さいケースでは 4ラインだと人が足りなくなってしまうので 3ラインに減らしています。 また、M が 7以下の場合は 1回の横断で柵を設置しきれないため、柵の数を少なくしてなるべく早く設置出来るようにしています。
M >= 8 かつ動物の数 <= 12
人間の数が多くて動物の数が少ない場合は柵を多少減らしても達成率に影響が無いので、なるべく少ない柵の設置で目標が達成出来るようにパターンを修正しています。
横移動のみでの捕獲が可能
柵の設置が終わると水色のラインに人を割り当て、後は対象のペットに対して横軸を合わせるだけで捕獲が可能になります。
チームは横軸を合わせて行動することでペットが捕獲範囲に入ってきた際にすぐに捕獲出来るようになります。
その他の配置箇所
M = 5 (3人, 2人）
M = 6 (3人, 3人）
M = 7 (4人, 3人）
M = 8 (4人, 4人)
M = 9 (4人, 3人, 2人)
M = 10 (4人, 3人, 3人)
犬、猫の捕獲
今回の問題では完全にランダムではない行動を行う動物として「犬」と「猫」の 2つが用意されていました。 これらの動物は最初の行動が「目的地に近い方向に移動」というものなので、通路を用意してあげればそこに勝手に入って来てくれて捕獲することが出来ます。
乱数次第ではずーーーっと横移動だけを行い通路を使ってくれないパターンもあるとは思いますが、基本的にはそのようなことは発生しないので特に問題はありませんでした。
通路の長さは 4以上を確保する
「犬」「猫」「豚」に関しては移動距離が 2であり、 移動前と移動後の (x + y) の偶奇が変化しないので最小効率の 3の通路で捕獲しようとすると捕まらない可能性があるのでそれを避けるために 4以上の長さを確保する必要があります。
この場合、緑マスに止まる「犬」「猫」「豚」は絶対に捕獲することが出来ません。
長さを 4以上にすることでどちらの場合でも捕獲可能なマスが存在するようになります。
通路から出ようとしている「犬」「猫」は積極的に捕まえに行かない
例えば図のような状況下で最初の行動が下方向だった場合、絶対に通路内に入ってくることは無いので捕獲対象としての優先度を下げるようにします。
その場待機 or 通路からの脱出のいずれかの行動になるので追ってもあまり意味がないです。
通路に入ろうとする「犬」「猫」は捕まえに行く
図のように通路の中に入っていく動きをしている場合は高確率で通路内に侵入してくる可能性があるので捕まえに行きます。
最後の 1匹を無理やり捕まえに行く
今回のスコア計算ではペットが 1匹残っているだけでスコアが半分になってしまうので、最後の 1匹に関しては無理やり捕まえに行きます。
その時に使用する捕獲のパターンです。（画像は M >= 8 の時に使用するもの）
赤いマスの部分は最後に部屋を閉める場所になっています。
最後の捕獲に関してはゴリゴリに if 文を書いてるのでかなり無理矢理な実装になってます。
牛が全然捕まってくれず最後に捕まえにいっている様子がわかると思います。
「最後の 1匹ではなく 2匹だともっとスコアの取りこぼしが少ないのでは？」と思ったのですが、この方針だと捕獲までにかかる柵の数と閉じ込めた際の空間の消費量が「待ち」の戦略に比べて増えてしまうので、全体的なスコアとしては下がってしまったので採用しませんでした。
感想
今回は比較的得意な分野（二次元グリッド + マルチエージェント）だったので、特に大きく方針を外すことなく実装出来たかなとは思います（1位のスコアの 9割が毎回の目標値 - 今回だと20位辺り）。柵の配置を固定ではなくて不定形にすることで 7G あたりのスコアが出ることは確認していたので (seed 0 で確認 77111111）、もう少し期間があればそっちの方針も試していたのかなとは思います。（不定形だと犬 & 猫の捕獲は難しいので「犬」「猫」「その他」で戦略を切り替える。このあたりを実装してきて 7G ぐらいを出す人が出てもおかしくないなとは思ってました）
もし他のヒューリスティックコンテストに興味があるという方は 3/17 2:00 から Topcoder Marathon Match 134 が始まるので是非参加してみてください。（ただし、こちらに関してはコンテスト期間中の解法や考察に関する言及は禁止となっているので注意が必要です）
