解説
問題
色と内部状態を元に、動くロボットがある
ある色と内部状態の時、あらかじめ決めておいた（遷移規則）塗り替える色・次の状態・移動方向 の行動を行う
決められたターン以内に、全ての目的地を順に訪問する問題
スコアは、色数と内部状態数の合計が小さい程よい
解法概要
目的地を後ろから見て、使う経路と適用する遷移規則を差分更新型のビームサーチによって決めます
ビジュアライザ
後ろから貪欲
詳しくは他の人が書いてくれることを期待して、自分の方法を書きます
色c、内部状態qの時適用される規則を、次の色nc、次の内部状態nq、移動方向dir
(c, q) => (nc, nq, dir) と表すとします
経路を固定して後ろから考えると、nc, nq, dir は自動的に決まるため、そのような遷移規則が既にあるか調べることで再利用ができます
ない場合でも、c, q は未使用の内から自由に選んで新たに作ることができます
後ろから決めると、スタート地点の色や状態がおかしなことになりますが、スタート地点の数字が(0, 0)になるように出力値に対してmodを取ればよいです
ビームサーチの遷移
ビームサーチライブラリは、thunderさんのものをNimに書き換えて使っています
差分更新ビームサーチライブラリをテンプレートメタプログラミングでつくってみた #AtCoder - Qiita
目的地の最後から、Tを超えない範囲で1マスは移動できる方向への遷移を検討します
既存の遷移規則を再利用すれば良い場合は、必ず採用します
ない場合は、(c, q) を1つずつ増やしたリストの先頭から5つまで次の候補へ追加します
(0, 0) (1, 0) (0, 1) (1, 1) (2, 0) (2, 1) (0, 2) (1, 2) (2, 2) のような増やし方でリストを作りました
その場停止や、壁に当たって止まるような移動は一切しません
（処理の書き分けが面倒なのと、遷移先を絞るために使っていません
ターン数は、min(1.5X, X+5000)ターンまでとしました
ビーム幅がそれほど大きくないため、大きな迂回路が採用できないためです
ビーム幅はseed=0では1500程度でした
評価関数
以下の評価値をoptunaで最適化後、手でキリよくした重みで足し合わせています
主に効いているものを太字にしています
- 色の種類数、内部状態の種類数
- 割当済みの遷移規則数
- 当初のX/Tに対する現在のオーバー量
- 色の変更回数、状態の変更回数
- 隣接色が同一である個数
- 同方向へ進んだ回数 － 反転方向へ進んだ回数
- 目的地到達回数
- 残り迂回可能距離
- 2ターン前と同じマスを踏んだフラグ
- 遷移規則の出力が既存と被っているフラグ
盤面の重複削除
ZobristHashで重複盤面の削除をしています
- これまで通ったマス集合
- 今のマスの色、状態
- 目的地達成回数
- 残り迂回可能距離 div 4
細かい工夫
既存の遷移規則を検索する際に、(c, q)を全探索していると遅いので逆引き用の配列を作りました
revList[nq][dir] = seq[(nc, c, q)] として、現在の状態と移動方向の添え字でアクセスできるようにしていました
nc がキーでなく値にいるのは、初期盤面を自由色-1としているからですがどうやら不要だったようです...
自由色の更新がなければ、revRule[nc][nq][dir]のように一発アクセスできるので、こちらの方が絶対いいです
提出コード
Nimです
参加記
はじめに
久々な長期コンな気がします
少し競プロから離れていたため、Nimを書くのも1カ月ぶりくらいでしょうか
できるだけ時間の都合をつけて1ページ目順位目指して頑張ります！
最初の考察
遷移という文字を見つけて、また確率か！？と身構えましたがそんなことは無かったです
色・状態・方向と定義が色々あって問題理解がやや難しいですが、AIに要約してもらって一旦理解は出来ました
色を1色のみとすると、内部状態をどんどん進めていけば任意の方向へ行動できる
色と内部状態の組み合わせによって遷移規則が作られるため、表現できるのは色と内部状態の種類の積
評価されるのは、色と内部状態の種類の和なため同じ種類数用意するのが良さそう
特徴的なseedは、seed=2が小さく、seed=3が大きめ、seed=19は更に大きめといった感じ
壁の有無はseedでかなり差があり、全く壁のない場合もあれば1マス幅でしか通れない場合もある
場所・色・内部状態が同一になると無限ループになってしまうので避ける
→嘘でした
経路を最初に決めて、遷移を最適化するとか？
同じマスを何度も通ると、状態を増やし続ける必要があるので嬉しく無さそう
同じマスを通らないように最短経路+αを構築するとか
グリッド2次元x色x内部状態の4次元のグリッド空間を、干渉しないように動くイメージが浮かぶ
3次元に落としてみると、子供のジャングルジムみたいな
経路さえ決まれば、逆向きに貪欲できそう
逆走査貪欲解法
目的地順に適当にbfsをして最短経路を見つけます
経路を逆に辿りつつ、各マスを次どの色にすべきか、と今の内部状態を持って順番に決めていきます
これまでの遷移規則で再利用できるものは再利用したり、色をまだ確定させなくてよい場合、などを実装して提出すると40位程度
最初は(0, 0)でないといけないのに、そうでない場合が発生してしまう重大なバグを取り除くと、初日の26時で暫定4位になれました！
改善検討
経路に被りが少ない方が、状態を増やさずに済みそうなため試してみます
目的地間の経路を一つ選び、最短経路内という制約内で他の経路と被りの少ない経路を選びなおす乱択を1000回実施して貪欲をしました
スコアが1,2改善するケースもありましたが、悪化する場合もありました
逆に、被りの多い経路を選ぶように乱択すると、ほとんどの場合悪化しましたが良くなる場合もありました
経路のみを最適化するのは、現時点では難しそうです
ビジュアライザからヒントが得られないか考えてみます
右のヒートマップを見ると色の薄い箇所(使用回数が1回)がかなり多くあります
状態を使いまわせていないのが問題なようです
後ろから決めている関係上、序盤に特殊な状態を作る必要があるのも問題です
手で最適化できそうな盤面(seed=93)を持ってきました
色々試して、ちょっとだけ良い動きのパターンが見えました
９、１２へ向かう線では、１２へ向かう途中で９へ曲がっていきます
これは問題ない動きで、曲がった後に１２へ向かう色を揃えることが出来るためです
直線に動いて、曲がりたい時は、曲がりたい場所の色が異なるor1マス手前で状態を変更しておく必要があり嬉しくなさそうです
他にもなんとなく傾向はありそうですが、全て言語化するのは難しそうです
経路乱択
良い解法が思い浮かばないので、一旦今の解を改良してみます
実行時間6ms程度のコードなので、経路を適当に引き直して貪欲を行い最も良いスコアの解を出力することにします
各seedで1,2の改善は見られたので、経路最適化による効果はあるがかなり微小
遷移規則の決め方などの方を根本的に見直さないと、まともにスコアを改善するのは難しそう
新しく採用する遷移規則を乱択する方がややスコアが伸びました
このことからも、改善すべきは遷移規則の決め方っぽい気がします
実装大変だがビームサーチを書くべきか、、、悩む
壁当たり操作追加
問題文にあった、壁方向へ移動すると停止するが色や状態は変化する。という処理を使ってみることにします
後ろからの貪欲なため、壁へ当たってから移動してくる。ような操作になります
この機能を追加するだけなのに、かなりバグらせて大変な思いをしました
悲しいことに、実装しきってもほぼスコアは変わりませんでした、、、
ビームサーチ実装
重い腰を上げてビームサーチを実装してみます
スマートなデータの持ち方は後にして、とにかくバグらせないように気を付けます
実装しきると、一応動いていましたが元の貪欲よりスコアがやや悪いです
ChatGPTに聞いて、評価関数にC+Qだけでなく割り当て済みの遷移の数も加えると10%程スコアが改善しました
ビームサーチにしただけで、スコアが改善するとはあまり思っていなかったので驚きました
提出すると、火曜日夜時点で35Gの24位となりました
この方針を詰めていけば良さそうな兆しが見えたので、沈みかけていたやる気が復活してきました
伸び悩み
ビームサーチのハッシュ方法や評価関数を調整したりしましたが、いまいちスコアが伸びません
何より、ビーム幅や時間を伸ばしても大して効果がないので高速化しても無意味そうなのが厳しい感じがします
木曜日夜の時点で30位なのは悪くはないですが、このままだと50位も怪しいです
根本から何か違うような気がしてきました
盤面の小さいケースは割と最適な気がしているので、N=10~14のみの提出をしてみます
17ケースACで相対スコア12.6Gでした
これは、元の50ケースのスコアと大差ありません
全てに共通した改善事項(本質)があり、自分はまだ見つけられていないようです
壁当たり移動
処理の書きやすさから、移動する行動のみを候補としていました
が、候補手は全て試した方が良さそうに思えたため実装してみます
メチャクチャバグらせて、一旦諦めて、やっぱり修正してというのを2,3日繰り返してなんとか実装しました
原因は、方向の反転をk^2で行っていたのですが、壁に当たる時は反転してはいけないのをずっと見逃していました
苦労して壁停止処理を導入しましたが、大体のケースでスコアが落ちる結果でした
明らかにビーム幅が取れなくなってしまったので、選択肢の広さが仇になったようです
評価関数見直し
ChatGPTと壁打ちしながらとにかく色々試すことにしました
過去のビムサ回のXを見返したりして、評価関数を増やしていきます
上手くいかなかった項目もありましたが（経路dpで求めた通過期待値を重みに使う、盤面全体の色合計値）、効いていそうな項目も見つけることが出来ました
連続した進行方向や、隣接色の関係などは良さそうな感じです
他にも、遷移規則の類似度を評価してみたり、重みをoptunaで最適化してみたりと微妙な改善で最終日まで1ページ目に残ることは出来ました
最終チェック
長期コンのシステスでACをあまり取れていないので、今回はしっかりチェックします
3000ケース回して、異常がありそうなケースに対応していきます
まず、実行時間が異様に早いケースがいくつかありました
これは、盤面のハッシュ化が甘すぎて小さいケースにおいて、ビーム幅があまり広がっていないようでした
重複削除を緩めつつ、大きな盤面での多様性維持のバランスを見ながら修正しました
次に、実行が終わらず無限ループするケースがありました
ビームサーチライブラリの不具合をChatGPTと一緒に追いましたが、見つからず。結構な時間をかけて突き止めたのですが、ビーム幅が自作のハッシュテーブル幅を超える場合に無限ループが発生していました
ビーム幅の最大に合わせてハッシュテーブルを設定すべきですが、大きくし過ぎてもデータの初期化に時間がかかるため、ビーム幅を最大30000程度に落とすことにしました
小さな盤面での最適解が見つからなくなる恐れがありますが、今回は大丈夫なようでした
他にも小さな高速化をして今回のAHCを終えました
暫定順位表
システスで上振れるか、下振れるかドキドキです
終わりに
最上位解法ではないだろうなと思いつつ取り組んでいましたが、氷の床のような発想は実現すると思っていなかったので驚きでした
それでも、同じような解法の中では割と詰めれた方だと思うので満足度は高いです
今回の結果で順位が10上がって65位になりました
50位が一つの目標なのでひとまずそこまでは頑張りたいです
