n×n盤面上の将棋の指数時間完全性について

安達 博行  亀川 裕之  岩田 茂樹  

誌名
電子情報通信学会論文誌 D   Vol.J70-D   No.10   pp.1843-1852
発行日: 1987/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(860.4KB)>>
論文を購入




あらまし: 
将棋の盤面を縦横9マスから縦横nマスに一般化したとき,与えられた局面から先手が勝てるかどうかを決定する問題は指数時間完成であることを示す.すなわち一般化将棋の先手必勝問題を解くどのアルゴリズムも少なくともnの指数時間を必要とし,この問題は「手に負えない」問題であることを証明する.この結果は,すでに指数時間完全であることが知られているG3の先手必勝問題(Stockmeyer, et al., Provably difficult combinatorial games, SIAM J. Comput. 8)から対数領域還元可能であることを示す.G3は与えられた積和形式の論理関数上のゲームである.一般化将棋の構成は各論理変数をシミュレートするための変数部,論理関数の各項に対応する飛車捕獲部,リテラルが項に含まれることに対応する竜角交代部などからなる.