びったんびったん

ユーザビリティ・プログラミングについて。

AtCoder Heuristic Contest 001 AtCoder Ad

AtCoder Heuristic Contest 001 - AtCoder

Heuristic Contest の初開催おめでとうございます。 楽しませていただきました。

seed: 1 f:id:hakomof:20210314202005p:plain

方針

  1. greedy に初期解を求め、少し山登り法をします
  2. 実行時間の前半、 1. を繰り返しそのうちの最良解を後半の初期解とします(多スタート)
  3. 後半、「キック近傍+少しの山登り」を近傍とした山登り(これは少しではない)をします

山登り法

広告の位置サイズを変更して良くなっていたら遷移する、ができるので焼きなまし法系だなあと思います。

近傍 1: 広告 1 つを最適化

要素を 1 つ 2 つ変えるというのは頻出なのでします。

広告を 1 つ選び、それ以外すべての広告の位置サイズを不変としたときの(ありうる矩形すべてのうちの)最適な位置サイズに選んだ 1 つの広告を変えます。これが平均 O(N) でできますが少し難しい。

なぜランダムな位置サイズではなく最適な位置サイズにしたかというと、最適な矩形に包含されるような良くなさげな矩形をランダムは多量に含むので、有効な近傍の割合がとても減ると思ったからです。

平均 O(N) にする
  1. ありうる矩形のうち他の矩形に包含されない矩形を列挙し(矩形列挙)、
  2. 列挙した矩形それぞれに、その矩形内での最適サイズを求めて最良をとれば(矩形内最適化)、

最適な位置サイズが求まります。

矩形列挙
  1. 最小の広告を左右にできるだけ伸ばす
  2. 上下にできるだけ伸ばす
  3. 矩形として列挙
  4. さらに上に伸ばすために左右を最小限に縮め、 2. にメモ化再帰。下に伸ばすのも同様

これは O(N3) ですが、実際には上下左右を他の広告に囲まれているため平均 O(N) になります。

矩形内最適化

int 最適な幅[広告のid][高さ] をテーブルで持ちます。 1 から矩形 H までの h それぞれに、 矩形 W < 最適な幅[id][h] なら愚直に、でなければテーブルを引けば O(H) で求まります。

このテーブルを disjoint sparse table 化すると区間 min or max を O(1) で求められるので、最適な幅が矩形 W 以下であるような高さから矩形 H までの区間最良をとれば O(1) で求まります。


あわせて 平均 O(N) にできました。

近傍 2: 広告 2 つを最適化

要素を 1 つ 2 つ変えるというのは頻出なのでします。

近くにある広告 2 つを選び最小にし、近傍 1 を順番に適用します。

遠くにある広告はお互い干渉しないのでそれぞれ独立に近傍 1 を適用するのと変わらず、いたずらに遅くするだけなので完全に無駄です。それぞれの広告でマンハッタン距離が近い順に 5 コを近い広告としました。この 5 という数は明らかに近傍 2 を適用したいであろう広告のペア群として少ない(漏れうる)ですが調整の結果ですね。その外側の山登りのイテレーション数とのバランスです。

また、近傍 1 を順番に適用するというのはこの 2 広告間に限定しても最適ではありません(例えば 2 広告間の分断線を 3 分探索すれば最適になりそう)。これは速度とのバランスと後述する膨張近傍でカバーできるからで、近くにある広告だけなのも同じです。しかし、近傍 1 では最適な位置サイズを求めていて、こんな風にこの部分はは遅くても正確に、あの部分は高速だが不正確に、というバランス配分が求められるのはヒューリスティックコンテストのおもしろいところだと思っています。

膨張近傍

ここで問題のスコアリングを思い出してみると、満足度 1.0 と 0.8 の 2 広告より、 0.9 と 0.9 の 2 広告のほうがスコアが良いです。そして、近傍 2 は片方をめいいっぱい良く配置してもう片方をあまったスペースにできるだけ良く配置するという主旨なので問題のスコアリングと相性が悪いです。なので、広告の満足度を均等に上げるために、

スコアが良くなる限り上下左右辺を 1px ずつ大きくすることにしました(他の広告と接しているならそれらを縮めてなおスコアが良くなる限り)。

メイン近傍

近傍 2 の後、そこで選んだ 2 広告に膨張近傍を適用する、これがメイン近傍です。最初のほうに書いた山登りではキック近傍以外は前半後半ともこのメイン近傍です。

キック近傍

こういう広告同士がガチガチにかみあって動かしづらそうな問題では、メイン近傍のような小さい近傍だけだと局所解を脱出できないので、

マンハッタン距離で近くにある 9 つの広告を最小化してから、メイン近傍で山登りをして脱出を狙います。

多スタートと greedy

同様にこういう動かしづらそうな問題は探索空間の多峰感が強いので、良い峰を引くという意味で多スタートや greedy を初期解とすることが有効になりえます(良い峰内の良いとところに行くのが山登りの役割)。

高速化

広告の矩形 x0, y0, x1, y1 それぞれのソート済みの配列と広告との相互参照するデータ構造をつくります。矩形が変化したらソートや相互参照を追従させる。

これを使うとボトルネックである矩形列挙や膨張近傍のループの開始や終了を枝刈りできて速くなります。

MM わくわく新プラットフォームまとめ

経緯

  1. 新プラットフォームへの移行が間に合わず MM110 が 1 週間延期(なぜ旧プラットフォームで予定通り開催しないのか
  2. 1 週間後、新プラットフォームで始まるも機能がまったく足りてない(なぜ始めた
  3. 機能の追加が追いつかないので更に延長。 rated に変わりないことを固持
  4. 数日後 unrated
  5. 1 ヵ月後、テストマッチが始まるも機能がまったく足りてない(おかわりおいしいです
  6. 機能がまったく足りないまま TCOMMR1 が明日にせまる
  7. TCOMMR1 の延期や中止のアナウンスはまだない←イマココ

現存する不具合

現存する不具合のだいたいは レナード尾根( EnoDraNoel ) (@usakdsteen) | Twitter さんが見つけたものです。私も後から検証しました。少し前はもっどひどかったぞ。

  • submit した後に撤退できる
  • example test と provisional test が無理やり統合された結果 provisional test の seed が 1 から 10 。 provisional test の seed は特定不可能じゃないとダメ。あと example で実験すると provisional も動いちゃうの不便
  • 相対スコア計算が間違ってる
  • 提出制限がされてない、本番だと簡単に詰まる
  • MLE のチェックがされてない
  • example test で実行時間と消費メモリがわからない
  • サブミットして順位表への反映を確認、数日後アクセスすると古い順位表が表示される、スパリロしても同じ、さらに待ってアクセスすると新しい順位表が表示されたりする
  • エラー出力の最後の方が漏れる
  • C#/VB の solution.sh の example が未記載(それはまだ C#/VB に未対応なのと同じですよ?
  • example.cpp のここで切り取ってってやつが不要になったのに残ってる
  • 正のスコアメールを得ても順位表上だと失敗扱いになることがある

要確認

  • reviews.json っていう怪しい情報にアクセス可能。明確に見えちゃダメな情報かはわからないけど、コンテストが始まってから見えちゃダメなことがわかっても遅いので
  • マルチスレッド制限はどうなっているのか?
  • スコア操作の脆弱性は結局埋められたのか?
  • 実行可能ファイル等を直接含めてよいという運営の回答があったが、今まで外部ライブラリ禁止だったわけだが。たぶんそれを把握せずの回答
  • コンパイルオプションが自由になっておそらく、 cpp でより多くの SSE 命令が使えるようになる。だから cpp の有利が増すけどそれもたぶん把握せずにコンパイルオプションを自由にしてる

不便

  • スコアメール届いてから順位表に反映されるまでに数分かかる
  • 順意表を最終サブミット時刻順にできない
  • solution.sh の改行が linux のやつしか許容されない
  • フォルダではなくファイルを圧縮しないといけない

Topcoder Marathon StainedGlass

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17394&pm=15264

Example Tests

It's good that I ran several times only seed 2

1, 188798.4375, 120831.0, 5/20
2, 2.0110236926112E7, 1.8450842E7, 44/1000
3, 2.585656663217272E7, 2.4089131E7, 20/555
4, 7493222.916638096, 6457431.0, 40/518
5, 4.1234232157296196E7, 3.9425575E7, 22/970
6, 8907273.54193523, 8194529.0, 31/728
7, 9728903.343749998, 8059686.0, 15/152
8, 2.7994073349021245E7, 2.5841511E7, 12/294
9, 6883570.201690821, 5904721.0, 44/552
10, 2.3159190600224324E7, 2.1495614E7, 18/474

1, 188798.4375, 120831.0, 5/20 f:id:hakomof:20190115103509p:plain

2, 2.0110236926112E7, 1.8450842E7, 44/1000 f:id:hakomof:20190115103600p:plain

3, 2.585656663217272E7, 2.4089131E7, 20/555 f:id:hakomof:20190115103646p:plain

4, 7493222.916638096, 6457431.0, 40/518 f:id:hakomof:20190115103715p:plain

5, 4.1234232157296196E7, 3.9425575E7, 22/970 f:id:hakomof:20190115103808p:plain

6, 8907273.54193523, 8194529.0, 31/728 f:id:hakomof:20190115103831p:plain

7, 9728903.343749998, 8059686.0, 15/152 f:id:hakomof:20190115103857p:plain

8, 2.7994073349021245E7, 2.5841511E7, 12/294 f:id:hakomof:20190115103946p:plain

9, 6883570.201690821, 5904721.0, 44/552 f:id:hakomof:20190115104009p:plain

10, 2.3159190600224324E7, 2.1495614E7, 18/474 f:id:hakomof:20190115103500p:plain

方針

序中終盤ともに 1 母点を周囲 8 マスに動かす焼きなまし(輪郭追跡 + BFS で差分計算)

試行回数は 125 万くらい

  • 初期状態はランダム
  • 序盤 4 秒
    • 画像を辺の長さが 1/8 になるよう縮小
    • N 色
    • 定期的に減色を空撃ちして、隣接領域との色差が小さい母点らや、同色で至近にある母点の片方らすべてを一度に、色差が大きそうなとこに飛ばす
  • 中盤 12 秒
    • 画像は原寸大
    • N 色
  • 中盤と終盤の間
    • 色数を黄金分割探索、 kmeans++ で減色
  • 終盤 4 秒
    • 画像は原寸大
    • N の 2%-10% 色

考察の流れ

だいたい時系列

焼けそうなので焼く。

状態は

  • 母点の座標
  • 母点のグループ
  • グループの色

からなる。 このうち母点の座標・母点のグループが決まれば最適なグループの色は求まる。 差の絶対値和の最小なので中央値。 なので、母点の座標と母点のグループを焼きなましてグループの色は差分更新で最適値に追従させる。 関連記事

具体的には、色素値ごとの面積の BIT と色素値和の BIT を持つと追加・削除・最適色でのスコアなどが O(log(256)) になり差分更新できる。

近傍

母点の自由な移動はうまく差分計算できても O(領域面積 * log(256)) で遅い。 もっと速くしたい。 近傍を小さくしよう。 母点を周囲 8 マスに動かせば領域の境界しか変わらない。

動かす母点の輪郭を 輪郭追跡 で求めて queue に入れる。 px の所属する母点が変わったか調べて、変わっていたら周囲 8 マスを queue に入れる。 queue が空になるまで BFS する。 これでほぼ厳密に差分計算ができた1

近傍が小さすぎない?

この問題のように要素同士に区別がない(母点を入れ替えてもスコアが変わらない)とき近傍は大きくなくてよい。 なぜなら、遠くに動かす近傍は、母点を玉突きのように少しずつ押し出しても代替できるので。

HACK TO THE FUTURE 2018予選 山型足し算 も同様の理由で近傍が小さい。

近傍が小さすぎない? 2

近傍は大きくなくてよいけど、小さいほどよいわけではない。 画像最大 800px に対して 1px の移動は小さすぎる気がする。 でも近傍を大きくすると遅くなってしまう。 じゃあ画像を縮小しよう。 800px に対する 1px の移動よりも 400px に対する 1px の移動は相対的に大きい。 画像を縮小すると速くなるので一石二鳥。

さらに、画像を縮小して焼いてから原寸大で焼くと試行回数と精度のバランスが取れるが、大きい近傍で焼いてから小さい近傍で焼くことにもなる。 近傍をだんだん小さくするのは良い工夫なので二石四鳥。

減色

疲れたので以降雑

母点のクラスタリングは基本的にうまく焼きなませない。 例えば、空のグラデーションが 5 色のとき 4 色のグラデだとか 6 色のグラデへの移行は全体的にずれるので焼きなましの小さな近傍では対応できない。 なので、母点の座標の焼きなましと母点のクラスタリングは分けて最適化することにする。 やり方は序盤に減色だとか、終盤に減色だとか、徐々に減色していくとか色々考えられ一概に判断できなかったので全部試した。 結果、序中盤は N 色で、1 回だけ減色するが良かった。 結果から考察すると、一度減色してしまうと同じ色同士の母点が結びついて動きづらくなるのでギリギリまで減色しないのが良いようだ。

クラスタリングは kmeans++ 。 といっても厳密スコアによる山登りに等しい。 代表色のクラスタリングではなく領域の全色集合同士のクラスタリングクラスタ数は黄金分割探索で、凸じゃないけどだいたい凸ってことで気にしない。 黄金分割探索で求まったクラスタ数±1に kmeans++ を数百回多スタート。 これ大事。 さっき書いた通り近傍探索(焼きなましとか kmeans++)がうまくいかないので多スタートで誤魔化している。 というか多スタートする必要があったから母点の座標の焼きなましと母点のクラスタリングを分けた。

母点のワープ

f:id:hakomof:20190115170813p:plain

黒背景には最小限の母点しかない。 元々黒背景にもたくさんの母点があったのだが、隣接領域がすべて同色の母点は除いてもスコアが変わらず、有意義なとこに差し込めばスコアが良くなることに気づいた。

これを拡張すると、隣接領域との色差が少ない母点は除けそうである。

同様に無駄な母点が無いか考えてみたところ、同色の母点がすぐ近くにあるとき 1 つを残して除けそうなことにも気づいた。

序盤の間等間隔に 9 回減色を空撃ちして、同色で至近にある母点の片方らと隣接領域との色差が小さいほうから 2.5% の母点らすべてを一度に、領域境界に周囲 9 マスの色差の和の二乗を重みとしてランダムワープ。

なんで焼きなましのサブ近傍にしなかったの?遅いのと、ワープ先になじんでからじゃないと良い悪いの判断ができない気がしたから。

なぜ序盤だけ?ワープ後になじませるのに大きい近傍が必要だから。


  1. 領域の角度がとてもきついときに離散化で領域が連結でなくなることがある。このとき輪郭追跡が漏れる。が、実験したところ数ケースに 1px 程度しか誤らないので許容範囲。

ビームサーチは DP

この記事は Competitive Programming (1) Advent Calendar 2018 - Adventar の 6 日目です。
5 日目の記事は armeria_betrue さんの 解説記事のはなし - ARMERIA です。
7 日目の記事は xuzijian629 さんの Implicit Treap - 競プロ練習記録 です。

ビームサーチとは

ビームサーチとはグラフのヒューリスティック探索アルゴリズムです。 初期ノード群から BFS 順に探索していき、深さ(初期ノードからの遷移回数)ごとに良さそう順のノードの上位 N コ以外を枝刈りすることで時間 / 空間計算量を改善します。

58-72p でくわしく説明されているので引用します。

本記事の趣旨

ビームサーチといったら上述のような説明が定番?です。 その説明は正しいのですが、私はビームサーチを上述を含んだより広汎なアルゴリズムだと思っています。なので、私の現在の解釈である「ビームサーチは DP の拡張」という観点で説明してみます。 色々な視点から同じものの説明がなされるのも一般に良いことですし。

ビームサーチは DP

DP の説明は省略します。

f:id:hakomof:20181205200921p:plain

例えば、木を探索するとして、どんな経路を通ったかによらず以降の最適な経路が同じ状態を同一とみなすと、木は DAG になり合流部以降の重複探索をなくすと DP になります。 つまり、どういう状態群を同一とみなすかは DP の一端です。

同様に今度は深さが同じ状態群を同一とみなして DP で解いてみましょう。

f:id:hakomof:20181205200949p:plain

単純な形ですが DAG は DAG です。 この DAG を DP するコードを起こすとこんなかんじでしょうか。

State dp[Depth];
dp[0] = initialState;
for (int d = 0; d < Depth - 1; ++d) {
    for (State nextState : dp[d].getAllNextStates()) {
        dp[d + 1] = max(dp[d + 1], nextState);
    }
}

お気づきいただけただろうか… この配る DP の振る舞いは幅 1 のビームサーチと完全に一致します(なにやら冗長なただの greedy でもよいです)。 なぜ一致するのかというとビームサーチが DP そのものだからというほかないです。 結局、ビームサーチは深さごとに状態をまとめる、 DAG になる、 DAG のトポロジカル順序である深さの昇順にビームを更新していく、と DP をしているに過ぎなかったのです。

ビームサーチの DP との違い

  • 状態のまとめ方が過剰
  • 評価関数
  • ビーム幅

状態のまとめ方が過剰

効率的な探索をしてなお最適解が現実的な時間で求まらないとき、非最適解でよいから現実的な時間で求めたいという動機があります。 そこで、現実的な実行時間になるまで状態を過剰にまとめるというのが思想の出発点だと思っています。

評価関数

本来異なる状態を同一とみなす以上、最適解に通じる状態が残るとは限りません。 ですが、状態のつぶれた情報をフルに駆使した評価関数で精度の底上げができます。

ビーム幅

例えば、実行時間が 10 秒くらいになるような状態数が 500 万くらいに状態をまとめるといった器用なことはできません。 そのため、実行時間と性能に融通が利きません。 ですが、ビーム幅を導入すると実行時間は約ビーム幅倍になり相応に性能が上がる(ことがある)ので、少し融通が利くようになります。


以上よりビームサーチは状態の過剰なまとめを許容する形に拡張された配る DP だと思っています。

で、何ができるの?

  • ビームは深さ以外でも切れます
  • あるビーム内状態の次状態は直後のビームでなくてよいです
  • 1 次元でなくてよいです
  • ビームサーチ以外の嘘 DP との併用や換装ができます
  • DP の知見が流用できます

例えば以下のような 2 次元の DP をビームサーチ化するとしたら、ビームはタテにもナナメにも切れます(切った後も DAG になっています)。 逆にヨコにはループができるので切れません。1

f:id:hakomof:20181205212430p:plain

f:id:hakomof:20181205212441p:plain

f:id:hakomof:20181205212503p:plain

ビームをどう切るかで性能が大きく変わるのは想像にたやすいでしょう。 肝心のビームをどう切ればよいかですが、 パラメータが違う状態同士の優劣判断が一番難しいパラメータで切るのが良さそうに思います。 なぜなら、各ビームにはそのパラメータが同じ状態しか含まれないので、そのパラメータを評価関数に含めなくてよくなるからです。 例えば、ゲーム AI などで 5 ターン目と 100 ターン目の比較は難しいからビームをターンで切るといったかんじです。

おわりに

近年マラソンをする人が増えうれしい限りで、焼きなまし / ビームサーチを覚えたい / 覚えたといったツイートをよく見かけるようになりました。 しかし、インターネット上の情報は少なく例も単純です。 そこで、実際のビームサーチ(や焼きなまし)が単純な例よりもはるかに柔軟でそれ自体に工夫の余地が多いことを少しでも感じてもらえたらなと思い本記事を書きました。 もちろん、それ以前のどんな方針を立てるかがマラソンで一番おもしろいとは思います。 ですが、ビームを撃つとか焼くとか決めた上でそれ自体を改造するのも十分おもしろいので楽しんで欲しいなと思います。


  1. 切れないことはない

Topcoder Marathon KnightsAndPawns

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&pm=14994

焼きなましに飽きた1点をのぞけば、おもしろい問題だったと思います。

f:id:hakomof:20180731200014j:plain

方針

  1. 空のボードにナイトをごく少数ランダムに配置して初期状態とする。
  2. ナイト数を固定してペナルティ最小化の焼きなまし(SA)をする。近傍はナイト1つの移動だけで追加や削除はしない。
  3. ペナが0つまりvalidな状態に到達したら、ベストを更新して、その状態にナイトを1つランダムに追加して2に戻る。

例えば、
ナイト数100のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数101のvalidな状態をSAで求める。その状態にナイトを1つ追加して、
ナイト数102のvalidな状態をSAで求める…
これを時間いっぱい繰り返します。

この方針の優位性

方針に悩んだので、とりあえずナイト数とvalidが存在するかどうかの関係性を洗いました。雑なSAで調べました。それによると、あるX以下のナイト数はすべてvalidをつくれて、Xより大きいナイト数はすべてvalidをつくれないという綺麗な感じに分かれました。また、Xのvalidな最適解はわりと高速に求まったので、これは最適解を拾えるケースはきっちり拾えないと死にそうという印象になりました。(最終方針だとケースの半分強で最適解と思われるものが安定して出る)

これらを元に前述の方針を立てました。

メリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、時間に余裕があれば安定して最適解が出る
  • SAのスコアが単なるペナなのでペナ方向のランダムウォークは理想的に行われる

デメリット

  • ナイト数を1つずつ増やしながらvalid解を求めていくので、収束が遅い。ですが、valid解にナイトを1つ追加した解つまりペナがとても少ない解からSAをはじめることでこのデメリットはかなり軽減される。
  • ナイト数を固定しているので、ナイト数方向のランダムウォークは皆無

他にもいくつか考えましたが、この方針が強そうだったので採用しました。

方針の続き

前述の方針そのままにさらに工夫を足します。

近傍を絞る

近傍はナイトを1つ動かす。ですが、ランダムなナイトをランダムな空きマスに動かすのではなく、

  • invalidなナイトをランダムな空きマスに動かす。
  • 攻撃されすぎなナイトを攻撃しているナイトを、ランダムな空きマスに動かす。
  • 攻撃されなさすぎなナイトを攻撃できる空きマスに、ランダムなナイトを動かす。

の3種類に絞ります。いずれもあるナイトのinvalidを解消する近傍です(たいていは別のマスにinvalidが移るだけですが)。SAはこのようなたとえスコアが下がっても部分的に改善する近傍だけが必要かつ十分なようで、それ以外の近傍を削ることが重要かつ頻出です。状態内のinvalidなナイトはとても少ないのでものすごい削られます。

毎試行必ず遷移するSA

普通のSAは近傍をランダムに選んで受理されたら遷移するので、試行回数×受理確率=遷移回数がパフォーマンスの目安になります。もし受理確率を100%にできたらもともとの受理確率が1%だとしたら100倍の高速化になります。今回の問題はこれができます(別途処理を追加するので10倍くらいの高速化(うろ覚え

このテク、過去のKnightsAttacksというコンテストで使ったのでそのときのツイートを流用します。(別にKnightがらみでなくてもこのテクは使ええます)

今回は黒赤青すべてのマスが変化するので41種類

今回は-16から+16の31通り

過去のコンテストのツイートバリバリ流用できるのほんと草生える

多スタート

局所にはまることはあるのでボードが小さいときは2回スタート

Example scores

Example scores:
0) 15.0
1) 1293.0
2) 3391.0
3) 1444.0
4) 1869.0
5) 173.0
6) 1415.0
7) 261.0
8) 230.0
9) 1499.0

f:id:hakomof:20180731195934j:plain f:id:hakomof:20180731200014j:plain f:id:hakomof:20180731200135j:plain f:id:hakomof:20180731200110j:plain f:id:hakomof:20180731200120j:plain f:id:hakomof:20180731200347j:plain f:id:hakomof:20180731200427j:plain f:id:hakomof:20180731200443j:plain

Topcoder Marathon Match 100 SameColorPairs

問題文

方針

私は焼きなまし厨なのでとりあえず焼きなましを考えます。

この問題の要求する解は消すペアとその順番です。その解そのものを(順番を含めて)直接焼きなますというのは難しそうです。なぜならあるペアを消すと新たにペアが消せるようになる、といった順序関係が強そうなので、順番を安易に変えると状態が壊れそうだからです。

そこで消すペアと順番を分けて考えてみます。消すペアの集合(消せる消せないにかかわらずすべてのマスをペアにしたもの)を固定したときの順番はどうなるでしょうか。これは以下のような簡単な貪欲で最適な順番、最適なスコアが求まります。

  1. 消せるペアを消す
  2. 新たに消せるペアが増えるのでそれも消す
  3. 1つも消せなくなるまで消す

なので、

  • 消すペアの集合を焼きなましの状態とする
  • 状態を少し変えたら、先の貪欲でスコア(差)を求めて遷移判定をする

とすれば焼きなましに帰着できました!

近傍

同じ色のペアを2つ選んでつなぎかえます。マスAとBを消すペアとマスCとDを消すペアを、ACを消すペアとBDを消すペアに変えるといった感じです。

状態に制限がなく、近傍も小さいのでうまく焼きなませそうです。

ですが、先の貪欲はめちゃくちゃ遅いのでまともにまわりません。なので収束速度の底上げ・高速化をしていきます。

盤面を分割して順に焼きなまします。探索空間が小さくなり収束が速くなることが期待されます。消すペアは近いことが多いので局所的な焼きなましはあまりデメリットになりませんでした。

盤面は1-27分割しますが最後の2ブロックだけ多スタートします。

近傍は、消せないペアか他のペアをたくさん囲っているペアの中から選びます。他のペアをたくさん囲っているペアというのは、囲われているペアが先に消えることを縛っていて、それがたくさんということは大局的に良い状態ではない可能性があります。なので変更の候補です。

近傍のつなぎかえ先は(広義)近いマスほど高確率で選ばれるようにします。

先の貪欲は次のような言い換えができます。消すペアを頂点として、ぺアXを消してからでないとペアYを消せないときXからYに有向辺を張った依存グラフを、閉路の手前までトポロジカルソートすると先の貪欲と同じ結果が得られます。消せるペアを探す手間が省ける分こっちのほうがたぶん速いです。

評価値は、消せるペア数 - 依存グラフの最小閉路の数 / 2.5です。閉路以下のペアはすべて死ぬので閉路の数をペナルティとすると探索空間がなだらかになってよさげです。

依存グラフは差分更新します。更新が必要な辺は、変更する2つのペアに入出する辺だけなので、グラフ全体を毎回つくりなおさなくていいです。

依存グラフを差分更新するにあたり、新しいペアを囲うペアを列挙する必要がありますが、愚直にすべてのペアを走査すると遅いので、バイナリ空間分割という衝突している物体の列挙を高速にするアルゴリズムを使います。囲われていることと衝突していることは同じことなので転用できます。