はじめに
以前、『競プロ〜ヒューリスティック/マラソン事始め〜』という記事を書き、その中でヒューリスティックコンテストについて大まかなパターン分類を試みました。
今回、MC Digital プログラミングコンテスト2022(AHC008)でこれまでとはちょっと異色な問題が出題されました。最初は前の記事のパターンに当てはまらない問題が出てしまって困ったなと思っていたのですが、考えていくうちにそうでもないように思えてきたので、先の記事の補足を兼ねて解法の説明を書きたいと思います。
どのパターンに該当するのか？
さて、今回の問題は『競プロ〜ヒューリスティック/マラソン事始め〜』のどれに該当するのでしょうか？
まずインプットについてですが、入力値には各ターンのランダム要素がありseedは明かされていないものの、基本的な情報は与えられています。また解を少し変えた時のスコアの計算ができるかと考えた時に、そもそも「解を少し変える」というのがどういうことなのか分かりにくく見通しが立ちません。そこで一旦「初期解重視型」だと思ってみることにしましょう。
「初期解重視型」だとすると、先の記事では評価関数をうまく作って、貪欲法やビームサーチで考えましょうということになっていました。そしてその評価関数は、次の一手の「良さ」を表すように考えましょう、と書かれています。ただ今回のケースで「良さ」を考えようとしてみると、自由度が高過ぎてやはり途方に暮れてしまいます。
筆者も、1日目はひとまず人の周囲4方向に壁を置くプログラムを作って途方に暮れていました。
今回の問題は、アルゴリズムのコンテストで言えば典型問題が中心のABCに対してより考察力が必要なARCやAGCがあるように、典型的なヒューリスティック問題と比較して考察力が問われているようです。
どうして良いのかわからない最大のポイントは自由度が高すぎることなので、敢えて枠組みを決めることで制約をかけて自由度を下げてみることにしました。
いきなりややこしい配置が出てきましたが、結論から言うとこれは考えすぎで、最終的にはもう少しシンプルな形になりました。ただ、考えたポイントとしては以下の通りです。
- 壁を作る位置は予め決めておく。壁は以下の条件を満たしたい。
- ペットが入りやすく、一度入ったら出にくい小部屋がある構造(赤い通路からは部屋に入りやすく、部屋に入ると出口が狭いので出にくいはず)
- 最初に作るときに作りやすい(青い矢印沿いに歩かせて必要な場所で上下にブロックを置けば作れる)
- 人が安全に歩くことのできる場所を確保する(赤い矢印は人専用通路としてブロックは置かない)
- そしてその通路からペットを閉じ込めることができる(封鎖用のブロックは緑にしか置かない)
このように決めたことにより、人の行動として以下を考えれば良いことになりました。
- 開始直後は壁作りに専念する。青いラインに1人ずつ担当をつける。なるべく近い列を担当する。
- 壁作りが終わったら、赤いラインに担当を割り当てる。
- 少なくとも5人いるので、1ライン1人以上は割り当てられる。
- 全体的にペットが多めの方向に人も多めに割り当てる。
- その後の人の基本行動は以下のどれか。
- 動物が入っている部屋に向かい、両サイドから閉じ込めることができる状態になったら閉じ込める(行動A)
- 赤い通路上の動物を追いかける。できれば隣の通路の担当も同じ縦位置に誘導する(行動B)
壁作りについては、作り方は固定したので、担当をどう割り当てるかという問題に帰着しました。
壁が作り終わった後の部分がまだ難しいですが、先の記事に従って何らかの評価関数を作って優先すべき行動を決めることができそうな雰囲気になってきました。実際、基本的には以下のような評価関数を作りました。
- 行動A
- 部屋ごとに、両サイドの最寄りの担当までの距離の大きい方
- 行動B
- 通路に対し、その通路の最寄りの担当までの距離と、隣の通路にいる最寄りの担当の縦方向の距離の大きい方
- 行動Aよりは若干優先度を下げる
評価関数ベースで考えることができるようにはなりましたが、今回は評価関数の工夫というよりは最終的には諸々の実装力を問われている印象を受けました。
開始2日目にこのあたりまで作ることができ、スコア約4G点でこの時点で何と暫定1位になりました。
工夫した点
以下、どういうきっかけで何を工夫したかを列挙していきます。
可視化
ヒューリスティックでプログラムを改善していくに当たって、改善の気付きを得るために可視化は欠かせません。もちろん公式提供されているビジュアライザで見ることも大切ですが、うまく行っているケースとうまく行かないケースを見分けるために、テストケースを大量に自動実行し、テストケースごとのサマリを出力することも重要です。今回のコンテストで筆者が最終的に出力していたサマリは以下のようなものです(ここまでで説明していない要素を含んでいますが後で説明します)
こういう形で結果を出力しておき、気になるケースを公式のビジュアライザでより詳細に見ることで気付きが得やすくなります。
仕組みを作るのは大変ですが、1回作っておくと枠組みは使い回すことができると思いますので、今回のような少し期間が長めのコンテストの際にでも作ってしまいましょう！
列の追加・可変化(シミュレーション)
先程の可視化リストで最終捕獲ターンを出力していますが、最終の300ターンよりも余裕を持ってペットを捕まえ切っているケースが割と多く、ペットに割り当てる小部屋の面積がもったいない感じがしたので、ペットには申し訳ないですが部屋を細かく刻むことにしました。具体的には先程の図で、赤い線に囲まれた部屋エリアが3ブロックになっていましたが、4ブロックに増やしてみました。
これによって平均点は0.5G上がりましたが、捕獲失敗しているケースは増えました。失敗しているケースを見てみると、以下のことがわかりました。
- (当然ですが)人が少なくペットが多いケースが失敗しやすい
- 猫の捕獲に失敗するケースが多い
- 犬はほとんど捕獲失敗していない
大量のケースで統計を取って列数を選択することも考えましたが、今後色々アルゴリズムを変えていくことも考慮して、自プログラム内で時間の許す限りシミュレーションをして、最も期待値の高いパターンを選択するようにしました。
評価関数の工夫
捕獲の成功率を高くして、かつ封鎖に使う部屋数を少なくするために、評価関数に以下の要素を入れました。
- 猫の捕獲に失敗するケースが多かったので、猫をやや優先
- 使う部屋数を少なくしたいので、部屋に入っているペット数が多い部屋の捕獲を優先
ただし、わずかに優先する程度にしておかないと逆効果になるようだったので、距離が同程度だった場合に猫やペット数が効いてくる程度にしました。
部屋パターンの追加
先程列を4列にしましたが、まだ余裕があるケースもありそうだったので5列にしたくなりました。ただ、複雑な部屋パターンにしてしまったため、5列にしようとすると奥行きが狭く窮屈になりそうだったので、もう少し単純な形にして列を増やすせるように、以下のパターンを増やしました。
何故こちらを先に作らなかったかという感じではありますが、これなら多少幅を狭めても部屋の形として成立しそうです。先程のシミュレーションを拡張して、部屋パターンも含めて良いものを選ぶようにしましたが、結果的に左側のパターンが主力になっていくことになりました。
袋小路での捕獲
捕獲に失敗しているケースを見ていると、図のように封鎖部屋によって連続した壁ができてしまい、黄色く着色したような袋小路に迷い込んだペット(特に牛や豚)がなかなか抜け出せずに捕獲に失敗しているケースがありました。このような場所はブロックを1つ置くだけで捕獲できるので、「部屋で捕獲する」「通路上のペットを追う」の他の行動として「袋小路で捕獲する」を追加して評価関数を付与することにしました。
分断の防止
スコアを眺めていたときに、全捕獲に成功しているのに極端にスコアの低いケースを発見しました。ビジュアライザで眺めてみたところ、縦1列の部屋を全部封鎖してしまい、盤面が左右に分断されてしまっていたので、縦1列で最後の1部屋は封鎖しないようにしました。
犬対策
この頃にはスコアが伸び悩んでいましたが、打開策として犬を一網打尽にするシステムを考えてみることにしました。犬はほとんど捕獲失敗していなかったですが、人に寄ってくる習性があるため、うまくやれば狭い場所に閉じ込めることができるのではないかという作戦です。
最初は通路を作って人をその一端に集めて、犬が集まってきたところで一気に一方向に走って出し抜くことを考えましたが、幅1の通路でこれをやるとなかなか犬を引き離すことができなさそうだったので、通路の両端で人を二分して待ち構え、その間を走っている犬を一網打尽にする作戦を取ることにしました。
成功するかどうかはわからなかったので、最初の間は犬を無視して、犬以外を捕まえ終わってかつ犬がある程度残っていて、かつターン数に余力がある時のみ発動するようにしました。
実際に実装してみたところ、「ターン数に余力がある」程度の見極めが難しく、安定して成功することができませんでした。成功・失敗の期待値からすると損になるようだったので、この作戦は断念することにしました。
ただこの失敗には副産物がありました。最初の間に犬を無視することにしたにもかかわらず、他のペットの道連れで勝手に犬が捕まっているケースがそれなりに発生していたのです。なので、ある程度のターンまでは犬を無視する部分だけ残すことにしました。これについても多少良くなるケースと悪くなるケースがあったので、これはシミュレーションで良い方を取ることにしました。
壁を減らす
これまでのところ、最初に壁の基本形を作って封鎖ブロックだけ後から置くという方法を取っていましたが、スコアを上げるためにはなるべく置く壁を減らしたいところです。ただ、闇雲に壁を作って捕まえるのは難しそうだったので、配置はこれまでと同じという前提を保ちつつ、ペットが(まだ完成していない)部屋に入ったときに部屋を作るというようなことを試みました。これは確かに成功するケースがあって成功した場合のスコアは飛躍的に伸びるのですが、失敗するケースもかなり多い状況でした。シミュレーションでうまくいく時のみ選択するというのも試みましたが、最後まで安定して動かすことができず、これは断念しました。
代わりに、壁を減らすアイディアとして採用したのが、人の通路沿いにある壁を1つケチるというものです。
見てわかるように、各通路の片壁ごとに10個ずつ壁を減らすことができますが、代わりに通路の面積が増えるのでペットがなかなか部屋に入りにくくなるのではないかという懸念がありました。
ただ実際に実装してみると、部屋に入りにくくなるデメリットを遥かに上回る壁削減効果があり、0.6Gくらいスコアが伸び、5G台に突入しました。
もちろんこのパターンも3列、4列、5列パターンを用意しました。壁削減効果は絶大で、これまでの部屋パターンが選ばれることがほとんどなくなってしまったので、これまでの部屋パターンはここで廃止しました。
列担当の廃止
上記の壁を減らす過程で、壁を最初に作らずに随時作っていくという実装の必要性から、人を列に割り当てる考え方を廃止しました。人を列をまたいで安全に移動させるというのはそれなりに難しい点はありましたが、この頃には色々な実装でパーツが揃ってきていたので何とか実装できました。これは0.1G程度の改善効果でした。
最終緊急捕獲
最終的にペットの捕獲に失敗するケースで1匹だけが残り数十ターンを延々と逃げているケースがあることに気付きました。見てみると、削った壁のあたりでオロオロしている牛や豚、通路を逃げ続けて翻弄する猫というようなパターンがありました。
少しでも何とかしたかったので、残り数ターンで最後の一匹だった場合は、1部屋で捕まえることは諦めて、隣り合った2部屋＋その間の通路を使って緊急捕獲することを試みました。
これまでの実装の色々な前提を覆すことになるので、最後の一匹以外には発動しませんでしたが、コンテスト最終盤で0.1G程度伸ばすことができました。
その他の細かい工夫
上記以外の細かい部分で工夫した点を箇条書きしておきます。主にビジュアライザで点数が低いケースを見ていて気付いた内容の対策です。
- 列をまたいで人が移動する時、封鎖を試みようとしている部屋は通らないようにする
- 何もすることがなくなった人は、ひとまず部屋から出る(その部屋を封鎖すると人が分離してしまうので)
- 終盤残りペットに対して人が余ってきた時のため、部屋の封鎖や通路を追うときに、余剰人員も近くに連れてくるようにする(そうすることで逃れられた場合のバックアップ要員にできることがある)
- ペットの動きのシミュレーション時に壁の形決め打ちで部屋をまたぐ移動は1ステップで行けるようにしてbfsを高速化しました
最終解
こんな感じになりました。seed=0で64,111,111点の動画です。5列パターンが使用されています。
おわりに
今回のコンテストは相性が良かったようで、AHCでは初めて1ページ目に入ることができました。この記事が何かのお役に立てば幸いです。