😎
AHC002に探索アルゴリズムを色々適用してみる
ゲームAIやヒューリスティクスの勉強のため、AHCの過去問を解いてみている
AtCoder Heuristic Contest 002
ランダム
可能な移動先の中からランダムに移動先を選ぶ
貪欲法
可能な移動先のうち、最大の得点を持つマスに移動する
ビームサーチ
ゲーム木の各深さにおいて上位k個（ビーム幅）の盤面のみをさらに展開する。決められた深さまで到達したらその深さで最大の得点を持つ盤面を選び、その盤面に至る最初の移動先に移動する
chokudaiサーチ
幅の狭いビームサーチを複数回実行することで多様性を保った探索を行う
動的計画法
各マスについて最高点を保持しておいて新たにそのマスに到達した時に最高点を上回っているなら更新する。適当に枝刈りもする。こちらに書かれていた解法。
100個のサンプル入力に対するスコアの分布をカーネル密度推定してプロットした。貪欲法ではランダムよりわずかに良くなる程度だが、ビームサーチやchokudaiサーチでは明確にスコアが向上する。ビーム幅や探索の深さを振ることでもう少し向上しそうではある。
使用したコード
ビームサーチとchokudaiサーチの実装についてはthunderさんの本を参考にした。
Discussion