THIRDコン2023（AtCoder Heuristic Contest 030）お疲れ様でした。2,140,937,483,257点で優勝です！長期コン初優勝なのでめちゃくちゃ嬉しいです。今回も解説記事を書きます。

問題概要

掘ったり占ったりして油田の位置を当てて石油王になってね（そこまでは言ってない）。

atcoder.jp

前提知識

この記事は以下の前提知識を必要としています（全部知らなくても、ある程度理解することはできると思います）。

ベイズの定理
エントロピー（情報量）
相互情報量
ガウス過程回帰

上3つについてはAHCラジオやあぷりしあさんの記事（ベイズの定理の記事・相互情報量の記事）で紹介されているので、そちらを読むと良さそうです。ただ何も説明しないのもアレなので、エントロピーについて簡単に説明していきます。

エントロピー

※私は大学で情報学を履修しておらず、本を軽く読んだ程度の知識しかないので、間違っている点があればご指摘ください。

エントロピーとは一言で言えば「どのくらい不確実なのかを数値化したもの」です。起こりうる事象 $x$ が $N$ 個あり、 $i$ 番目の事象の起こる確率が $p_i$ であるとき、エントロピー $H(x)$ は $H(x)=-\sum_{i=1}^Np_i\log_2p_i$ と定義されます。*1

……式だけ見てもイメージしづらいので、具体的な例を見ていきましょう。以下のように $3\times3$ マスのグリッドがあり、青と橙の $2$ つのポリオミノが存在する状況を考えます。

この時あり得る配置 $x$ は $4$ 通りです。事象 $i$ が発生する確率が全て等しく $p_i=\frac{1}{4}$ であったとすると、エントロピーは $H(x)=-\sum_ip_i\log_2p_i$ $=-\sum_i\frac{1}{4}\log_2\frac{1}{4}$ $=2$ となります。不確実性が $2\ \mathrm{bit}$ 分あるということですね。

ここで左上のマスを掘ったところ、石油埋蔵量 $v(0,0)=1$ だと判明したとしましょう。そのとき、 $4$ 通りの配置のうち $2$ 通りはあり得ないということが分かったので、再度エントロピーの定義式通りに計算すると $H(x)=-\sum_ip_i\log_2p_i$ $=-\sum_i\frac{1}{2}\log_2\frac{1}{2}$ $=1$ となります。不確実性が $2\ \mathrm{bit}$ 分から $1\ \mathrm{bit}$ 分に減少しました。

今度はさらに左下マスも掘ってみて、石油埋蔵量 $v(2,0)=0$ だと判明したとしましょう。するとエントロピーは $H(x)=-\sum_ip_i\log_2p_i$ $=-\sum_i\frac{1}{1}\log_2\frac{1}{1}$ $=0$ となります。不確実性が0なので、配置が完全に確定したということですね。このように、何度もクエリを投げることでエントロピーを0（に十分近い値）にすることがこの問題の目的です。

条件付きエントロピーと相互情報量

このエントロピーを使うと、どのマスを掘ると嬉しいかを定量的に評価することができます。先程の問題に戻って、左上のマスと右上のマスのどちらを掘った方が良さそうか考えてみましょう。

最終的にエントロピーを0にしたいので、掘った後のエントロピーが0に近くなるような掘り方をすると良さそうです。ただし注意点として、まだ掘る前なので石油埋蔵量 $v$ が実際に何の値になるかは分かりません。したがって全ての $v_j$ について、 $v=v_j$ だったと仮定したときのエントロピー $H_{v=v_j}(x)$ を考え、それを各 $v_j$ の起こる確率 $q_j$ で重み付けして期待値を求めることにしましょう。この値 $H_v(x)=\sum_jq_jH_{v=v_j}(x)$ のことを条件付きエントロピーと呼びます。

さて、左上マスを調べるときの条件付きエントロピー（エントロピーの期待値）を計算してみましょう。

$v(0,0)=0$ が出ても $v(0,0)=1$ が出てもエントロピーは $1$ となるので、エントロピーの期待値は $1$ です。どちらの値が出ても二択が残るようですね。

同様に右上マスを調べるときの条件付きエントロピーも計算してみます。

$v(0,2)=0$ が出るときと $v(0,2)=2$ が出るときは配置が一意に確定するため、エントロピーは $0$ となります。 $v(0,2)=1$ が出るときは二択が残ってしまい、エントロピーは $1$ です。この期待値を取ると、確率 $1/4+1/4=1/2$ でエントロピーは $0$ 、確率 $1/2$ でエントロピーが $1$ になるので、エントロピーの期待値は $1/2$ です。さっきよりもエントロピーの期待値が小さくなっていますね！したがって、左上マスを掘るより右上マスを掘る方が嬉しい気持ちになれそうです。

このように、条件付きエントロピーという考え方を取り入れると、ある場所を掘ったときの嬉しさを定量的に評価することができます。なお、上記の説明では簡単のために起こりうる/起こり得ないの0/1で評価していましたが、占いの結果起こりやすそう/起こりにくそうという曖昧な値でも、各配置の起こりうる確率 $p_i$ と占った結果 $v=v_j$ となる確率 $q_j$ の2つが分かれば計算することができます。

そして、 $v$ について調査することで元の値 $H(x)$ からエントロピーがどのくらい減少するかの期待値 $I(v,x)=H(x)-H_v(x)$ を相互情報量と呼びます。できるだけ少ないコストでできるだけエントロピーをたくさん減少させたいので、エントロピー減少量の期待値 $I(v,x)$ をコスト $C$ で割った $I(v,x)/C$ が最大になるような占いの仕方を山登りで求めるのが私の解法でした。

ちなみに、エントロピーについてもっと丁寧に学びたい方は以下の本もオススメです。私もこの辺りの知識はもともと持ち合わせていなかったのですが、昨年夏のハーフマラソンのときにこちらの本を読んで初めて知りました。1章さえ読めば今回のコンテストに使うには十分な知識が得られると思います。*2

情報理論 (ちくま学芸文庫)

作者:甘利俊一
筑摩書房

Amazon

解法

事前知識について学んだので、ようやく解法の説明に入っていきます。

AHC030お疲れ様でした！暫定1位かな？めちゃくちゃ面白い問題でした……！
可能性の高そうな配置を焼きなましっぽい謎BFSでたくさん生成しつつ、クエリ後のエントロピーの期待値が最小になるような（相互情報量が最大になるような）占い方を毎ターン山登りで生成しました。 #AHC030 pic.twitter.com/yv0NGdyQr7
— TERRY (@terry_u16) 2024年2月19日

AHCラジオとだいぶ被ってしまいますが、以下のような流れで解きました。

今までの占い結果を考慮したときに起こり得そうな油田配置を謎乱択BFSでたくさん生成する
「占うマスの集合を決め打ったときの、占い結果と油田の配置との相互情報量をコストで割ったもの」が最大となるようなマスの集合を山登りで求める
十分確信が持てるまで1.と2.を繰り返し、確信が持てたら回答を行う

ただこの解法だけだと $M$ が大きいときに特定しきれないことが多いため、以下のような1マス掘り戦略も併用して難易度によって切り替えました。

今までの占い結果と矛盾しない油田配置を謎乱択BFSでたくさん生成する
「掘るマス1つを決め打ったときの相互情報量」が最大となるようなマスを全探索で求める
十分確信が持てるまで1.と2.を繰り返し、確信が持てたら回答を行う

1マス掘り戦略

1マス掘り戦略と複数マス占い戦略の2つを使い分けたのですが、前者の方がシンプルなのでそちらから説明します。

まず、本来やりたいことは以下の通りです。

全てのあり得る配置を全部列挙する
1マス掘ったときの相互情報量が最も大きいマスを探して掘る
十分確信が持てるまで1.と2.を繰り返し、確信が持てたら回答を行う

このうち2.については、全てのあり得る配置 $x$ を $T$ 個全部列挙できていればマス $(r, c)$ を掘ったときに石油埋蔵量が $v_j$ である確率 $q_j$ は簡単に求められ、そのときのエントロピー $H_{v=v_j}(x)$ はこれに矛盾しない配置の数を $T_{v_j}$ として $H_{v=v_j}(x)=\log_2{T_{v_j}}$ となります。よって相互情報量 $I(v,x)$ は $I(v,x)=H(x)-H_v(x)$ $=\log_2T-\sum_j q_jH_{v=v_j}(x)$ $=\log_2T-\frac{1}{T}\sum_j{T_{v_j}}\log_2{T_{v_j}}$ となり、これが最大となるマス（すなわち $\sum_j T_{v_j}\log_2{T_{v_j}}$ が最小となるマス）を選んで掘ればよいです。

もう1つの1.が難しいです。 $M=2$ のケースでは全ての候補を列挙できますが、候補の数は概ね $N^{2M}$ 個くらいあるため $M$ が大きくなると手に負えなくなってきます。そこで、あり得る配置を山登りのような謎乱択BFSで列挙していきます。

まず適当な配置を作り、それが今まで判明した石油埋蔵量とどれだけ矛盾しているかという値をペナルティとします。このペナルティが0である配置をたくさん作りたいので、これを山登りで求めることを考えます。ある配置 $x$ に対して、「ポリオミノをランダムに $K$ 個削除し、ペナルティが小さくなるように1つずつ貪欲に配置し直す*3」という破壊再構築近傍を適用した配置 $x'$ を求めます。そして $x'$ のペナルティが $x$ のペナルティ以下になっていれば採用、そうでなければ不採用とすれば、ペナルティの小さい配置をたくさん集められそうです。

今回は最新の $x$ だけを使って山登りするのではなく、今までに集めた配置のうちペナルティが最小値タイのものをプールしておき、プールから等確率にランダムに1つ $x$ を持ってきて近傍を適用し、 $x'$ をプールに戻すということを繰り返しました。*4 こうするとそれっぽい $x$ がたくさん得られるので、得られた $x$ の集合を全てのあり得る配置と思い込んで2.を適用すればよいです。

以上を動画にするとこんな感じです。薄く表示されているポリオミノは、あり得る配置の一つを表しています。エントロピーが大きいとき（不確実性が高いとき）は薄く、エントロピーが小さいとき（不確実性が低いとき）は濃く表示されるようになっています。下側のポリオミノから順番に位置が確定していっていることが分かるかなと思います。

複数マス占い戦略

複数マス占い戦略は以下の流れで行います。大まかな流れは1マス掘り戦略と同じです。

今までの占い結果を考慮したときに起こり得そうな油田配置を謎乱択BFSでたくさん生成する
「占うマスの集合を決め打ったときの、占い結果と油田の配置との相互情報量をコストで割ったもの」が最大となるようなマスの集合を山登りで求める
十分確信が持てるまで1.と2.を繰り返し、確信が持てたら回答を行う

まず1.についてですが、1マス掘り戦略から以下が変わっています。

配置の評価関数を、占い結果を元にした対数尤度とする
評価関数の最も良かったものだけでなく、一定数を全てプールしておく
プールから等確率に持ってくるのではなく、尤度の比で重み付けしてランダムに取り出す*5
近傍の中で行う貪欲については、配置したときの尤度の比で重み付けして配置位置を乱択する

1.の変更点はそのくらいで、あとはほぼ1マス掘り戦略と同じです。ベイズ推定を用いた対数尤度の計算については公式スライドやeijirouさんの記事が詳しいので、そちらに譲ります。

なお評価関数の計算に今までのクエリ回数を $Q$ として $O(Q)$ 、近傍で置き場所の全探索にポリオミノあたり $O(N^2)$ かかっているので、近傍の計算量が $O(N^2KQ)$ とかなり大きくなってしまったのが悩みの種でした。この辺の焼きなまし力は他の上位陣に負けている気がします。*6

そして2.については、当然ながら1マス選べば良いのではなくマスの集合を選ぶ必要があります。そのため全探索ではなく山登りを用いて、コストあたりの相互情報量 $I(v,x)\sqrt k$ が最大となるようなマスの集合 $S$ を求めました。

以上を動画にするとこんな感じです。このような簡単なケースでは、1マス掘り戦略と比べてかなり小さいコストで特定できるようになっています。

パラメータチューニング

今回の問題はパラメータチューニングがかなり重要だったように思います。正解までに消費するクエリ数が読みづらいのですが、盤面の難易度に応じてどのくらいクエリを使うかをどうにかして推測できれば、そこから各ターンの計算時間を決めることで実行時間を有効に使うことができます。私の謎乱択BFSの性能は他の上位陣に比べておそらく良くなかったのですが、実行時間を長くすればスコアが上がることは分かっていたため、ここのチューニングでなんとか挽回できたのではないかと思います。

今回は主に以下の値をパラメータとしました。各 $N,\ M,\ \epsilon$ およびポリオミノサイズの平均値 $\bar{s}$ に応じて、各パラメータについて最適な値が選ばれるようにしたいです。

ターンごとの実行時間
- ターンを $0\le t\le 1$ となるように正規化した上で、 $t$ ターン目の実行時間を $(1.0-t)^\kappa +bt$ に比例させるとして、 $\kappa,b$ をチューニング
謎乱択BFSと相互情報量山登りの実行時間の比
1マス掘り戦略と複数マス占い戦略のどちらを使うか
相互情報量山登りの際、状態を最大何個まで考慮するか
尤度比がどのくらいになったら答えるか

どの $(N, M, \epsilon, \bar{s})$ の組でも同じパラメータを使うのであれば、optunaで最適化するだけで終わりです。しかし、 $(N, M, \epsilon, \bar{s})$ に応じてパラメータを変化させるとなると途端に難しくなります。

割と思い付きやすいのは「グリッドサーチしてそれぞれの点 $(N_i, M_i, \epsilon_i, \bar{s}_i)$ でパラメータをチューニングし、線形補間する」という戦略かなと思いますが、入力が4次元なのでかなりグリッドを粗くしないと必要な点数が膨大になってしまいそうです。

そこで今回はランダムな点（30～90点程度）においてoptunaで最適化した上で、ガウス過程回帰を用いてそれらを滑らかに繋ぐことにしました。最小二乗法を直線ではなく良い感じの曲線で行うイメージです。*7

これは結構効果が大きく、導入前後で手元1000ケースのスコアが6～7%ほど向上する結果になりました。これがなければ3位か4位くらいになっていただろうと思います。

ちなみにガウス過程回帰は以前のAHCで解説記事にしているため、よろしければそちらもお読みください。以下の本もオススメです。

www.terry-u16.net

ガウス過程と機械学習 (機械学習プロフェッショナルシリーズ)

作者:持橋大地,大羽成征
講談社

Amazon

日記

コンテスト中の日記を以下に置いています。ただし最後の4日分は日記書いてないです（は？）

github.com

感想

完全に1週間を捧げてしまったのですが、その甲斐あって1位を取れてかなり嬉しいです。短期コンは1位を取れていたのですが長期コンはなかなか1位を取れていなかったので、喜びもひとしおでした。個人的にはパラメータチューニングにガウス過程回帰を使うというオリジナリティを出せたのが一推しポイントです。

一方で焼きなまし力にはまだまだ課題を感じました。小さな近傍だと上手く焼けないと思っていたのですが、全然そんなことはなかったようで……。軽くて小さな近傍を選ぶか重くて大きな近傍を選ぶかの判断はなかなか難しいですね……。

今回の問題は歴代AHCの中でもかなり好きな方に入りました。昨年夏のハーフマラソンでコンテスト中に本を買ってエントロピーの基礎を勉強していたのですが、そのときの知識*8がまさかここで活かせるとは思っていませんでした。しかしベイズ推定&エントロピーの知識ゲーかと思いきや、実は最終的には焼きなまし性能バトルだったという奥の深さはさすがwataさんだなあと感じました。優勝したとはいえwataさんにボロ負けしたのは悔しいので精進しようと思います。

来年はAWTFのAHC版も開催されるので、ここで1位を取れたのはかなり大きいですね。AWTF出場できるように長期的にも頑張りつつ、まずはマスターズも勝ちに行きたいと思います！

*1:logの底を2としていますが、別に2でない値でも良いです。底を2とすると「不確実性が何bit分あるか？」と直感的に解釈しやすいので、今回は底を2としています。

*2:というか私はまだ1章しか読んでいません……。

*3:そのような場所が複数ある場合はランダムに選んでいます。

*4:プールをキューのようなものと考えるとBFSっぽく解釈できるので、謎乱択BFSと呼んでいます。ペナルティの最小値が更新されたらプールの中身を捨てていきます。

*5:尤度の累積和を持っておけば、プールサイズをPとしてO(logP)でサンプリングできます。実装の際には尤度のアンダーフローに注意してください。

*6:計算量は重いのですが計算式自体は単純なため、SIMDによる高速化が結構効きます。尤度を64bit浮動小数点数から32bit浮動小数点数にしたうえで、AVXをゴリゴリ書くことで相対的にだいぶ速くなりました。

*7:余談ですが、ガウス過程回帰のカーネルのハイパーパラメータのチューニングにもoptunaを使用したため、「解答コードのスコアを最大化するパラメータをoptunaで最適化した結果をガウス過程回帰で補間するためのカーネルのハイパーパラメータをoptunaで最適化する」というなんともややこしいことになっていました。

*8:といってもごくごく基礎的な内容ですが。