問題
方針
- それぞれの空間からランダムに座標をいくつか選ぶ
- シルエットAの回転方向は 0で固定、シルエットBの回転方向をすべて試して一番評価が良くなるブロックを選ぶ
- ブロック設置後に 1マス延長を試してスコアが良くなるなら採用する処理をスコアが改善できなくなるまで繰り返す
- 「設置」→「山登り」をシルエットが完成するまで繰り返す
- 途中置くところが無くなったらランダムなブロックを選んで全削除
- 完成したらリセットして最初からやり直し、時間制限いっぱいまで実行して一番良かったものを採用
パネルの重み付け
一番良い状態のブロックをどう評価するかについてですが、各パネルに値を付与してその値の合計値が高いものを良いブロックと評価しました。 パネルの評価については「その部分をカバーするのがどれだけ難しいか」を基準に値をつけます。
- パネルの周囲4 マスにパネルが少ないほどより高いスコアをつける
- そのパネルを埋めることができる空間の個数が少ないほど高いスコアをつける
周辺パネルが少ないと高スコア
周辺のパネルの枚数が同じでも別方向から見たときにその位置にブロックを置ける空間の数が異なれば難易度も変わるのでそれも評価に含めます。
具体的な評価値についてはケースごとに分けて optuna で調整しました。
ランダムな座標選択
スタート地点として座標をランダムに選択しますが、まだ未完了のパネル、ブロックの設置難易度が高いところほどスタート地点として選ばれやすくしています。
- 優先度高 : 両サイドともまだ未完成のパネル部分
- 優先度中 : 片方のサイドがまだ未完成のパネル
- 優先度低 : その他の部分。周辺の空白マスの多いものを選ぶ（ブロックの動きの自由度が高くなりそうなもの）
一番良いブロックの置き方を求める
座標を決めたら次に回転方向を決めます。回転の種類は全部で 24種類あって組み合わせとしては 24 * 24 = 576 通りありますが、片方は固定しても特に問題ないので片方は 0で固定して、もう片方の残りの 24通りをすべて試します。ブロックは再帰的に探索して伸ばせる部分が無くなるまでブロックを伸ばし続けます。途中で他のブロックにぶつかった場合、そのブロックを削除してもそのブロックの連結性が保たれる場合はそのブロックが無いものとして探索を続けます。
この処理をいくつかランダムに座標を選び直しながらその中で一番良かったものを採用します。
なるべく周辺パネルが少ないマスをカバーするようにブロックが生成されていると思います。
連結性の確認
「このブロックを消したときに連結性が保たれているかどうか」の確認は簡易的なものを使用しました。正確に行おうとすると「1個消す → 周辺マスを DFS して 2回以上探索が行われるかどうか」みたいな判定処理になると思うのですが、この処理がとても重いので消したいブロックとその周辺のマスを確認して消せるかどうかの判定を行いました。
周辺に同じ ID のブロックが 1個以下しかない場合
特に細かい確認は必要なく問題なく消せます
周辺に同じ ID のブロックが 2個以上ある場合
隣接ブロックが他のブロックで接続されているかどうかを確認します。具体的には隣接ブロックがある方向を足し合わせたマスに同じ ID のブロックがあるかどうかを確認します。
図の例だと消したブロックの周辺には「前方向」と「左方向」の 2箇所同じブロックが存在していますが、この場合「前方向 + 左方向」に同じ色のブロックが存在するかを確認し、存在している場合は連結性が保たれているとして削除を行います。
n個隣接ブロックが存在する場合、この条件を満たすブロック配置が n - 1 個あれば連結性は保たれているのでそれで判断を行いました。
正確性は犠牲にしているので例えば以下のような状態だと無理だと判断されてしまいます。
計算量の問題から隣接ブロックの数が 4以下のところだけをチェックしています。消したいブロックを中心とした 3 x 3 の空間でチェックを行う実装もやってみましたが処理が重くて諦めました。評価の段階では壊しながら進みますが実際に置くときは他のブロックがあるところでストップするようにしています。（後に行う山登りで実際に壊してみてスコアが改善するかどうかを確かめます）
山登りによる改善
1つのブロックの設置が完了したら、その都度山登りによる改善を行います。遷移としては「1つマスを選んで 1マス伸ばす」を行い。スコアが改善したら採用するという処理を行います。これを改善できるマスが無くなるまで繰り返します。
before - after
処理が非常に重いため最初は一番最後のみの実行を行っていましたが、ブロック設置毎に実行したところスコアが大きく改善したためこちらを採用しました。
時間制限いっぱい繰り返す
「ブロック設置」→「山登りで改善」を繰り返してシルエットの未完成部分がなくなったらそこで終了。一番良かったのもを採用して終了します。繰り返し実行の中で現状の最小スコアより高くなったら早めに終了したりと足切り処理も入れています。
感想
最初思いついた方針でそのまま走った結果になった。この手の少しの変化で局所解の脱出が難しそうなやつは毎回多スタートの貪欲を選択している気がする。最初はブロック設置 + ランダム削除だったけど最初から作り直したほうがスコアが良くなったのでそっちになった。nika さんに抜かれたあたりから「あっこれ方針違うんだな」と思ってたけど残り 3日とかの段階だったので大きな変更もなくそのまま終了した。終盤に足が止まってしまうのは毎回の反省点。今回の問題みたいに 1位のスコアが圧倒的になるタイプの問題好き。（大体トップスコアの 9割が 20位のイメージだけど今回は 20位でも 6割程度しか取れていない）
