一般化ぷよぷよのより強い計算困難性

• Item type: Symposium(1)
• 公開日: 2021-11-06
• タイトル: 一般化ぷよぷよのより強い計算困難性
• タイトル / 言語: en
• タイトル: Stronger Hardness Results on Generalized Puyopuyo
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ぷよぷよ
• キーワード / 主題Scheme: Other
• キーワード / 主題: パズル計算量
• キーワード / 主題Scheme: Other
• キーワード / 主題: NP 完全性
• キーワード / 主題Scheme: Other
• キーワード / 主題: 近似困難
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東北大学大学院情報科学研究科
• 著者所属: 九州大学大学院経済学研究院
• 著者所属: 名古屋大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, Tohoku University
• 著者所属(英): en
• 著者所属(英): Graduate School of Economics, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者名: 江藤, 宏; 木谷, 裕紀; 小野, 廣隆
• 著者名(英): Hiroshi, Eto; Hironori, Kiya; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では一般化ぷよぷよの計算複雑度について考える．対象とするのは盤面サイズ，色数に関して一般化した，オフライン型パズルとしてのぷよぷよである．本研究ではこの一般化ぷよぷよにおける 2つの問題を取り上げる．1 つは全消し判定であり，もう一つは連鎖数最大化である．前者に関してはぷよ 2色（おじゃまぷよあり）の設定であっても NP 完全であることが，後者に関してはぷよ 4 色（おじゃまぷよあり）の設定でも NP 困難であることが示されている．特に後者に関しては，詳細な証明は公開されていないがぷよ 3 色（おじゃまぷよあり）の設定で，あるいはぷよ 5 色（おじゃまぷよなし）でも NP 困難であることが指摘されている．本研究ではこれらの結果をいくつかの側面から強化する．我々の結果は以下のとおりである： (1) 連鎖数最大化はぷよ 3 色（おじゃまぷよなし）でも NP 困難，(2) P≠NP の仮定の下で， ぷよ 4 色（おじゃまぷよあり）の連鎖数最大化に対しては近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズムは存在しない， (3) 全消し判定はぷよ 4 色（おじゃまぷよなし）でも NP 完全である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we investigate the computational complexity of a generalized variant of Puyopuyo. The variant generalizes the size of the board and the number of colors but falling pairs of puyos are given in the offline manner. We focus on two problems of the generalized Puyopuyo; board clearing and maximizing chains. Both problems are already known to be NP-hard. More precisely, the former is NP-complete even for puyos of 2 colors with N-puyo setting, and the latter is NP-hard even for puyos of 4 colors with N-puyo setting. The latter result is mentioned to be improved to the setting of puyos of 3 colors with N-puyo and the setting of puyos of 5 colors without N-puyo, though the detail is not published. In this paper, we strengthen these results from several aspects. Our results are as follows: (1) The chain maximization is NP-hard even for the setting of puyos of 4 colors without N-puyo. (2) The chain maximization for puyos of 3 colors with N-puyo cannot be approximated within any polynomial factor in polynomial time, unless P=NP. (3) The board clearing is NP-complete even for the setting of puyos of 4 colors without N-puyo.
• 書誌情報: ゲームプログラミングワークショップ2021論文集; 巻 2021, p. 130-137, 発行日 2021-11-06
• 出版者 / 言語: ja
• 出版者: 情報処理学会