Marathon Match 146 HappyGrid 参加記
問題
最終提出コード
https://gist.github.com/siman-man/f8e9022891d996d36d5f505f67ff929d
方針
「盤面の作成」「ボールの移動」の 2つのフェーズがあります。
- 焼きなましによる盤面の作成
- 最小全域木を作成し葉の頂点を埋めるようにボールを移動させる
盤面の作成 (start ~ 9.0 sec)
まず最初に高得点が得られるような盤面の作成を焼きなまし法を用いて行います。遷移としては最初にランダムなボールを 1つ選択し、そのボールの元の位置からマンハッタン距離が 4以内の座標をランダムに選択してその位置と入れ替えるという処理を行っています。
最初はランダムな 2点を選んでスワップを行っていましたが、完成後の盤面を眺めているとほとんど元の位置から動いていないので選択する座標を制限するようにしました。（オレンジで色塗られている部分がスワップ対象の範囲になります）
スワップ後は盤面のスコア計算を行います。スコアは「連結サイズ」「ボールの元の位置からの距離」の 2つで構成されています。
連結サイズスコア
ボールの連結サイズによってスコアを決定します。スコア関数は下記のようにしました。
int calc_size_score(int k) { if (k == K) { return P; } else if (abs(K - k) <= 1) { return P / 8; } else { return -1 * abs(K - k); } }
距離スコア
ボールが元の位置からどの程度離れているかによって決定されるスコアです。距離が 1離れるごとに 2点減点を行っていきます。
g_distance_penalty[cz][z] = 2 * dist;
盤面作成パートの制限時間は 9.0sec に設定していて試行回数は大体 2000万回程度となっています。ここで求めた盤面を元にボール移動フェーズへと進みます。
ボールの移動 (9.0 ~ end)
ボールの移動は以下の処理を繰り返して行います。
- 移動先の対象となるセルを選択
- 選択したセルに必要な色のボールまでの経路を探索
- ボールを探索した経路に沿って移動させる
セルの選択
まず盤面に対して最小全域木を構築し、葉に該当する部分のセルを選択します。対象が複数存在する場合は盤面の中心からマンハッタン距離が一番遠いものを選択します。（オレンジ色の部分が対象となるセルの一覧になります）
必要な色のボールまでの経路を探索
選択したセルからスタートしてそのセルに必要な色のボールまでの経路を探索します。経路探索にはダイクストラ法を用いています。経路としてはなるべく全体の移動回数が少なくなるような経路を選択するようにしています。大まかな条件としては以下のようになっています。
- 既に移動済みのボールの上は通らない（壁として扱う）
- 移動時のスワップを行った際に既に完成後の盤面の色の配置と異なる色のボールが来る場合は減点
- 同じ色のボールが来る場合は加点
経路を発見したらそれに沿ってボールの移動を行います。移動後はその位置を固定化して木の更新を行います。
これをすべてのボールの配置が完了するまで繰り返します。
時間制限一杯繰り返す
最小全域木を作る際には辺のコストをランダムに設定して毎回違う形の最小木が出来るようにして、この「木を作る」「ボールを配置する」の処理を時間制限一杯まで繰り返し行い目的の盤面を作成するまでの手数が一番少ないものを採用します。
感想
上位との点差がかなり僅差なので細かいところを詰めてるか詰めてないかで差が付きそう。最終日ほとんどパラメータ調整しかしてないので戦うための手札が少ないなと感じた。（毎回これ言ってる気がするな。。。）
あと、最後の移動を構築する部分は時間があればビームサーチを使用してもっと最適なものを選べた気がするけど時間が無いので諦めた。（期間的にも制限時間的にも）
