著者

松金 輝久 武永 康彦

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.89, no.3, pp.405-413, 2006-03-01

参考文献数

8

被引用文献数

3

---

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

著者

松金 輝久 武永 康彦

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1426, pp.147-152, 2005-04

著者

松金 輝久 武永 康彦

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.743, pp.95-103, 2005-03-11

参考文献数

7

被引用文献数

1

---

計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題のNP完全性を3-PARTITIONからの帰着によって示す。

著者

松金 輝久 武永 康彦

出版者

京都大学

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1426, pp.147-152, 2005-04

著者

松金 輝久 武永 康彦

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J89-D, no.3, pp.405-413, 2006-03-01

---

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

著者

中井 健一朗 武永 康彦

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1799, pp.183-186, 2012-06

著者

岩田 茂樹 武永 康彦 笠井 琢美 伊藤 大雄

出版者

電気通信大学

雑誌

基盤研究(C)

巻号頁・発行日

2011

---

本研究は、ゲーム情報学全般にわたる研究のうち、(1) And-Or 木のコンピュータによる探索、と (2) ゲームやパズルの複雑さに関する研究を行う、ことを目的とする。And-Or 木(ゲーム木)のコンピュータによる探索では通常、評価関数が用いられる。ゲーム木の自然なモデルを定め、ゲーム木のある深さにおいて深さ優先探索により探索する局面数を考える。完全な評価関数に確率 p(0<p<1) で近い評価関数を用いたときは、完全な評価関数と比べて、ゲーム木の深さの多項式倍の数の局面数を探索することを示した。ゲームやパズルの複雑さの研究では、いくつかのゲーム・パズルの計算複雑さを明らかにした。