著者

江藤 宏 木谷 裕紀 小野 廣隆

雑誌

ゲームプログラミングワークショップ2021論文集

巻号頁・発行日

vol.2021, pp.130-137, 2021-11-06

---

本研究では一般化ぷよぷよの計算複雑度について考える.対象とするのは盤面サイズ,色数に関して一般化した,オフライン型パズルとしてのぷよぷよである.本研究ではこの一般化ぷよぷよにおける 2つの問題を取り上げる.1 つは全消し判定であり,もう一つは連鎖数最大化である.前者に関してはぷよ 2色(おじゃまぷよあり)の設定であっても NP 完全であることが,後者に関してはぷよ 4 色(おじゃまぷよあり)の設定でも NP 困難であることが示されている.特に後者に関しては,詳細な証明は公開されていないがぷよ 3 色(おじゃまぷよあり)の設定で,あるいはぷよ 5 色(おじゃまぷよなし)でも NP 困難であることが指摘されている.本研究ではこれらの結果をいくつかの側面から強化する.我々の結果は以下のとおりである: (1) 連鎖数最大化はぷよ 3 色(おじゃまぷよなし)でも NP 困難,(2) P≠NP の仮定の下で, ぷよ 4 色(おじゃまぷよあり)の連鎖数最大化に対しては近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズムは存在しない, (3) 全消し判定はぷよ 4 色(おじゃまぷよなし)でも NP 完全である.