組合せ最適化問題としてのぷよぷよの連鎖数判定問題

摘要

ゲームやパズルの計算量や解法に関する研究は古くから行われている．特に最近ではテトリスのよrnうなゲームが注目を集めている．本論文では，対戦型ゲームとして広く知られるぷよぷよを，入力として初期盤rn面と落下してくるピース列が与えられ，ピースを落下させることにより特定の目的を達成するパズルゲームとしrnて定式化し，その連鎖数判定問題を考える．連鎖はぷよぷよにおける特徴的な性質であり，最大の連鎖を発生さrnせる連鎖数判定問題がNP完全であることを証明する．