175 0 0 0 組合せ最適化問題としてのぷよぷよの連鎖数判定問題(計算量理論)
- 著者
- 松金 輝久 武永 康彦
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)
- 巻号頁・発行日
- vol.89, no.3, pp.405-413, 2006-03-01
- 参考文献数
- 8
- 被引用文献数
- 3
ゲームやパズルの計算量や解法に関する研究は古くから行われている.特に最近ではテトリスのようなゲームが注目を集めている.本論文では,対戦型ゲームとして広く知られるぷよぷよを,人力として初期盤面と落下してくるピース列が与えられ,ピースを落下させることにより特定の目的を達成するパズルゲームとして定式化し,その連鎖数判定問題を考える.連鎖はぷよぷよにおける特徴的な性質であり,最大の連鎖を発生させる連鎖数判定問題がNP完全であることを証明する.
83 0 0 0 OA 一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用)
- 著者
- 松金 輝久 武永 康彦
- 出版者
- 京都大学数理解析研究所
- 雑誌
- 数理解析研究所講究録 (ISSN:18802818)
- 巻号頁・発行日
- vol.1426, pp.147-152, 2005-04
25 0 0 0 一般化ぷよぷよの連鎖数判定問題
- 著者
- 松金 輝久 武永 康彦
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.104, no.743, pp.95-103, 2005-03-11
- 参考文献数
- 7
- 被引用文献数
- 1
計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題のNP完全性を3-PARTITIONからの帰着によって示す。
18 0 0 0 IR 一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用)
- 著者
- 松金 輝久 武永 康彦
- 出版者
- 京都大学
- 雑誌
- 数理解析研究所講究録 (ISSN:18802818)
- 巻号頁・発行日
- vol.1426, pp.147-152, 2005-04
14 0 0 0 組合せ最適化問題としてのぷよぷよの連鎖数判定問題
- 著者
- 松金 輝久 武永 康彦
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 D (ISSN:18804535)
- 巻号頁・発行日
- vol.J89-D, no.3, pp.405-413, 2006-03-01
ゲームやパズルの計算量や解法に関する研究は古くから行われている.特に最近ではテトリスのようなゲームが注目を集めている.本論文では,対戦型ゲームとして広く知られるぷよぷよを,入力として初期盤面と落下してくるピース列が与えられ,ピースを落下させることにより特定の目的を達成するパズルゲームとして定式化し,その連鎖数判定問題を考える.連鎖はぷよぷよにおける特徴的な性質であり,最大の連鎖を発生させる連鎖数判定問題がNP完全であることを証明する.