概要

私の解法では、差分更新ビームサーチを用いて操作列を 1 手ずつ伸ばしました。

探索対象は、基本操作 \(F\), \(L\), \(R\), \(S\)、登録済みマクロの再生 \(P\)、および特殊操作 \(P_{\mathrm{M}}\) です。

\(P_{\mathrm{M}}\) は、過去改変によりマクロを決め、それを現在位置で即時に再生する操作で、詳しくは後述します。

評価関数

評価値は、残り距離、配置済みボールへのボーナス、残り基本操作数に関する補正の 3 つを組み合わせて作りました。

ここで、\(d(u,v)\) をマス \(u\) からマス \(v\) までの最短距離とします。

まず、状態 \(s\) における残り距離 \(D(s)\) を次のように定義します。

\[ D(s) = \sum_k d(p_k, q_k) \]

\(q_k\) はボール \(k\) に対応するかごの位置です。\(p_k\) はボール \(k\) の現在位置で、手に持っているボールについてはロボットの現在位置として扱います。\(D(s)\) が小さいほど、全体としてゴールに近い状態だとみなします。

次に、正しいかごに置けているボールへのボーナスを

\[ B(s) = \sum_{k:\ p_k = q_k} b_k \]

とします。

さらに、残り基本操作数に応じた補正を \(R(s)\) とします。これは、終盤に使える基本操作数の余力をある程度残すための項です。

以上を合わせて、評価値はおおまかに次の形です。

\[ \mathrm{score}(s) = D(s) - B(s) - R(s) \]

評価値が小さい候補を優先します。つまり、残り距離が小さく、正しく置けているボールが多く、終盤に使える余力も残っている状態を高く評価します。

バケット分け

単純に評価値だけで上位候補を残すと、似た状態ばかりが残りやすくなります。

そこで、候補を次のように、\(8N^2\)個のバケットに分けました。

\[ (\text{ロボット位置}, \text{向き}, \text{ボールを持っているか}) \]

各バケットごとに上位候補を残すことで、特定の位置や向きに探索が集中しすぎるのを防いでいます。

このバケット分けにより、評価値の良い候補を残しつつ、探索の多様性もある程度確保できます。

重複除去

状態の重複除去には Zobrist hash を使いました。

ハッシュには主に次の情報を反映しています。

• 各ボールの位置
• 登録済みマクロの長さ
• \(P_{\mathrm{M}}\) に関する待ち状態 (後述)

探索する操作

通常の状態では、次の操作を候補として展開します。

• \(F\)
• \(L\)
• \(R\)
• \(S\)
• \(P\)
• \(P_{\mathrm{M}}\)

ただし、\(L\)の直後の\(R\)など、明らかに無駄な操作は枝刈りしています。 また、\(P\)では連続する同一操作をまとめて処理することで少し高速化しました。

\(P_{\mathrm{M}}\) 操作

\(P_{\mathrm{M}}\) は、過去改変によって \(M \ldots M\) を置いていたことにする操作です。

例えば、過去のある区間に基本操作列 FRRFFS があったとした時に、この区間の前後に \(M\) を置いていたことにすれば、この操作列をマクロとして登録できます。その後、現在位置で \(P\) を押すことで、同じ基本操作列を再生できます。

探索中では、この \(M \ldots M\) の挿入と \(P\) の再生をまとめて \(P_{\mathrm{M}}\) という 1 つの特殊操作として扱います。

この方法により、探索中に \(M\) の開始・終了を細かく操作として選ばなくても、良さそうな過去区間を後からマクロとして再利用できます。

\(P_{\mathrm{M}}\) で \(M \ldots M\) を置ける区間

\(P_{\mathrm{M}}\) では、過去の任意の区間をマクロ化できるわけではありません。出力として矛盾しないように、\(M \ldots M\) を置ける区間にはいくつか条件を設けています。

主な条件は次の通りです。

• 区間の長さがマクロ長の上限以下であること
• 開始位置が、直前に \(P_{\mathrm{M}}\) で置いた \(M \ldots M\) の終了位置より後であること
• 終了位置が、最後に \(P\) を使った位置より後であること

登録するマクロの長さの上限値は最終的に 120 に設定しました。

\(P_{\mathrm{M}}\) の候補列挙

\(P_{\mathrm{M}}\) の候補は、過去の操作列上の区間 \([\mathrm{start}, \mathrm{end})\) として列挙します。

まず、\(\mathrm{start}\) を 1 つ固定し、\(\mathrm{end}\) を \(\mathrm{start}+1\), \(\mathrm{start}+2\), … のように右へスライドさせながら、区間を少しずつ伸ばしていきます。

各 \(\mathrm{end}\) に対して、\([\mathrm{start}, \mathrm{end})\)をマクロとして登録し、現在位置で再生した場合の状態を計算します。

\(\mathrm{start}\) を固定して \(\mathrm{end}\) を伸ばすことで、直前のシミュレーション結果に追加分だけを反映しながら候補を作れます。

また、\(P_{\mathrm{M}}\) は通常の操作と比べて少し特殊で、「過去の区間に \(M \ldots M\) を挿入し、さらに現在位置で \(P\) する」という操作です。

この操作をそのまま同じ世代で扱うと、ビーム内で候補の世代がずれて扱いにくくなるため、探索上は 2 ターン待つことにしています。

待ちターン数の情報もハッシュに入れておき、それらが同一視されないようにしました。

基本操作列の上限 \(T\) への対策

この問題では、出力操作列の長さだけでなく、マクロ展開後の基本操作列の長さにも注意が必要です。

マクロ展開後の基本操作は最大 \(T\) 回までしか実行されません。そのため、探索中に基本操作数を使いすぎると、終盤で全てのボールを運びきれなくなります。

そこで、進捗に応じた基本操作数の上限を用意しました。

進捗は、残り距離 \(D(s)\) を使って見積もります。初期状態での値を \(D_0\) とすると、進捗はおおよそ次のように表せます。

\[ \text{progress} = 1 - \frac{D(s)}{D_0} \]

この進捗に応じて、その時点で許される基本操作数の上限を決めます。

序盤では、まだほとんど進んでいないため、使える基本操作数を \(T\) よりかなり小さく制限します。
一方で、終盤では、解に近づいているため、上限を \(T\) に近づけます。

おおまかには次のような形です。

\[ \text{limit} = T \left( (1 - \alpha)\,\text{progress} + \alpha \right) \]

ここで、\(\alpha\) は序盤でも最低限許す基本操作数の割合です。

候補を作るときに、次の基本操作数がこの上限を超える場合は、その候補を捨てます。

これにより、序盤で遠回りしすぎる候補を落としつつ、終盤では必要な操作を許容できます。

ビーム幅

ビーム幅は固定ではなく、実行時間を見ながら調整しました。

各ターンで、展開した候補数と実際にかかった時間を観測し、残り時間内に探索を終えられる程度のビーム幅を推定します。

これにより、軽いケースでは広めに探索し、重いケースでは時間切れを避けるようにしています。

ビーム幅の調整では、残り距離 \(D(s)\) から残り探索ターン数を見積もり、残り時間を使い切れる程度に幅を動的に変更しました。