- 著者
-
安達 博行
亀川 裕之
岩田 茂樹
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 D (ISSN:09135713)
- 巻号頁・発行日
- vol.J70-D, no.10, pp.1843-1852, 1987-10-25
将棋の盤面を縦横9マスから縦横nマスに一般化したとき,与えられた局面から先手が勝てるかどうかを決定する問題は指数時間完成であることを示す.すなわち一般化将棋の先手必勝問題を解くどのアルゴリズムも少なくともnの指数時間を必要とし,この問題は「手に負えない」問題であることを証明する.この結果は,すでに指数時間完全であることが知られているG3の先手必勝問題(Stockmeyer, et al., Provably difficult combinatorial games, SIAM J. Comput. 8)から対数領域還元可能であることを示す.G3は与えられた積和形式の論理関数上のゲームである.一般化将棋の構成は各論理変数をシミュレートするための変数部,論理関数の各項に対応する飛車捕獲部,リテラルが項に含まれることに対応する竜角交代部などからなる.