👹

AHC042 に参加しました(66位)

2025/02/03に公開

AHC042 に参加していました。スコアは 466099 で、 66 位を取ることができました。過去最高パフォーマンスが出て感動しました。

seed0, score=3111
seed0, score=3111

コンテスト成績表
コンテスト成績表

自分の行った方針をまとめたいと思います。

解法の概要

2 つの評価関数を基に、 1 ターンごとのビームサーチを行いました。

評価関数

評価関数 1 : 盤面の鬼の位置に関する評価関数

まず、基本的な考えとして、「真ん中の方に鬼がいるのはよろしくない」という発想がありました。外側の鬼だけに注目すると、内側の鬼がひたすら真ん中あたりをグルグルしてしまう可能性を危惧したためです。(これが正しい判断だったかどうかはわかりません)

評価関数としては鬼の座標を (X_i, Y_i) として、以下の式の通りになりました。低い方が良い評価とみなしています。

\sum \min(i+1, j+1, N-i, N-j)

後述するビームサーチを実装して、464638 を達成しました。

seed0, score=3098
seed0, score=3098

評価関数 2 : 鬼の隊列に関する評価関数

評価関数 1 を実装し終えた結果を見て、「1 度に多くの鬼を移動できた方が良い」ことに気づきました(本当はこっちの方が先に浮かぶべき発想だと、これを書いてる時点では思っています)。

これは、seed0 の結果の終盤の行動から発想できました。

そこで、以下のような空間で分けて、評価関数を作りました。このような形にしたのは、鬼をなるべく近い方向の出口と対応させたかったためです。

空間の分割のイメージ(上部分のみ)
空間の分割のイメージ(上部分のみ)

各 I の字を g として、評価関数は以下の通りにしました。高い方が良い評価とみなしています。

\sum \max(| g | - 1, 0)

この評価関数単体ではうまく遷移ができなかったようで、多くのケースで答えを出すことができませんでした。

評価関数の結合

評価関数 1 の値を f_1, 評価関数 2 の値を f_2 として、 F = f_1 - f_2 としました。低い方が良い評価とみなしています。

ビーム幅を調整し 466099 を達成しました。

seed0, score=3111
seed0, score=3111

評価関数 2 の効果も相まって、心なしか鬼同士が揃ってくれている気がしています。

ビームサーチ

上を基にした貪欲法を書いていたのですが、雑に貪欲をしていると詰むケースがあったため、即席でビームサーチをしました。最終的にビーム幅は 88 になりました。

定数倍改善等は全く行っていません。時間いっぱいにビーム幅を増やした時が、既に頭打ちのスコアだったためです。

その他

zobrist hash で盤面のループを回避

unordered_set で過去の盤面情報を全て記録するようにしていました。これによって前の操作と(意味をなさない)逆方向の操作を防いでいました。

今後やりたいこと

延長戦解法については改めて別記事を作りたいと思います。

高速なビームサーチの実装

今回は筋のいいビームサーチを初めて書くことができました。世の中には差分更新をうまく扱うことによって高速なビームサーチを実装されている方がいるらしいので、それをマネて見たいです。

焼きなまし方針の確認

どうして焼けるのかがさっぱりわからないので、上位の方針を読んで理解したいと思います。きっと今後に役立つエッセンスがあると思っています。

公式解説の貪欲

貪欲だけでとんでもないスコアを叩きだしているようなので、公式解説放送をしっかり見て復習したいと思います。

Discussion