※画像は公式Visualizerよりお借りしました
はじめに
本日は2/18 - 2/26の期間にAtCoderで開催されたコンテスト「RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。
2/18-2/26日の間、AHC018に取り組みました。AHC017に参加できなかった悔しさもあり相応の時間を費やしまして、最終順位は23位でした（システス後まで順位表一ページ目は保てなかった・・・）。AHCに参加するのはこれで四回目ですが、過去最高順位（そして初橙パフォ）でした！
問題設定も面白く、ヴィジュアライザで自分のプログラムの解を眺めるだけでも楽しかったです。
Postmortemの経験も増えてきましたが、いまだ用語がよくわかっておらずところどころ間違っていたりすると思います。発見された方は優しくご指摘いただけると嬉しいです。
問題概要
問題内容は、私自身が伝えるより問題文自体を見ていただいたほうが伝わるとおもうので以下にリンクを張っておきます。
簡単にまとめると「水道を引きたいんですが地質調査してないのでいい感じのルート見つけながら掘ってください」という問題でした。
この記事で用いる独自表現
・flow
水が流れているマスのことを言います。すなわち、
・水源マス
・水源マスとつながっているすでに掘削されたマス
の二つを指します。
最終提出AIの詳細（戦術など）
seed:0での様子を貼っておきます。
言語:Go言語
いつもの。個人的な好みであり、特に言語的な利点はないです。
解法
以下、AIの概要です。
・基本は2フェーズ
掘削計画の基本は二つのフェーズからなっています。
フェーズ1: investigate
このフェーズでは代表点をとり未知のフィールドの様子をざっくりとつかみます。
1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む
2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める
ここでもしミニフィールドの最短路上の代表点で壊せていないところがなければフェーズ1を終えフェーズ2に移行
3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。
4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更
フェーズ2: destruct
このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。
1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完
2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）
3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）
4. 家側から順番に掘削
もう少し詳しいところは以下で見ていきます。もし長い文字列で目が滑ってしまうような場合には、上に乗せたseed=0での様子と照らし合わせてみるとよいかもしれません。
・フェーズ1: investigate
1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む
落とし込み方としては「家、水源、flowを最も近い代表点に丸める」という方法があると思いますが、最終提出では「左上、左下、右上、右下方向でそれぞれ一番近い代表点（計4点）に分裂させる」という手法をとっています。
2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める
Dijkstra法です。
ミニフィールド上では、移動は8方向にとります。これは、200*200フィールドにおいて、代表点間は縦→横→縦→横→・・・と繰り返すことで上下左右の代表点に近づくことなく斜めの代表点に移動できることが関係しています。
移動コストを考えるときには、各代表点の頑丈さの推定値を用います。
壊したことのあるマス・・・壊すまでにかかったパワー
パワーを加えたことがあるが壊せていないマス・・・そこに費やしたパワー×5
パワーを加えたことがないマス・・・C×5
といった具合に雑に推定しておきます。×5としているところを増加させると寄り道を考えずらくなり、逆に減少させるとあちこち調査するようになります。
また、移動コストの計算は縦横移動と斜め移動で多少変わります。代表点を12マス間隔でとると17×17のミニフィールドが出来上がるわけですが、以下ではわかりやすく2×2のミニフィールドでいくつかの移動コスト例を見ます。
を(i,j)の頑丈さの推定値とする。
(0,0)から(0,1)（横移動）のコスト:
(0,0)から(1,1)（斜め移動）のコスト:
(0,0)から(1,1)への移動の仕方は以下の3つが考えられます。
・(0,0)→(0,1)→(1,1)
・(0,0)→(1,1)
・(0,0)→(1,0)→(1,1)
この計算式により、(0,1),(1,0)の頑丈さによっては、斜めに突っ切るほうが近いと判定してもらえることがわかります。
なお、このコストの式はフェーズ2での補完の値との整合性が取れるようになっています。
3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。
パワーは
・まだ掘ったことがないなら、Cの値と同じだけの力で掘る
・掘ったことがあるならこれまで累計で与えた力と同じ力で掘る
といった具合です。この掘り方では最悪のケースでも最適な掘り方の二倍のコストで掘ることができます。
4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更
今回掘ろうとしたマスに累計で与えたパワーを更新しておきます。
・フェーズ2: destruct
このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。
1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完
以下は10マス間隔で代表点を取っていたころの図ですが、4つの代表点から正方形エリアをこのように補完します。（線型）
（この図は左下と右下が比較的柔らかく、左上と右下が硬い場合です）
この補完は補完の仕方よりもPhase1のミニフィールドでのコストの式と整合性をとることが重要です。
整合性が取れてないとこんな悲しいことに・・・
2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）
お決まりのDijkstra法になります。
3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）
追加調査前
追加調査後
このくらいの幅でサンプルを取っておくと頑丈さを大きく外すことはないので、これ以上幅を小さくしてもあまり効果はなかったです。
4. 家側から順番に掘削
「思ったよりも掘削に力が必要だった」、逆に「ちょっと軽めにたたいたつもりだったのに壊せちゃった」があれば、前後の掘削ルートの頑丈さの推定値を微妙に操作します。これも「微妙な操作」の式自体はあんまり関係がなくて（実際雑です）、「想定よりも硬い・柔らかい」が減衰しながら次以降の掘りに反映されているところが大事だと思われます。
おわりに
ここまで読んでいただきありがとうございます。過去最高順位をとることができたのもうれしかったですが、何より自分のプログラムがしっかりと硬いところを避けて掘削しているのをVisualizerで見ることができて感動しました。私は戦略性+Visualizer（ゲームをするかのような頭の使い方と視覚的な要素）からヒューリスティック系のコンテストに興味を持ったタイプで、毎度公式Visualizerが用意されているのには頭が上がりません。
次に参加するコンテストをどれにするかは未定ですが（早ければ今週末のあれかも）、次回コンテストでもまた楽しんでいきたいです。お世話になった方々、ありがとうございました！
おまけ
基本的にPostmortemは以上になります。ここからは見出しにもある通り完全におまけですので、見ても有益なものはないかもしれません。
思ったこと、追加情報をまとまりもなく書きとどめておきます。
追加情報
・Phase1での横移動・斜め移動のコストは、Phase2で補完したときの横移動×12の総コスト・（横移動＋縦移動）×12の総コストとほぼ一致する
・ミニフィールドに落とし込む際には、flowなどと代表点の距離を用いてDijkstra法の際に初期値を増やしておくことで誤差を減らすことができる
・掘削で頑丈さを計測する時、「計測を正確にしたい」と「破壊までにかかる回数をおさえたい」がトレードオフな関係なので、あまり丁寧な計測は効果がなかった
・Phase2の代表点間の補完は線形より良い近似もあるが、追加サンプルもふまえると正確さとしてはそれ以上突き詰める必要は感じなかった
・道をつなげるとき、一発目はCに応じて予想コストの0.8倍~0.95倍で掘削していた
・ローカルで実行する際、「phase1でかかったコストを無視するか」「最適な力で掘削するか」などフラグを用意しておくと自分のプログラムの問題点が把握しやすくてよかった
考えたこと
・インタラクティブ問題はローカルでの実行に壁を感じて参加者が少なくなるかと思ったけどそんなことなかった
・問題見たときに「水道つなげる前に地質調査しようよ」と思ったけど、本当に最初に地質調査する問題だった
・最も柔らかい部分と最も硬い部分の差が500倍もあるというのがあまり実感がわかず、最初は調査すると自明解より弱くなるんじゃないかと思っていた
・人間の温かみのあるパラメータ調整が自分の武器だと思っているので、全人類がOptunaをうまく使えるようになってしまうとなかなか苦しい
次回以降に向けて思ったこと
・みんなの自作ビジュアライザがかっこいいので自分も作りたい。（他の方のVisualizerって毎回すごい見た目してるけど典型みたいなものはあらかじめ持ってるのだろうか？はたまたコンテスト中に０から作っているのか・・・？）
・ローカルで大量テストができる環境作りたい。
・コンテスト中に焼きなまししたい。（ほんとは今回するつもりで意気込んでいたんだけど・・・）
