ブロックを効率よく穴に落とす問題でした
https://www.topcoder.com/challenges/82eb883d-85e9-442f-b0eb-91631d3d2a8f
方針
まずベースとなるブロックを落とす順番の操作配列を作成します。
操作配列の作成についてはいくつかステップを踏んでいます
1手落としの効率化
最初は 1手で落とせるブロックを列挙して落とす順番を焼きなましで求めます。
ブロックを動かす操作というのは前後の操作に影響を与えてしまうため、操作の順序を変更した際に現時点での操作が有効かどうかを毎回調べる必要が発生して、このコストがとても大きいので焼き鈍すのは難しいです。
ただ、1手落としの順番に関しては [穴の位置、ブロック取得する方向] の情報に落とし込めば前後の依存関係がなくなるため、実行可能性を調べる必要がなくなり十分高速な処理が可能になります。
例えば上記の画像の状態であれば
[[穴1, 左], [穴1, 左], [穴2, 上], [穴2, 右], [穴1, 下], [穴2, 右]]
のような操作配列を作る感じです。少なくとも 1手落としに限定すればこれでほぼほぼ最適な手順が手に入ります。
ただ、 1のブロックを落とす際には横にずらすことで 2手操作のブロックが増える可能性があるので、良さそうであれば落とすのではなくずらしていました。
貪欲に操作を決定
1手操作を優先的に実行はしますが、実際には「1手操作を 2回行って 1, 2 のブロックを落とす」より「2 手操作を行って 9 のブロックを落とす」のような後者のほうがスコア効率がよくなるケースが存在します。そのため、並行で貪欲に操作を決定する処理も走らせながら良さそうなものを選択しました。
貪欲に操作を決定しますが、一番良い操作が 3手以上の場合は 2手操作になるように盤面を操作できないかどうかを探索する処理を走らせます。
例えばこの状況だと 3手で 7のブロックが落とせますが、1つ上のブロックを上にスライドさせることによって 2手で落とすことが可能となります。
この手だけを見ればどっちも「3 手で 7のブロックを落とす」という結果は同じなのですが、2 手で落とせることになったことで他のブロックの落とす効率も上がるので結果的にスコアが出るようになります。
このような盤面操作の手が存在するかどうかは「穴」と「ブロック」のラインが直交している部分を調べて、その周辺 1マスにブロックが置けるかどうかをチェックしています。
他にも「1 のブロックが邪魔して 2手操作ができないパターン」の対策で 1のブロックを除去する処理を入れています。
ブロックを取得することによる値の期待値を計算
全体の最適化のためには、そのタイミングでの最大値より数手先を含めたスコアのほうが重要なので、ざっくりと値を計算して評価に加えていました。
この画像のケースだと [7, 1] と処理するより [1, 9] と処理したほうがスコアが高くなる。 評価は後ろに存在するブロックに対して下記のコードで決定していました。
value += block_value / d d += random_value # random_value は探索前にランダムに決定される値 [1.0, 3.0] の間でランダムに設定
[ブロックの総和] / [必要な手数] よりはスコアが出たので採用しましたが、正直理由はわかってないです。
操作をイベントとして扱う
最終的に得られた操作列は「ブロックを穴に落下させる」を区切りとしてイベントの配列して扱います。なので
1 2 S R 4 6 S U 8 6 S U 6 5 M R 6 6 S U 0 2 M D
のようなフラットな操作配列ではなくて
[
[1 2 S R],
[4 6 S U],
[
8 6 S U,
6 5 M R,
6 6 S U,
0 2 M D
]
]
「ブロックを落とす」という単位でまとめられた操作配列を持つ感じになります。
イベントの操作順番の変更
最後に得られたイベントの配列を全体の操作が壊れない範囲で移動操作します。移動によって全体のスコアが上がった場合はその入れ替えを採用します。（山登り）
方法としては入れ替え対象のイベントの適用をスキップして、その後のイベントの適用が失敗するまで適用を続けて、その都度「このタイミングでこのイベントを入れた場合」のスコアを計算して一番値が大きいタイミングの位置に挿入します。
これを前からと後ろからの両方試して、スコアの更新が出来なくなったら終了です。（後ろからの場合はすべてのイベントの適用後の盤面から各イベントの逆操作を行っていく感じです）
ここまでが一連の処理になります。
イベントの結合処理
特定のイベントに関しては依存関係が強くてまともに入れ替えができないので、ある程度イベントをまとめることで順番の変更処理の対象を減らすようにしています。
例えば画像のような状態では [7, 6, 9] と順番よくブロックを入れるという操作はほぼほぼ不動なのでこれらは 3つイベントとしてではなく 1つのイベントとしてまとめています。イベントをまとめることによって 1回の入れ替え処理で発生するスコアの変動が大きくなり改善幅も大きくなって結果的にスコアが上昇しました。
イベントをまとめるかどうかについては「初手の操作の座標の y軸 or x軸 が等しいかどうか」で判定を行っていました。（等しいと同一判定）
時間制限まで処理を繰り返し行う。
あとはこの処理（手順作成 -> 手順入れ替え）を時間制限が来るまで回し続けます。実行前は様々なパラメータの値を変更して毎回違う操作列が取れるようにします。
感想
貪欲に操作手順を決めるところで差がついてしまったと思うので、盤面評価力が足りてないなと改めて痛感しました。
