Skip to content

AHC042 - Oni wa Soto, Fuku wa Uchi(焼きなまし解) ​

問題文(AtCoder)

使用した主な手法:焼きなまし法 / 操作列の最適化 / シミュレーション

問題概要 ​

N=20 の盤面に鬼(x)と福(o)がそれぞれ 2N 個ずつ配置されている。

各行・列を上下左右に1マスずつ移動し、福を盤外に落とさずに、すべての鬼を取り除くことが目的。

すべての鬼を取り除いた場合、操作回数 T に対して得点は次のようになる。

score=8N2−T

したがって、できるだけ短い操作列を求めたい。

問題では、すべての鬼について上下左右の少なくとも1方向に福が存在しないことが保証されている。これを利用すれば、必ず完成する操作列を構築できる。

解法の概要 ​

この解法では、操作列そのものを焼きなまし法で最適化する。

ただし、上下左右に1マス移動する操作をそのまま扱うと、探索する操作列が長くなってしまう。

そこで、同じ方向への連続移動を1つにまとめた操作を定義する。

全体の流れは次のとおり。

  1. 問題の保証を利用して、必ず完成する退避解を作る。
  2. 複数回の移動をまとめた操作列を焼きなましの状態とする。
  3. 操作列を最初からシミュレーションし、除去した鬼の数・手数・福の損失を評価する。
  4. 操作列の挿入・削除・交換・変更などで近傍を生成する。
  5. 最良の合法解を保存し、最後に1マス単位の操作列へ展開する。
項目この実装での設定
探索手法焼きなまし法
探索対象圧縮した操作列
初期状態空の操作列
退避解鬼を押し出して戻す貪欲解
評価関数鬼の除去数・手数・ペナルティ
近傍挿入・削除・swap・変更・方向反転
制限時間1.85秒
温度約1.26 → 0.40

解法のエッセンス ​

複数手の操作を1つにまとめる ​

通常の操作は、行または列を1マス動かすだけである。

しかし、ある方向に福が存在しない場合、複数回動かして鬼をまとめて落とせる。

この性質を利用して、探索で扱う操作を次のように定義する。

cpp
struct Action {
    int dir, p, lim;
    Action(int d = 0, int index = 0, int limit = -1)
        : dir(d), p(index), lim(limit) {}
};
  • dir:移動方向
  • p:操作対象の行または列
  • lim:移動方法を指定する値

lim には2種類ある。

lim動作
11マスだけ移動する
-1最初の福より手前にある鬼をまとめて落とす

例えば、次の行を左に移動するとする。

text
左端                   右端
. x x . o . .

lim=1 なら、左に1マス移動するだけ。

text
x x . o . . .

一方、lim=-1 なら、福の手前にある最後の鬼を落とすまで、左へ3マス移動する。

text
L → x x . o . . .
L → x . o . . . .
L → . o . . . . .

この例では、3回の移動を1つの Action で表現できる。

操作列を圧縮することで、焼きなましが探索する変数の数を減らせることが大きな利点。

方向を統一して盤面を操作する ​

上下左右の操作を個別に実装すると、同じような処理を4回書く必要がある。

そこで、cell() 関数を使い、常に押し出す側の端から何マス目かという形式で盤面にアクセスする。

cpp
inline char& cell(Board& b, const Action& a, int i, int n) {
    if (a.dir == 0) return b[i][a.p];
    if (a.dir == 1) return b[a.p][i];
    if (a.dir == 2) return b[n - 1 - i][a.p];
    return b[a.p][n - 1 - i];
}

例えば、上方向なら上端が i=0、下方向なら下端が i=0 になる。

これにより、どの方向でも同じシミュレーション処理を使用できる。

操作列をシミュレーションして評価する ​

焼きなましの状態は、操作列そのものとする。

cpp
struct State {
    vc<Action> actions;
    vi shifts;
    int turn = 0, done = 0, penalty = 0;
    double score = 0;
};

evaluate() では、初期盤面から操作列をすべて再生する。

各操作について、押し出す側の端から調べ、移動回数 cnt を決定する。

cpp
int cnt = 1;
int lim = (a.lim == -1 ? input.n : 1);

rep(i, lim) {
    char c = cell(b, a, i, input.n);
    if (c == 'o') {
        if (i == 0) penalty++;
        break;
    }
    if (c == 'x') {
        cnt = i + 1;
        done++;
    }
}

ここでは、福に到達するまでの範囲で、最後の鬼を落とせる移動回数を cnt とする。

盤面の更新は次のように行う。

cpp
turn += cnt;
shifts.push_back(cnt);

rep(i, input.n - cnt)
    cell(b, a, i, input.n) = cell(b, a, i + cnt, input.n);

srep(i, input.n - cnt, input.n)
    cell(b, a, i, input.n) = '.';

このシミュレーションによって、以下を求める。

  • done:盤外に落とした鬼の個数
  • turn:実際に必要な操作回数
  • penalty:福を落とした回数などに対するペナルティ
  • shifts:各圧縮操作が何手になったか

なお、この実装では turn > 100 の状態で次の操作を評価しようとすると、追加ペナルティ1000を与えてシミュレーションを打ち切る。

cpp
if (turn > 100) {
    penalty += 1000;
    break;
}

問題の制限は1600手だが、探索中はそれより大幅に短い操作列へ誘導している。

評価関数の重みを時間とともに変える ​

評価関数は次のとおり。

E=wd⋅done−turn−wp⋅penalty
  • wd:鬼を取り除くことへの報酬
  • wp:福を落とすことなどへのペナルティ

評価値は大きいほどよい。

最初から福の損失を強く禁止すると、操作列の変化が制限され、鬼を落とす手順を発見しにくくなる可能性がある。

そこで、探索の進行に応じて重みを変える。

経過時間の割合を t∈[0,1] とすると、

wd=5+7twp=101.2+2.3t

となる。

パラメータ探索序盤探索終盤
鬼の除去報酬 wd512
ペナルティ wp約15.8約3162

序盤は不完全な操作列もある程度許容しながら探索し、終盤は福を落とさない解を強く優先する。

cpp
done_weight = 5 + 7 * t;
penalty_weight = pow(10.0, 1.2 + 2.3 * t);

このように、探索の進行に応じて評価関数自体を変えるのが特徴的な工夫である。

操作列に対して近傍を生成する ​

焼きなましでは、操作列に対して5種類の変更を行う。

近傍内容選択確率(操作数が21以上)
挿入ランダムな操作を追加13%
削除操作を1つ削除12%
swap近い位置の2操作を交換55%
変更操作をランダムに変更10%
方向反転上下・左右を反転10%

特にswapを多く採用している。

cpp
int i = randint((int)a.size()), j;
do {
    j = randint((int)a.size());
} while (i == j || abs(i - j) >= 10);
swap(a[i], a[j]);

交換する2操作の距離を10未満に制限することで、操作列全体を大きく壊さず、局所的な順序の調整を狙っている。

また、操作数が20以下の場合は挿入のみを実行する。

cpp
int mode = randint(100);
if ((int)a.size() <= 20) mode = 0;

初期状態は空の操作列なので、まず操作を増やし、一定の長さになってからさまざまな近傍を試す設計になっている。

焼きなましで操作列を最適化する ​

通常の焼きなましと同様、評価値が改善する場合は採用し、悪化する場合も確率的に採用する。

P=min(1,exp⁡(Enext−EcurT))

温度は、経過時間の割合 t に対して次のように変化する。

T=100.1−0.5t

実装では次のように受理判定する。

cpp
double delta = next.score - cur.score;

if (delta >= 0 || rand01() < exp(delta / temp))
    cur = move(next);

評価値の重みと温度は256反復ごとに更新する。

温度を徐々に下げることで、序盤は悪化する変更も受け入れやすくし、終盤は改善を重視する。

最良の合法解を別に保持する ​

焼きなまし中の状態は、必ずしも合法な完成解ではない。

鬼が残っていたり、福を落としていたりする場合もある。

そこで、探索状態 cur とは別に、最良の完成解 best を保持する。

cpp
if (next.done == 2 * input.n &&
    next.penalty == 0 &&
    next.turn < (int)best.size()) {

    best.clear();
    rep(i, next.shifts.size()) rep(k, next.shifts[i]) {
        auto a = next.actions[i];
        best.emplace_back(a.dir, a.p, 1);
    }
}

完成解と判断する条件は以下の3つ。

  • すべての鬼を落としている
  • ペナルティが0
  • 現在の最良解より操作回数が少ない

また、この更新は焼きなましの採用判定よりも前に行っている。

つまり、探索状態として採用されなかった候補でも、最良の完成解なら保存する。

なお、actions は圧縮操作列なので、出力時には shifts を利用して1マス単位の操作へ展開する。

必ず完成する退避解を用意する ​

焼きなましでは、制限時間内に完成解を発見できるとは限らない。

そこで、fallback() で必ず完成する退避解を作る。

方法は次のとおり。

  1. 鬼を1つ選ぶ。
  2. その鬼を盤外へ出せる、福のいない方向を探す。
  3. 必要な回数だけ押し出す。
  4. 逆方向に同じ回数だけ戻す。

往復することで、除去した鬼以外の駒を元の位置に戻せる。

cpp
rep(t, steps) {
    if (cell(b, best, t, input.n) == 'x') rest--;
    cell(b, best, t, input.n) = '.';
    res.push_back(best);
}
if (rest == 0) return res;

Action back((best.dir + 2) % 4, best.p);
rep(t, steps) res.push_back(back);

この実装では、往復後の盤面を直接作る代わりに、除去した範囲を空マスにすることで状態を管理している。

最後の鬼を取り除けた場合は、逆方向へ戻さずに終了する。

重要なのは、この退避解を焼きなましの初期状態には使用していないこと。

焼きなまし自体は空の操作列から開始し、退避解は出力する最良解の初期値としてのみ使用する。

これにより、探索がうまくいかなくても、常に合法な解を出力できる。

まとめ ​

この解法の特徴は、操作列をそのまま最適化するのではなく、複数の移動をまとめた表現に変換して焼きなますことにある。

特に重要な工夫は以下のとおり。

  • 連続移動を1つの操作にまとめ、探索する操作数を削減する。
  • 操作列全体をシミュレーションして評価する。
  • 探索序盤と終盤で、鬼の除去報酬とペナルティの重みを変える。
  • 近距離swapを中心に操作列の順序を改善する。
  • 探索状態とは別に最良の完成解を保持する。

ビームサーチ解が盤面の状態を探索するのに対し、こちらは操作列そのものを探索する解法である。

同じ問題でも、探索対象の設計によって異なるアプローチが成立する例になっている。