RECRUIT 日本橋ハーフマラソン 2023冬（AHC018）、対戦ありがとうございました。暫定10位（想定バフォ2804）と、過去最高の成績を出せましたので、解法を紹介します。
最終は16位（パフォ2668）でしたが、それでもダントツの過去最高でした。
全般的には、以下のアルゴリズムを使っています。
- ダイクストラ法
- 最小全域木
- 山登り法（やっていることは「川下り」なので、紛らわしい・・・）
なお、他の上位解法と比較すると、以下の特徴がありました。
- 岩盤の厚さの予測は、初期設定と掘削中の箇所の更新、最終の格子点間線分の線形補間だけおこない、格子点については隣接含め盤面の局所的大域的な予測は実施していない。
- ダイクストラ法と最小全域木を組み合わせた最適ルート探索を、毎ターン実施している。
- 上記のため、無駄な調査掘削をほとんど行っていない。
また、コーディングは、検討をPythonで、提出プログラムをRustで実施しています。この組み合わせが、AHCでの最強の組み合わせであると、筆者は考えています。
Rustに関しては、残念ながら本記事では、具体的には言及されていません。
1. Perlin noise を知っていますか？私は知りません
今回の出題は、水脈が点在している岩盤地形上に、どのように水脈を掘削すると、すべての家に水が供給できるか？というものです。岩盤は、ゲームの地形自動作成などで使われる Perlin noise というものを使ってつくられています。
この岩盤は、ビジュアライザを見ると、ランダムとは程遠く、自然な渓谷や尾根がつくられているようです。また、解答プログラムの入力では岩盤の数値は隠されていますが、テストデータでは岩盤の数値がすべて明確になっています。これは、非常につかえる事実です。
筆者は、開始当初の土日は参加できなかったので、平日はしばらく、テストデータの分析に費やしました。Pythonで、NumPy、Pandas、Matplotlibなどを使いこなしていると、こういう作業が楽にできます。
1.1. 理想解をつくる
いくつかのテストデータを使って、「理想的な解」をつくってみましょう。
自分のアルゴ（水）の能力でも、次のような「理想（に近い）解」のアルゴリズムが考えられます。
- ちょうど良いPowerで岩盤を掘削完了した時にスコア値として加算される、
岩盤の厚さ + Cを辺の重みとする。 - 水源・家を相互に結ぶ「最短距離辺」を、ダイクストラ法を何回か使うことで求める。
- 水源（のうち少なくとも1つ）と家を結ぶ最小全域木をつくる。
- この時、UnionFindで、最初に「水源同士をすべてつなぐ」処理をすることで、余分な水源はつながらなくてよく、さらに、家と水源のセットが、複数非連結でできるような形も許容できる。
最後の部分が、ABC-E問題くらいの難易度だと思いました。辺同士が途中で重なったりする場合は、もっと良い解をつくることができますが、そこまでは拘らないことにします。
すると、次のようなヒートマップ上の経路をつくることができます。図示はビジュアライザでもできますが、いろいろ加工して調べられるように、Pythonでつくっています。
Seed=0の場合
想定どおり、渓谷のところをなるべく通るような経路ができています。
Seed=6の場合
この結果は、いろいろ示唆がありました。
- 水源が複数ある場合、かならずしも木にならなくてよい。非連結でも解として有効。
- 左上のように、経路上どうしても尾根をとおる必要がある場合がある。
- 左中央部のように、初期のアルゴリズムの特性上、むだな経路がわずかにできる。
1.2. Perlin noise の特性を知る
次に、テストデータを少し多めに生成して、岩盤地形の数値的特徴をとらえてみます
左上のグラフはすべての岩盤、右上は水源のみ、左下は家のみ、右下は最短経路のみを抽出しています。それぞれ、X軸が各テストケース、Y軸が岩盤の厚さです。
未知の数値データは、平均値たけをみるのでなく、最大最小、中央値、四分位値といったものをみると、傾向がわかりやすいです。すべてのグラフは、左上グラフの中央値でX軸をソートしています。
このグラフから、以下のような重要な事実がわかります。
- ケースによって、岩盤の厚さの数値はかなり異なるが、25%、50%、75%、最大値のY軸の間隔（対数比）は、ほぼ等しい。
- 水源や家の岩盤は、すべての岩盤と比較して、かなり薄く設定されている（これは問題文からもすぐにわかります）。
- 水源や家の岩盤は（対象となる数が少ないため）、その厚さがわかったからといって、全体の傾向は推測できない。
- 経路の岩盤は、水源や家ほどではないが、薄い。また、すべての岩盤とそれなりに相関が認められる。
1.3. 岩盤の厚さを推定する
実際の解答においては、岩盤の厚さはわかりませんので、それまでの試行によって得られた事実をもとに、事後推定を確からしくできるか、がポイントになります。
掘削の試行結果に応じて、以下の事実が確定します。
- 岩盤の厚さは10〜5000である。
- 掘削したが、未完了の場合、それまでに掘削した量+1が岩盤の厚さの最小値である。
- 掘削完了し場合、それまでに掘削した量が岩盤の厚さの最大値である。
よって、岩盤の最小値・最大値を管理して、確定した事実を更新していきます。さらに、最小値と最大値が更新された時に、岩盤の推測値を事後推定として更新します。ここで、前節で得られた「岩盤の厚さの対数比を存在確率でプロットすると線形の関係性がみられる」という重要な事実を使うと、以下のような事後推定の式を得ることができます。
$$
pred_{\ new} = \exp((1 - p0) \times \ln(MIN) + p0 \times \ln(MAX))
$$
p0はハイパーパラメータです。なお、前節の事実をもとに、水源か家だと判別（すぐにできます）した場合は、違うパラメータにします。
実際、p0=0.5（50%=中央値）、MIN=10、MAX=5000とすると、計算結果は約224となり、前節のグラフの中央値と、とても近い値になります。
Perlin noise の式をもとに、この事後推定の式が解析的に求められれば、カッコいいです。（できるかどうか、知りません）
冒頭にも書いているように、隣接を含む局所的・大域的な予測は、いっさいやりませんでした。（最終的に格子点の間を掘削する際の線形補間を除く）
2. 複雑性を排する格子解法は典型です
岩盤の厚さの予測値が求められたため、テストデータで最適経路を求めたアルゴリズムを適用することが可能です。「最適そうな経路」を実際に掘削し、掘削した結果で岩盤の予測を更新していく「山登り法」を使えば、うまく解けるはずです。
ところが以下のように、大きな問題にぶつかりました。
- 200x200とはいえ、ダイクストラを何回も繰り返すと計算量が大きくなる。
- 岩盤の予測の精度を上げるには、岩盤をかなり掘らないといけないため、無駄な掘削が多くなり、結果としてスコアが悪化する。
ビジュアライザの結果をみると、とても無駄に掘削していることがわかるでしょう。
1つめの問題を解決するために、ダイクストラの実行頻度を減らすと、2つめの問題が大きくなってしまう、という八方塞がりです。
これを打開するには、ヒューリスティックの典型である「複雑性の排除」を考えて、200x200すべてを通行可能とするのではなく、格子状の通路のみ通行可能（家や水源は最寄りの格子点と接続可能）とします。AHC012の解法に近いです。
参考: 格子で切る、AHC012の上位解法（筆者は時間内に思いつきませんでした）
格子型に制限することで、以下の効果があります。
- ダイクストラを格子点（+水源+家）だけに限定できるため、計算量を大きく減らすことができる。
- 微妙に異なる場所を掘削してしまう、という無駄が無くなり、掘削場所を絞り込め、早く最適に近い解を得ることができる。
- 通行可能性がある経路が限られるため、似て非なる無駄な経路をつくらない。
格子点がすべて確定した後に、最適経路をつくる格子点の間の区間を、いっきに掘削していきます。格子点間の岩盤の推測には、単純な線形補間を使いました。
なお、水源と家だけを起点に最小全域木をつくったあと、得られた格子点をすべて加えた状態でもう一度最小全域木をつくる、という段階を踏むことで、無駄なループが残ることを防止できます。
このアイデアにより、スコアを大きく改善することができました。なお最終的に改善したのは、バグが取れた土曜の夜でした。格子点のstepは9にするとスコアが良くなりました。
結果として、以下のようなビジュアライザの出力を得ることができます。
Seed=0
Seed=6
とても効率的な経路を通っていることがわかります。また、最終経路以外の掘削箇所は格子点のみ、それも低地に偏っていますので、無駄な掘削も少ないことがわかります。
ここまでの結果で20位近辺にスコアアップしました。
3. 締めはOptunaでハイパラチューニング
これまでの記事で登場した値のほかにも、いくつか決められないパラメータを、ハイパーパラメータとして、コマンドライン引数から更新できるようにしておきます。最後にOptunaを使って、最適なハイパーバラメータのセットを求めます。
チューニングにあたって2つポイントがあります。
- 相対スコアでチューニングすること。
- Cの値でチューニングを別に行うこと。
相対スコアは首位の人のスコアとの比で求められるため、正確な算出はできません。しかしながら、Myベストを基準にしておくと、テストケースごとの特性差による絶対スコアへの影響を排除できます。相対スコアを使うことで、絶対スコアであまり差が出なくても、順位が大きくあげられる「筋」を見出すことができました。
今回の問題は、Cの値により、いろいろな数値が大きく影響されます。そのため、余裕があるなら、Cの値ごとにOptunaでチューニングします。なお、同じデータでCだけを変えたものを使った方が比較がしやすいですので、テストケースの数値を自分で変えて作成しました。
以上により、10位近辺までスコアアップしました。
4. やらなかったこと
以下は、時間の関係や効果が得られなくて（実装バグかもしれず、本当に効果が無い手法なのか切り分けできていません）、やらなかったことです。
- （本文でも言及しましたが、）現在の盤面全体の推測値により、推測値をなめらかに最適化すること。格子型にしているため、畳み込み演算を使えば、何かできそうな気がします。ガウス過程回帰も発想しましたが、標本値がなかなか確定しない今回の問題では、使いにくいと思いました。
- 水源や家と、格子との接続において、格子点ではなく、格子「線」と直角に接続をすることで、より接続を効率的にすること。形状によっては少し距離を得します。
- 格子のstepを順次変えていくこと。初回32→16→8など。最初に粗く全体を捉えて、だんだんと解像度を高くすると、効率的かもしれません。
- 山登りから焼きなましへの変更。今回のような、環境情報が不完全な中で試行回数が増えるほどペナルティがつくタイプの問題は、一般的には焼きなましは困難です。ただし、強化学習におけるε-greedy方策を応用して、「時々、最適経路以外のところを掘削してみる」という動きをすることで、焼きなまし効果を得ることができそうです。
- 全般的な高速化。特にC=1の場合、稀に掘削回数が多くなるため時間的に厳しくなりがちです。対策として、途中でダイクストラの更新頻度を落としたり、山登り途中で諦めたりしたため、スコアが伸びにくかったです。最終的には、推定値を更新するのは1回に１箇所だけだっので、差分ダイクストラを使えば改善したかもです。
- 余った時間の活用。逆にCが大きい時は、時間があまりますので、他のアイデアを入れて予測改善させることができたかもしれません。