AHC054 参加記
長期の AHC を初めてまじめにやったので、せっかくなので記録を書いておきます。コンテスト終了時点の暫定順位で 9 位
問題はここにあります
コンテスト中考えていたこと
- インタラクティブ要素、本当に活用できるんだろうか？
- 次の目的地にたどり着くまでになるべく変なところを訪問させるゲームか？と最初思っていた。しかし、その間に訪問する箇所って基本的に今いる位置とか目的地とかの周辺なので、あまり移動距離を大きくできない。一方、目的地の選び直しをたくさんさせられれば、結構遠くまで行ける可能性が高くなるので、「マス間の距離を長く保ちつつ、なるべくたくさんの目的地を訪問させる」のが目標らしい、ということがわかる。
- 盤面構成はそこそこ速くなったが、盤面の評価が絶望的に遅いのでなんとかしたい。いい感じの評価関数を作れないか？
- いろいろ考えてみたが、スコアがかなり細かい盤面の変化にも敏感ということがわかり、諦めてしまった
- 雑な評価関数では、評価関数の値と実際のスコアが全然相関してくれない
- 「事故」が絶対起きないように最初から花を 要塞 で囲ってしまうのはどうか？
- 手動で要塞を構築してみたところ、かえってスコアが悪化するケースが発生したため、断念
- 無理やり構築した要塞は無駄が多いみたいで、探索中に自然に発生するもののほうが良い可能性が高い
やったこと
盤面を複数構成→一番良いものを選ぶ→局所改善、という流れでやった。
盤面の構成
まず、盤面の中央を貫通し、左右を分断するような長いパスを構成できるならする。このパスは高確率で最初の方に訪れるが、このパスを見たあとだと冒険者に「今左側にいて、目的地が右側なら、とりあえずこのパスに到達する必要がある」と思わせることができるので、多分単に真ん中に壁を置くとかよりも無駄な移動を減らせる。さらに、パスの両端からさらに長いパスを伸ばせるなら伸ばす。
次に、花の周りに木を置いて、なるべく花が見つかりにくいようにする。これは、花を目指していないのに花を見てしまうリスクを減らすための対策である（後述）。
最後に、盤面全体が連結である限り、なるべくたくさん木を置く。このとき、毎回連結判定に
局所改善
盤面の一部を（最初の状態で木がない場所については）空にして、盤面の構成プロセスをやり直すと、局所的に違う新しい盤面が得られる。
盤面の評価
テスターと全く同じ方法でスコアを計算するということをランダムな
ただし、これだとかなり時間がかかるので、苦肉の策として「盤面が左右に分かれているときは、左側（右側）の更新に対しては右側（左側）は無視する」ということをやった。これで更新回数が増えて、少しスコアが伸びた。
その他の改善
目的地が花になってしまうともうどうしようもないが、花を目指しているわけでもないのに途中で花を見てしまうのは最悪である（コンテスト中、これを「事故」と呼んでいた）。先の構成だと、盤面評価に比べて盤面の構成は圧倒的に速いので、事故が起きない盤面が構成できるならば事故が起きる盤面の評価はスキップして捨てる、などの対策をとった。
例えば下の図において、スタート地点から花までのパスは黒線で示した通りだが、花に至るまでに（紫で囲って示したとおり）花の周囲の木をすべて観測することになる。すると、花に向かうのが（花が目的地の場合はともかく）最短路ではないことが確定するため、「事故」は起きない。
盤面の構成時に↓のような構造を入れると、行き止まりのマスはそこに行こうと思わない限り見ずに済む 可能性が高い ので、お得である。理想的には、行き止まりマスが花より先に目的地として選ばれるときに目的地となるので、1/2 の確率で選ばれることになる。
.#.
#.#
#..
.#.
もっというと、↓のように階段をもう 1 段伸ばしてあげると、行き止まりの隣のマスも同様の理由で 1/3 くらいの確率で選ばれるかもしれない。特に、これは↑のパターンに 1 マス付け加えるだけなので、お得である。実際これでちょっとスコアが上がった。
.#..
#.#.
#..#
.#..
Discussion