参加記
はじめに
今回は、自主制約を極力排除した方針を考えることを目標にして取り組みます
前回の長期AHCの反省を活かして、1ページ目に入れるように頑張ります
問題
NxNマスのグリッド上の (0, N//2) を開始地点として、ランダムな1マスに花が植えられている
迷路を動的に生成して、できるだけ花へ辿り着かないようにする
考察
いつものdiscordメモです
乱択解法
考察の参考にするため、いつも通りChatGPTに簡単な解を書いてもらいます
まず、花の3方を木で塞ぎます
その後、冒険者の4方の未確認マスにランダムに木を置きます
ただし、開始位置と現在位置から花へ到達できない場合は木の設置を乱択し直します
目的地へ向かう関係上、思ったよりも勝手に行き来してくれそうです
木の置き方によって到達不可能なマスがあると、もったないため3x3の連結判定などで塞がないようにした方が良さそうです
また、木を遠くに置くと間が全て空マスだと判明してしまうので、あまり嬉しくなさそうです
冒険者の動きに合わせて、適応的に迷路を作ることが肝になりますね
初日0:20の順位表です
まだまだ伸びるとは思いますが、現時点でも8倍の差があるのはびっくりです
斜め移動方針
斜めに経路を作れば視界も広がらず、良さそうだなーと考えました
実際には、既存の木が邪魔でそのまま構築はできず実装は諦めました
ただ、直線よりはこういった形の方が良さそうな動きは見えたので後で何かに使えるかもしれません
オフライン焼きなまし
全然良い解法が思いつかないため、良い迷路の形をチートして見てみることにしました
ローカルの入力には、目的地の順もあるためこれを使って正確なシミュレートを行うことができます
マップ全体に対して、木を置くか置かないかを焼きなましによって最適化します
前回の解を利用できるようにして、60秒焼きなましを何度も行いました
流石にオンライン実行でこれほどのスコアは出ないと思われます
見つけた良さそうな方針をメモしていきます
斜め移動
冒険者に与える情報を最小限にできる
花への経路が奥まっている
花の座標が目的地に選ばれた時しか、訪れないような迷路が構築できていると良さそう
木で囲われた小規模な領域
この状況が作れると、周りの木全てを確認済みにして周る必要があるため、かなり時間稼ぎになります
広い面積を囲ってしまうと、一度確認しきったらその分目的地がスキップされてしまうため、小さい面積のみが良さそうです
現在値から４方向へ木を配置する貪欲
冒険者目線で結局影響があるのは、現在値から４方向に木があるかどうかなためこれを評価値貪欲で決定していくことにします
花へ到達しにくくするため、以下のような障害を設けることにします
左右反転+回転4方向の計8パターン試して置けそうな配置のうち、開始位置から遠くなるような置き方を選びました
木の配置は、現在地から４方向に距離５までの範囲の総組み合わせを試して、以下のような評価をしました
- 木の配置数が多いと減点
- 現在値中心に7x7範囲に、2x2の空マスがあれば減点
- 花を囲う木の周りへの木の設置は減点
- 次のターンで増える確認済みマス数減点
- 現在地からゴールまでの距離が遠いほど加点
貪欲にしては悪くない動きをしているように見えます
提出すると、得点 296,742 を得て暫定30位になりました
相対スコアは約52Gなため、あと2倍程度スコアが伸びるようです
ざっくりの方針として、オンラインで木の配置を決めていくのは間違っていないような気がします
2分岐解法
現状の解法を見ていると、まっすぐ斜めに進んで壁に当たると脇道を生成しつつ、再度ななめに進むような形しかつくれないことに気付きました
開始地点から1直線に進むと、その道は二度と戻ることは無いのでもったいないような気がします
道の端を分岐点にして、必要な時に分岐を作るようにしてみます
作り方はdfsで生成した全経路について適当に評価して、良さそうな経路をまず1本選びます
2本目も同様の考え方で、1つ目の経路の根から順に作ろうとしてみます
実装してみると、あまりスコアが出ませんでした
分岐ポイントに到達する毎に分岐させていく解法だと、冒険者が行きたい方向へ動けてしまう。というのがありそうです
いいタイミングで通行止めにして歩いてきた道を戻らせるようにしたいです
4隅後回し戦略
あまり良い考えが浮かばず、悩み続けて気付いたら週末になっていました
大体100位前後でこんなにも何もわからない回は久しぶりです
改めて、オフライン焼きなましのビジュアライザを眺めていると気付いたことがありました
中央付近を蛇行させておいて、4隅に未確認マスを残しておけば行ったり来たりの距離を稼げるのではないか。と思いました
良い構築を考えてみますが、あまりに難しい
思いつかなかったため、焼いてみることにします
以外にも、それっぽい形ができました
が、スコアは微妙でした...検討からズレているとしか思えません
領域2分方針
4隅残しでなく、全体を横断するような経路を作ってしまえば、それらを行き来するにはその経路を通るしかない。という状況を作れそうです
それを再帰的に構築すれば、目的地間の距離を稼げそうです
と思っていましたが、既存の木が邪魔で上手く構築できず諦めました
パラメータ最適化
日曜日まで何も思いつけなかったため、元の貪欲を仕方なく詰めることにしました
評価値全てに係数を設けて、これらをoptunaで最適化しました
pahcerの使用で驚くほど簡単に実行することができました（terryさんありがとうございます！
パラメータ調整のみで、10~20%程スコアが上がったと思います
最後に、3000ケースでのACと最悪パターンの確認をして終了しました
最終スコア
seed=0000, score= 700
seed=0001, score=1,925
seed=0002, score= 190
seed=0003, score=5,656
seed=0004, score=3,762
seed=0005, score=8,434
seed=0006, score= 740
seed=0007, score=2,591
seed=0008, score=5,511
seed=0009, score=2,432
seed=0010, score=3,408
終わりに
ここまで何も分からない長期コンは久々でした...
帰って来た情報を全く活かすことができずに終えてしまったので、上位解法を見て復習したいと思います
