Presentation Information
[4Yin-B-53]Optimal Solution Search in "Hexa Away" Using Stage-Decomposition-Based Heuristics
〇Mitsuki Sakamoto1, Kenshi Abe1, nozomu karai1, keisuke niimi1, koya ihara1 (1. CyberAgent)
Keywords:
Search Algorithm,Heuristic Search,Puzzle Games
本研究は，カジュアルパズルゲームHexa Awayにおいて，ステージ制作や自動Quality Assurance (QA)に必要となる「最短手数」を，最適性を保ったまま効率よく算出する手法を提案する．本問題は，盤面配置を状態，操作を遷移とみなす最短経路探索として定式化できる．しかし，入れ替えや爆弾など多様なギミックにより到達可能な盤面数（状態空間）が爆発的に増大するため，単純な全探索では現実的な計算時間内に解を得ることは難しい．A*探索を用いる場合でも，ピースごとの必要手数を足し合わせる素朴な見積もりは，複数のピースに作用する操作（共通操作）を二重に数えて過大評価となり，最短解保証を損ね得る．一方，共通操作を一律に無視すると見積もりが弱くなり探索が効率化されない．そこで本稿では，共通操作の影響を適度に織り込みつつ，過大評価を避ける形でコストを見積もる新しいヒューリスティック（ARROW）を提案する．さらに，先行実行できる操作を探索前に処理する工夫を導入し，探索対象となる状態数を削減する．多数のステージで評価した結果，提案手法は最短解を維持したまま，特に難しい盤面における探索状態数を大きく削減できることを示す．