simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Marathon Match 137 StoneSeries 参加記

問題

www.topcoder.com

方針

2種類のビームサーチによる探索

  • 通常のビームサーチ
  • 最長パスを見つけるためのビームサーチ

ビーム幅がある程度確保出来る場合は通常のビームサーチをそうでない場合は最長パスを見つけるためのビームサーチを使用しました。

最長パスの探索

今回の問題ではなるべく大きな値の石を置くことで獲得出来るスコアが増えるので、大きな値の石を置くために最長パスを探索しました。

パスの伸ばし方

パスを伸ばすのは 1の石を使うことで可能となります。

任意の石の周辺の空きマスに対して +1 した石を置きます。

このままでは「2以上の石を設置する場合は周辺に 2個以上の石が必要」という条件に反するので、さらに周辺のマスを探索して 1が置けるマスを探して設置します。

条件に反していない場合はそのまま +1 した石を置き続けることが出来ます。

このように 1の石の周辺は +1 した石が置きやすくパスを伸ばすのに非常に役に立つので、この動作を続けることで長いパスを作成することが可能になります。

ビームサーチによるパスの探索

パスの伸ばし方はわかりましたが適当に探索してもいい感じのパスを見つけてはくれないので 2つほど大きな指標を与えてなるべく大きなパスを見つけてくれるようにしました。

  • 石を置く際にはなるべく斜め置きを避けるようにする
  • なるべく外側からマスを埋めるようにする

探索については以下の通りです

  • 画面端の任意の位置を選択してそこから開始
  • 周辺 8マスの空きマスを探索し「現在の値 + 1」の石を置く
    • 周辺に 1の石がない場合は 1の石を置ける場所を探して置く

斜め置きを避ける

石の影響範囲の関係上、斜めに移動するよりは縦 or 横に移動するほうが 1の石をより効率的に利用出来るので斜め移動に対してペナルティを与えています。

斜め移動と横移動を比べると横移動のほうが効率よく 1の石を利用できている。

外側のマスを埋めるようにする

長いパスを作ってもらうためになるべく端を詰めながら移動して欲しかったので、グリッドの中央からどれだけ離れているのかを各セルに対してスコア化してその合計値を評価しました。

こうすることでなるべく端のマスを通りながら移動する経路を評価することが出来たと思います。

この探索で見つける経路は以下のようなイメージになります

パスの反転

この探索で見つけたパスは基本的に「外側 -> 内側」へと向かうのですが、この状態だと値の大きな石が中央付近に来ることになります。値の大きい石の周辺は周辺の合計値が大きくなってしまうので利用が難しく空きマスを多く無駄にしてしまう可能性があります。そのため、なるべくブロックの多いマスに追いやって影響を弱くしたいです。

幸い、見つけたパスは始点と終点をちょっと変更すれば逆向きに出来ます。逆向きにすることで「内側 -> 外側」に向かう経路となり大きい値の石を画面端に追いやることが可能となり影響力を弱めることが出来ます。

逆向きにした経路

最初から「内側 -> 外側」に向かう経路を探索すればよいのではと思うのですが、自分の評価関数だと「内側 -> 外側」の経路を作ろうとするとうまく画面端にピッタリくっつくような経路が出来なかったのでこのような反転処理を入れています。

残った空きマスを探索して石を置く

経路を作り終わった後は残りのマスをビームサーチで探索して得点が大きくなるように石を置きます。

時間制限まで処理を繰り返す

ここまでの処理が 1セットで、後は制限時間の間「経路の初期位置」「斜め移動のペナルティの値」「画面端ボーナスの値」をランダムに変えながら繰り返して一番高いスコアが得られたものを採用します。

通常のビームサーチ

「グリッドのサイズが小さい」 or 「ブロックの比率が高くて最長経路の探索が困難」な場合は普通のビームサーチで探索を行いました。

こちらに関しては特筆することも無く。評価としては主に以下の通り

  • 盤面の石の値の合計値
  • 画面端に値の大きい石が存在しているかどうか

後は zobrist hash による重複排除を行っています。

感想

問題自体はシンプルだったが、シンプルが故に評価が難しかったです。小さいサイズでのビームサーチの結果を見るに最長経路を作るよりかはいかにして空きマスを少なくするのかが重要っぽい感じではあるのだが、いい感じの評価関数を見つけれられずに終わった。最長経路を作らずにビームサーチをしたほうが得点は高くなるのでなるべくビームサーチに置き換えたかったがどうしてもグリッドサイズが大きくなるとビーム幅が十分に確保できなくなってしまうので諦めた。

そのビームサーチも評価関数があまり良くなさそうなので改善する余地はいくらでもありそう。「評価関数を良くする」->「ビーム幅が少なくても高スコアが取れる」->「ビームサーチ出来るグリッドのサイズが増える」->「得点がUP」という感じになるはずなので後半は評価関数の改善に主に力を入れてたけどダメだった。

Seed 1: 263.0
Seed 2: 289489.0
Seed 3: 154934.0
Seed 4: 174324.0
Seed 5: 154501.0
Seed 6: 10181.0
Seed 7: 1289.0
Seed 8: 5684.0
Seed 9: 11545.0
Seed 10: 97828.0

TCO22 Final に進出しました

TCO22 Final に進出

公式の順位表が更新されて Stage 4 のポイント集計に自分がカウントされていなかったので、去年に引き続き今年も TCO Final に出れるっぽいです(やったー)、去年は 4 -> 2 -> 4 の 200pt での突破でしたが、今年は 3 -> 7 -> 4 の 175pt での突破になりました。

TCO22 - Marathon

4位 とは 5pt 差でギリギリの戦いでした。

MM132

1, 2位とかなり離されたので結果としては残念だったがポイント的には 75pt 取れてラッキーだった回。3回のうち 1回でも高順位を取れると Final がぐっと近づくので本当によかった。

MM133

苦手な推定系の問題。当時流行っていた wordle を題材にした問題で、方針が全くわからず右往左往してたがなんとか 7位で耐えることが出来た。

MM134

比較的得意なマルチエージェント回。 Daiver19 さんより順位を上回らないといけない状況だったので個人的には絶望していたがなんとか勝てた(勝率 1割ぐらいだったので)

感想

方針を 2回外して突破できたので本当にラッキーという感じ。去年は 8位という下馬評通りな感じの順位で終わったので今度はそれより上の順位を目指したい。

AHC011 Sliding Tree Puzzle 参加記

問題

atcoder.jp

方針

主に 3つのパートで構成されています

  • 与えられたパネルから木を構築する
  • 構築した盤面の各パネルに対して数字を割り振る
  • (N * N - 1) puzzle を解く

木の構築

木の構築は盤面を焼き鈍して作成を行いました。木の条件が厳しそうなイメージだったので「パネルの交換だけで出来るのか?」と疑問だったのですが実装してみたら意外と速く構築出来て驚きました。

近傍としては「2つのランダムなパネルを選択して入れ替える」の 1つでしたが選択時に色々と制限をかけています。

同じ種別のパネルを選択しない

同じ種類のパネルを入れ替えても状況は変わらないのでそれは行わないようにします

確実に悪い配置とわかる場合は除外する

「確実に悪い配置」というのは「そこにパネルを置くと絶対に木が完成しない」状態を指します。

図のように画面端に向かって枝が伸びているようなタイルが存在する場合は絶対に木が完成しないので、このような配置にならないように選択を行っています

どちらかは必ず接続状態を維持するようにする

タイルを交換する際にどちらのパネルも接続状態が途切れてしまう場合は交換を行いません。

例えば緑のマルで囲まれた部分を交換すると両方のパネルとも周辺のパネルと接続状態が途切れてしまいます。このような場合は交換を行わず再度タイルの選択をやり直します。

評価値

盤面状態の評価は「連結成分の個数 + 元の盤面からどれだけ近いか」で計算を行いました。

連結成分の計算は盤面全体を DFS で探索して計算を行っています。

元の盤面状態からどれだけ近いか

今の位置から元のパネルの種類の最短距離を計算してその合計値が少ない状態を良しとしています。

評価値については事前に計算しておきます。図は評価値の事前計算の一例です

種別 9 のタイルについて評価を行います

各マスについて種類 9 のパネルとどれだけ離れているのかを計算し dy * dy + dx * dx の最小値をテーブルに保存しておきます。

盤面評価の際はすべてのマスについてこの値を合計したものを利用しています。(この値が大きいほど元の盤面から乖離している ≒ 元に戻す手数が多いと考えられます)

(コンテストの途中、元の位置の距離 (dy * dy + dx * dx) をコストにしてみましたが、特にスコアに変化がなくただ試行回数が減っただけなのでこの評価値をそのまま採用しています)

焼きなましの打ち切り

盤面構築の際にどんなに試行回数を重ねても連結成分が減らない局所解に陥ることが多々あったので、 10万回スワップを行って 1回もスコアの更新が発生しなかった場合は処理を打ち切りました。

破壊的な近傍を用意して局所解からの脱出を行うよりも再実行のほうがコスパが良かったのでそうしています。

複数繰り返して色々な盤面を得る

1回の焼きなまし処理はだいたい 0.1 sec で終わって、盤面が得られる確率が大体 50% ぐらいだったのでこの処理を設定した時間 (今回は 1.7 sec) が来るまでに複数回実行して、様々な盤面を取得します。

構築した盤面の各パネルに対して数字を割り振る

完成した盤面に対して数字を割り振っていきます。割り振りには最小費用流を使用し、辺のコストには元の盤面からの距離 dy * dy + dx * dx と 1 ~ N のランダムな値で計算しています。ランダムな値を追加しているのは距離だけの評価だと毎回同じ数字の割り振りになってしまい、もし出来上がったものがパズルとして達成不可能な場合に数字を振り直したいのでランダムな値を追加して別の割り振りパターンになるようにしています。

パズルの達成が可能な盤面でコストが一番低くなるものを最終的に解く盤面として採用します。

完成可能かどうかの判定は以下のサイトを参考にしました。

manabitimes.jp

外周に近いマスのコストを高くする

n-puzzle は真ん中を先に揃えても後で壊される可能性が高く、基本的には端から揃えていきたいのでコストを計算するときに端のほうのコストが高くなるように設定しました。

配置コスト 5 + 9 = 14

配置コスト 4 + 10 = 14

画像では両方とも同じコストになるので距離のみの評価だとどちらを選んでも良いのですが、実際にはこの距離コストに係数を掛けたものを利用しています。

係数の値は端に近いほど高くなるように設定しています。(実装的には max(y, N - y + 1) みたいな感じです) この係数を使った場合は以下のような結果になります。

配置コスト(new) (4 * 5) + (6 * 9) = 74

配置コスト(new) (6 * 4) + (4 * 10) = 64

結果として、端のタイルはなるべく短い手数で済むような配置になります。(スコアとしては 2 ~ 3000 点ぐらいの向上)

(N * N - 1) puzzle を解く

盤面構築が終わったら後はパズルを解くフェーズになります。今回はビームサーチを利用しました。序盤は高速化が足りてなくて N が大きいケースでは外堀を埋めるルールベースを書いていましたが明らかに手数が多くて悪手だと感じていたので最低限のビーム幅が確保できる状態まで高速化しました。

評価関数

盤面の評価としては主に元の盤面からの距離から計算されるコストと Linear Conflict を少し改造したものを使用しました。(あと端が揃っているかどうか)

距離による評価

元の位置との縦軸の距離の差分 (dy) 横軸の距離の差分 (dx) を調べて、 dy * dy + dx * dx をコストとして計算します。 dy + dx のマンハッタンディスタンス (MD) の場合だと同じ評価値で揃える難易度が全く異なるものが発生しそうだったので2乗の方を採用しています。

特定のパネルを任意の位置に移動させたい場合に「同じ方向に連続で移動する」という動作がかなり手数を使ってしまうので、それを避けるようになるべく「縦の差分」と「横の差分」の差が少ないほうがコストが低くなるように設定しています。

端を揃えた状態の評価

n-puzzle では端が完成するとそれ以降は端を操作する必要がなくなるので、端が揃った場合はボーナス得点を与えています。

ただ、画像のように一部の端だけが完成し続けると最終的に端を崩さないと完成しない状況になりうるのでこのボーナスは「画面端から距離 Xの場合に有効とする」 といった感じで変数を使って制限を加えていました。(変数の値としては盤面のサイズの半分を超えないように設定しています)

隣接マスの関係性の評価

盤面全体をみて評価出来たほうがより精密に評価を出来るようになるとは思いますが、今回は高速化の都合上 1回の移動で変動したタイルの隣接マスだけを見て評価を行いました。

Linear Conflict

Linear Conflict についてはこちらのページを参考にしました。

michael.kim

隣接マスをみて完成図の同じ行 or 列に所属していて番号が逆転していた場合はペナルティを与えています。

特に、お互いが後 1手で完成する同士であった場合はより重いペナルティを与えています。(角でこれをやられるとかなりの手数を消費するので)

後はお気持ち程度の評価ですが、同じ列 or 行に所属していない場合でもゆるくペナルティを与えています。

本来であれば 97 の左側に来るべきなので減点する。

あと 1手同士が隣接している場合にボーナス

15 puzzle の攻略サイトを調べていると「後から車庫入れ」という形になっているとパズルがスムーズに解けるということだったので「残り 1手同士が隣接している」状態にボーナスを与えました。

studio-boiler.com

なので画像のような盤面状況が評価されることになります。

ボーナスとしては小さい値でしたが外すと 2 ~ 3000 下がったのでそれなりに有効だったみたいです。

zobrist hash による重複排除

同じ盤面を探索しないように zobrist hash による重複排除を行っています。重複排除の処理を外すと得点が 10000 下がったのでかなり効果があったみたいです。

Zobrist hashing - Wikipedia

感想

方針自体は maspy さんが初日に 38,307,047 を叩き出していたのでかなり早い段階で決まりました(n-puzzle を構築してそれを解く)あとは、手数を短くするために盤面構築の精度を上げるか n-puzzle solver の精度のどちらを上げるかでちょっと迷っていましたが最終的には solver の精度を上げたほうが良さそうだと思ったので評価関数を色々試してはみましたが 1位に追いつくことが出来ませんでした。

ビームサーチが題材の場合は評価関数を頑張らないとどうにもならないので(ビーム幅を 10倍にしても 1位のスコアに追いつけない)、15-puzzle の資料を色々読んでいましたが 4 * 4 というサイズの小ささに特化した手法が多くて Linear Conflict のような汎用的なものを見つけることが出来ませんでした。(本当はあったかもしれないけどそこは調査力が無かったということで)

ところで 6/23 2:00 から Marathon Match 137 が始まる予定なので興味がある方は是非参加してみてください。(世界大会に向けての予選なので恐らく強い人がたくさん参加する可能性が高いです)

リンクは参加方法についてのガイドラインになります。

www.topcoder.com

今回の問題では「焼きなまし」と「ビームサーチ」というマラソンマッチにおける基本的な探索手法を同時に扱えたのでとても面白かったです。個人的には AHC の時間制限を 10sec あたりまで伸ばしてくれたら時間管理をもっとゆるく行えて気持ちが楽になりそうだなと思っています。(自分の評価関数だとへたにビーム幅を下げると解が見つからない可能性があったのでこのあたりの調整がちょっと面倒でした)

MM136 HungryKnights 参加記

問題

www.topcoder.com

今回のスコア計算では同色の移動を連続で行うことで指数的にスコアが増える仕様となっていたので、出来るだけ長い同色消しの経路を作成する必要がありました。

方針

基本的な方針はビームサーチでの経路探索になります。

スタート地点の選択

長い経路を作りたいので、盤面にあるマスの色をカウントして一番多い色から消していきます。どのマスからスタートするかはランダムに決定しました。

移動先の決定

現在位置からの移動の候補は 8種類あり、移動先が同色かそうでないかで処理を分けます。

同色の場合

同色の場合は特に処理を行わずそのまま移動します。

違う色の場合

色が違う場合は別のマスから対象の色を持ってきて遷移するようにします。

移動先が別の色でこのままだと連鎖が途切れてしまう。

別のマスから同じ色の駒を持ってくる。

移動が可能になる。

この「別の駒を持ってくる処理」については連鎖中に行ってしまうと連鎖が途切れてしまうので、まとめて連鎖用の経路の前処理として実行します。

評価関数

処理後の盤面評価についてですが主に以下の点を重視しました。

  • 残っているマスの個数
    • マスが残っているほど移動に自由が効いて連鎖を作りやすくなる
  • 画面端に近いマスを消していると高得点
    • 画面端のマスは残りやすいため、なるべく残らないように評価を高くしておく
  • 次に消す予定の色を残すようにする
    • 他の色でも大連鎖を組みたいのでなるべく残すようにする
    • その色だけではなくて周辺のマスも消さないようにする

その他

細かいスコアを取るためにやったこと、連鎖スコアに比べると些細なものなのであまり細かく詰めてはいない。

貪欲

連鎖も作れなくなったあとは残った駒を貪欲に消していきます。

挿入

最終的に使われない駒で、その周辺で処理を挿入できそうな箇所があれば変更を行います。

右上の青が最後まで使われなかった場合

「紫」→「黄色」と移動を行っているが、「青」→「黄色」 +「紫」→「青」 のほうがスコアが高くなる場合は「青」→「黄色」の処理を挿入する。

事前同色消し

残った駒の周辺に同じ色の駒がある場合は事前に同色消しを行っておきます。

先程と同様に青が残っている状態

事前に同じ色を使って消しておくことで 1点もらえる

感想

ビームサーチで評価関数勝負かと思ったら 1位は焼きなましだった。2色同時探索はちょっと実装しようかなと思ったけど、焼きなましはちょっと思いつかなかった。とりあえず実装してみてどのぐらいのスコアが出るかは確認したほうが良かったかもしれない。(初手のビームサーチで良いスコア取れたからそれに引きずられた感はある)

2割、3割スコアが離れてたら方針を疑ったかもしれないけど 1割以内で Psyho さんだったしなんかいい感じの評価関数があるのかなと思ってしまった。

Marathon Match 134 ShearTheSheep 参加記

問題

www.topcoder.com

戦略

  • どの農家がどの羊を追いかけるかの割当を最小費用流問題として解く
  • 対象への最良経路を探索
  • 羊毛のバケツリレーを行う

農家と羊の割当

どの農家がどの羊を追いかけるのかを最小費用流問題として解きます。辺の張り方としては「農家」→「羊」となるようにし、フローの量は「農家の数」とします。

f:id:simanman:20220324211559p:plain:w480

辺のコスト

S →「農家」は 0、「羊」→ T は 0、「農家」→「羊」についてはそれぞれコストを計算するための関数を使って定義を行います。また、各辺のキャパシティは 1 で定義します。

コスト計算では以下の要素を考慮します。

  • 対象との距離
  • 対象の羊毛の量
  • 周辺の羊毛の量
  • 納屋までの距離

対象との距離

対象までの距離をダイクストラ法で求めます。

距離が 4以下の「羊」については「壁」「木」と同様に通れないオブジェクトとして扱い、それ以上の距離にいる「羊」については距離に応じたペナルティを与えます。(ペナルティの係数は optuna で調整)、「農家」ついては交差したとしても羊毛を受け渡しが可能なので特にペナルティ無しで通過出来るようにしています。

羊毛の量

羊毛の量が MAX の時に成長のタイミングが来ると狩れるはずだったの毛の成長が行われないので実質スコアの減少となります。そのため、羊毛の量が MAX の状態の羊を優先的に狩るようにしました。

周辺の羊毛の量

保持できる羊毛の量 C が多い場合は連続で毛を狩るようにしておくと得点効率が良いので、対象の羊毛の量だけではなく周辺の羊毛の量も調べてそれも評価します。

納屋までの距離

ある程度羊毛を集めると納屋に戻って収める必要があるので、納屋までの距離も評価します。(この評価値はある程度羊毛を集めた農家だけに適用)

「農家」→「納屋」の辺を追加

ある一定量の羊毛を集めた農家に対しては「納屋」への辺の追加を行います。「納屋」→ T のコストは 0、 キャパシティは無限(農家の数より大きな値であれば何でも良いです)で定義し、「農家」→「納屋」のコストについてはダイクストラで計算した値に設定します。

f:id:simanman:20220324215816p:plain:w480

対象への最良経路を探索

目的への経路をダイクストラ法で探索します。「羊」との距離を詰める場合は、羊側の行動によって距離が短くなる候補が多くなるように行動します。(基本的にはY軸とX軸の長い方を短くするような動きになります)

羊毛のバケツリレー

納屋の数が少ないケース等では羊毛を収めに来た農家が詰まってしまうので、詰まった状態でも羊毛を納屋に収めれるようにします。

f:id:simanman:20220324235644p:plain:w320

f:id:simanman:20220324235723p:plain:w320

f:id:simanman:20220324235835p:plain:w320

f:id:simanman:20220324235902p:plain:w320

農家の行動順を入れ替えて納屋までの羊毛の受け渡しを 1ターンで終了させるようにすることで詰まること無く羊毛を収めることが出来るようになります。意図的にリレーを行うというよりかは詰まった時にこの機能が無いと不便だよねという感じです。

感想

2次元グリッドベース + マルチエージェント系の問題。スコア計算が線形的なとの「これをやれば爆発的にスコアが伸びる」みたいなのも特に無かったので、基本的な実装は前半で終わってしまって、後半は地味なチューニング作業が多くなってしまった。焼鈍系の問題が減った代わりにオンライン系の問題が増えてきた印象がある。いい感じの評価値もといコスト計算を行う方法が全然わからないので、機械学習でその辺りを改善できるなら実装していきたい気持ちがある。

optuna 今までは Best parameters しか見てなかったけど、今回は Visualization 機能でパラメータとスコアの関係を俯瞰的に見れて便利だったので今後も機会があれば使っていきたい。(本音はチューニングじゃなくて方針で差がつく問題をやりたい)

Seed  1: 251
Seed  2: 6048
Seed  3: 4250
Seed  4: 403
Seed  5: 1179
Seed  6: 187
Seed  7: 1997
Seed  8: 639
Seed  9: 1406
Seed 10: 382

第8回 Asprova プログラミングコンテスト 参加記

問題

atcoder.jp

方針

  • 製造する製品の(形状、色、生産個数)をまとめて タスク という形にまとめる。
  • タスク を行う順番を焼きなましで更新していく
  • 順番が確定した後 生産個数 の部分を別の焼きなましで改善していく

タスクの作成

製品を 1個ずつ扱うと計算量が大きくなってしまうのと、基本的に切り替えのコストが大きいのである程度製品をまとめて生産するほうが良くなります。

f:id:simanman:20220313221455p:plain:w480

今回は初期の生産個数を N[s][c] / K[s] と定義してタスクの生成を行いました。

焼きなましによる生産順番の改善

焼きなましによって生産の順番を改善していきます。遷移としては以下の 3つになります。

  • 任意の 2つのタスクの順番の入れ替え (swap)
  • 2-opt
  • 任意の 1つのタスクの位置の入れ替え (insert)

スコア計算ですが1回のループで生産できる個数に制限が存在しているのと、前に設置したハンガーの再利用を考慮すると差分計算が出来ないため、基本的には再計算を行っています。 また、スコアを厳密に計算してしまうと必要な試行回数を稼げないためある程度簡易化したものを利用しました。(簡易版で試行回数 2M 程度)

簡易版では「再利用できるかどうか」の判定を簡略化しており、大まかに「前に設置した形状 s とどれだけ間隔が離れているか」を評価の基準としています。(間隔が H に近ければ近いほど評価しています。)

f:id:simanman:20220313223507p:plain:w480

また、個数制限についても「直前に設置したタスクの生産個数との和が制限を超えているかどうか」だけで判定しており、この辺りの精度も落としています。

ただ、ベストスコアに関しては完全版のスコア関数を利用して比較を行います。

生産個数の焼きなまし

順番を確定させた後に、生産個数について別で焼きなましを行いました。一緒にまとめてやってしまうと非常に複雑化してしまって全然安定しなかったので「順番」→「個数」と別々で行っています。遷移としては「任意の製品を選び生産個数を変動させる」というものになります。

f:id:simanman:20220314041146p:plain:w480

ここでのスコア関数は完全版を使用しています(制限時間は 0.2 sec 程度で試行回数が 20K 程度)。

感想

焼きなましの試行回数が全然稼げず終わってしまいました。簡易版を使用して誤魔化したのですがそれでもまだ足りなかったです。 「切り替えコストを少なくして、なるべくハンガーを再利用出来るようにする」と頭の中では理解していたのですが、結局それをどう評価していけばよいのかがわからず終わってしまいました。良い評価関数を作るにあたってデータ集めと解析を怠ってしまったのは個人的には反省です。

ラソンマッチにおいては「改善できなくなったら負け」なので、継続的にスコアを改善できるような仕組みを考えていきたいですね。

AHC008 Territory 参加記

AHC008 に参加していました。

atcoder.jp

方針

大きく分けて「柵を配置する」「動物を捕まえる」の 2つのフェーズでゲームを進めていきます。

  • 複数人で 1つのチームを作ってチーム単位で行動を行う
  • 部屋の中に予め設定しておいた柵を配置する
  • チーム単位で動物の捕獲を行う

f:id:simanman:20220228054037g:plain:w480

チームの作成

1人でペットを追いかけても捕獲するのが非常に困難なので、複数人で対象の動物を捕獲します。人間の数にもよりますが基本的には 2チームに分かれて捕獲を行います。

f:id:simanman:20220227234400p:plain:w480

f:id:simanman:20220227234638p:plain:w480

人間の数によってチームのメンバー数と編成数は変化します。

  • 5人 (3, 2)
  • 6人 (3, 3)
  • 7人 (4, 3)
  • 8人 (4, 4)
  • 9人 (4, 3, 2)
  • 10人 (4, 3, 3)

柵の配置

今回はグリッドサイズが 30 * 30 で固定だったので、前もって柵を配置する場所を決めておいてそれに元に柵の配置を行います。 今回自分は全部で 11個の配置パターンを用意しました。

基本的には図のような配置になります

f:id:simanman:20220227204949p:plain:w480

ポイントとしては主に以下の 2点になります

  • 人が横移動するだけで捕獲が可能
  • 犬、猫を捕獲するための通路の作成

その他の配置パターン M = 5

f:id:simanman:20220228010722p:plain:w480

M = 6

f:id:simanman:20220228010900p:plain:w480

M = 7

f:id:simanman:20220228011335p:plain:w480

Mが小さいケースでは 4ラインだと人が足りなくなってしまうので 3ラインに減らしています。 また、M が 7以下の場合は 1回の横断で柵を設置しきれないため、柵の数を少なくしてなるべく早く設置出来るようにしています。

M >= 8 かつ動物の数 <= 12

f:id:simanman:20220228054436p:plain:w480

人間の数が多くて動物の数が少ない場合は柵を多少減らしても達成率に影響が無いので、なるべく少ない柵の設置で目標が達成出来るようにパターンを修正しています。

横移動のみでの捕獲が可能

柵の設置が終わると水色のラインに人を割り当て、後は対象のペットに対して横軸を合わせるだけで捕獲が可能になります。

f:id:simanman:20220227225856p:plain:w480

チームは横軸を合わせて行動することでペットが捕獲範囲に入ってきた際にすぐに捕獲出来るようになります。

f:id:simanman:20220227235928p:plain:w480

その他の配置箇所

M = 5 (3人, 2人)

f:id:simanman:20220228012542p:plain:w480

M = 6 (3人, 3人)

f:id:simanman:20220228012633p:plain:w480

M = 7 (4人, 3人)

f:id:simanman:20220228012822p:plain:w480

M = 8 (4人, 4人)

f:id:simanman:20220228014643p:plain:w480

M = 9 (4人, 3人, 2人)

f:id:simanman:20220228014812p:plain:w480

M = 10 (4人, 3人, 3人)

f:id:simanman:20220228014905p:plain:w480

犬、猫の捕獲

今回の問題では完全にランダムではない行動を行う動物として「犬」と「猫」の 2つが用意されていました。 これらの動物は最初の行動が「目的地に近い方向に移動」というものなので、通路を用意してあげればそこに勝手に入って来てくれて捕獲することが出来ます。

f:id:simanman:20220228020956p:plain:w480

乱数次第ではずーーーっと横移動だけを行い通路を使ってくれないパターンもあるとは思いますが、基本的にはそのようなことは発生しないので特に問題はありませんでした。

通路の長さは 4以上を確保する

「犬」「猫」「豚」に関しては移動距離が 2であり、 移動前と移動後の (x + y) の偶奇が変化しないので最小効率の 3の通路で捕獲しようとすると捕まらない可能性があるのでそれを避けるために 4以上の長さを確保する必要があります。

f:id:simanman:20220228022115p:plain:w120

この場合、緑マスに止まる「犬」「猫」「豚」は絶対に捕獲することが出来ません。

f:id:simanman:20220228022323p:plain:w120

長さを 4以上にすることでどちらの場合でも捕獲可能なマスが存在するようになります。

通路から出ようとしている「犬」「猫」は積極的に捕まえに行かない

例えば図のような状況下で最初の行動が下方向だった場合、絶対に通路内に入ってくることは無いので捕獲対象としての優先度を下げるようにします。

f:id:simanman:20220228024814p:plain:w120

その場待機 or 通路からの脱出のいずれかの行動になるので追ってもあまり意味がないです。

f:id:simanman:20220228025008p:plain:w120

通路に入ろうとする「犬」「猫」は捕まえに行く

図のように通路の中に入っていく動きをしている場合は高確率で通路内に侵入してくる可能性があるので捕まえに行きます。

f:id:simanman:20220228025745p:plain:w120

最後の 1匹を無理やり捕まえに行く

今回のスコア計算ではペットが 1匹残っているだけでスコアが半分になってしまうので、最後の 1匹に関しては無理やり捕まえに行きます。

その時に使用する捕獲のパターンです。(画像は M >= 8 の時に使用するもの)

f:id:simanman:20220228030957p:plain:w480

赤いマスの部分は最後に部屋を閉める場所になっています。

最後の捕獲に関してはゴリゴリに if 文を書いてるのでかなり無理矢理な実装になってます。

f:id:simanman:20220228031600g:plain:w480

牛が全然捕まってくれず最後に捕まえにいっている様子がわかると思います。

「最後の 1匹ではなく 2匹だともっとスコアの取りこぼしが少ないのでは?」と思ったのですが、この方針だと捕獲までにかかる柵の数と閉じ込めた際の空間の消費量が「待ち」の戦略に比べて増えてしまうので、全体的なスコアとしては下がってしまったので採用しませんでした。

感想

今回は比較的得意な分野(二次元グリッド + マルチエージェント)だったので、特に大きく方針を外すことなく実装出来たかなとは思います(1位のスコアの 9割が毎回の目標値 - 今回だと20位辺り)。柵の配置を固定ではなくて不定形にすることで 7G あたりのスコアが出ることは確認していたので (seed 0 で確認 77111111)、もう少し期間があればそっちの方針も試していたのかなとは思います。(不定形だと犬 & 猫の捕獲は難しいので「犬」「猫」「その他」で戦略を切り替える。このあたりを実装してきて 7G ぐらいを出す人が出てもおかしくないなとは思ってました)

f:id:simanman:20220228045142g:plain:w480

もし他のヒューリスティックコンテストに興味があるという方は 3/17 2:00 から Topcoder Marathon Match 134 が始まるので是非参加してみてください。(ただし、こちらに関してはコンテスト期間中の解法や考察に関する言及は禁止となっているので注意が必要です)

使用素材

サラリーマン(事務職) | ドット絵ダウンロードサイト DOTOWN

茶色のネコ | ドット絵ダウンロードサイト DOTOWN