著者
松金 輝久 武永 康彦
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)
巻号頁・発行日
vol.89, no.3, pp.405-413, 2006-03-01
参考文献数
8
被引用文献数
3

ゲームやパズルの計算量や解法に関する研究は古くから行われている.特に最近ではテトリスのようなゲームが注目を集めている.本論文では,対戦型ゲームとして広く知られるぷよぷよを,人力として初期盤面と落下してくるピース列が与えられ,ピースを落下させることにより特定の目的を達成するパズルゲームとして定式化し,その連鎖数判定問題を考える.連鎖はぷよぷよにおける特徴的な性質であり,最大の連鎖を発生させる連鎖数判定問題がNP完全であることを証明する.
著者
松金 輝久 武永 康彦
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
巻号頁・発行日
vol.104, no.743, pp.95-103, 2005-03-11
参考文献数
7
被引用文献数
1

計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題のNP完全性を3-PARTITIONからの帰着によって示す。
著者
松金 輝久 武永 康彦
出版者
The Institute of Electronics, Information and Communication Engineers
雑誌
電子情報通信学会論文誌 D (ISSN:18804535)
巻号頁・発行日
vol.J89-D, no.3, pp.405-413, 2006-03-01

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