AHC030 参加記 - eijirouの競プロ参加記

THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）お疲れ様でした。

システムテストの得点が 2,050,795,126,975 で 3 位でした。

問題概要

クエリを通して、石油がある場所を特定する問題です。

油田の個数と形は入力で与えられますが、各油田がどこにあるかは与えられません。

詳しくは公式の問題文を参考にしてください。

atcoder.jp

方針

毎ターン次のことを行いました。

焼きなまし法を用いて、油田配置の中で対数尤度が大きいものを 32 個ほど得る。
得られた油田配置の中に実際の配置が含まれていると仮定し、各油田配置の事後確率を求める。
得られた事後分布を利用して占うマスを選ぶ。

他の上位者と大まかな流れは一緒だと思います。焼きなまし法の部分が私は得意だったようなので、この記事では焼きなまし法で油田配置を推定する部分を中心に説明します。

ベイズ推定

占う場所を選ぶときに油田配置の事後分布が欲しくなるので、油田配置の事後分布を求めることを目標とします。

占いの履歴を $Q$ とし、各油田配置を $x$ と表記します。

$Q$ が得られたときに実際の油田配置が $x$ である事後確率 $P(x | Q)$ を求めたいです。入力生成方法を読むと事前確率 $P(x)$ が全て等しいことがわかります。ベイズの定理を踏まえると次の式が成り立ちます。

$P(x | Q) = \frac{P(Q | x)}{\sum_{x}{P(Q | x)}}$

$P(x | Q)$ を求める代わりに $P(Q | x)$ を求めればよいことがわかりました。

$P(Q | x) = \prod_{q \in Q}{P(q | x)}$ です。

$P(q | x)$ は正規分布の一部を積分した値であり、正規分布の累積分布関数が $\frac{1}{2} \left( 1 + \mathrm{erf} \frac{x - \mu}{\sqrt{2 \sigma^{2}}} \right)$ であることから計算できます。

油田の個数 $M$ がある程度大きいとき、全ての油田配置 $x$ について $P(Q | x)$ を計算する時間がありません。そこで、 $P(Q | x)$ が比較的大きいものをいくつか集めた集合を $X'$ とし、 $X'$ に実際の油田配置が含まれていると仮定して

$P(x | Q) = \frac{P(Q | x)}{\sum_{x \in X'}{P(Q | x)}}$

で分布を近似することにしました。

$|X'|$ と過去の占いの情報量が十分大きければ、高い精度で近似できると思います。

焼きなまし法

$X'$ を求める手法はいくつか考えられ、大きく 2 つに分類できると思います。1 種類目は枝刈り全探索、MCTS、ビームサーチなどの全探索を改善したもので、2 種類目は山登り法や焼きなまし法などの局所探索です。

結論として、今回は焼きなまし法を使用しました。 $M$ が大きいときに探索空間が広すぎて全探索系の手法が弱そうで、また、局所性がある近傍を設定して焼きなますことができそうだったからです。

焼きなまし法の評価値として、対数尤度 $\log_{2}{P(Q | x)}$ を使用しました。

評価値が高い状態を 32 個ほど優先度付きキューで管理し、最後に保持していたものを $X'$ としました。同じ状態やクエリで推測して間違えた配置は省くようにします。

近傍は 3 種類です。

近傍 1: 1 マス移動（選択率: 9 / 16）

ランダムに 1 つの油田を選び、前後左右のランダムな方向に 1 マスずらします。

近傍 2: ランダムな場所に移動（選択率: 3 / 16）

ランダムに 1 つの油田を選び、ランダムに選んだ場所に移動させます。

近傍 3: 2 つの油田の入れ替え（選択率: 4 / 16）

ランダムに 2 つの油田を選び、2 つの油田の位置を入れ替えます。

石油埋蔵量が変化するマスの数が最も少なくなるような入れ替えのみを近傍として設定しました。複数通りある場合はそのいずれかをランダムに選びます。入れ替え方は入力を読み込んだ直後に事前計算します。

状態の持ち方

状態は、各油田の左上の座標と、各占いに対する石油埋蔵量を保持するようにしました。 $N \times N$ の二次元グリッドは使いません。

油田が $M$ 個あって、それぞれの置き方はたかだか $N^{2}$ 通りしかありません。すなわち、1 つの油田を選んで配置する場合の数は $O(N^{2} M)$ です。そこで、占いの結果を得るたびに $O(N^{2} M)$ 通りそれぞれに対して占った場所の個数を計算するようにしました。この処理によって石油埋蔵量を $O(|Q|)$ で更新できます。

また、占いの結果を得るたびに、実際の石油埋蔵量が $k$ だったときにその占いの観測値が得られる確率も計算しておきます。焼きなまし法の最中に誤差関数を呼ぶ必要がなくなり、尤度の計算を $O(|Q|)$ で実現できます。

実装では石油埋蔵量が変わる占いのみを取り出して更新していますが、石油埋蔵量が変わる占いの割合が高そうなので高速化されているかはわかりません。

多点スタート

8 つの状態を並行して焼きなまし、少しずつ状態を減らすようにしました。

状態を減らすとき、基本的にはその時点での評価値が最も低いものが削除されます。ただし、評価値の悪化を許容した直後に削除されるようなケースもあるため、評価値の指数移動平均をとったり、遷移の受容確率を評価したりしました。改善の寄与は小さいです。

初期状態

焼きなまし法の 1 ターン目の初期状態はランダムに生成しますが、2 ターン目以降の初期状態として、1 つ前のターンで得られた油田配置の中から尤度が高いものを選ぶようにしました。

初期解の尤度が高いと焼きなまし法の収束が速くなり、探索性能が改善されるようでした。

8 つの状態から 32 個の状態を生成し、次のターンは 32 個の状態から評価値が高い 8 つの状態を選ぶため、焼きなまし法を遷移としたビームサーチと捉えることもできます。

温度の自動調節

基本的には、初期温度を 6.0、最終温度を 0.6 にして温度を指数的に減少させます。

ただし、温度を上記のように固定すると、占いの回数が増えるにつれて焼きなまし法の遷移採択率が低くなるようだったので、採択率が 0.04 を下回ったときに初期温度と最終温度を 1.05 倍しました。採択率が 0.04 以上になるように温度を自動調節しているつもりです。難しいケースだと初期温度が 10.0 程度まで上がるようでした。