一般化はさみ将棋のEXPTIME完全性

スポンサーリンク

概要

• 論文の詳細を見る

• はさみ将棋とは、自分の駒を用いて相手の駒をはさんでとる2人対戦型ゼロサムゲームであり、日本のはさみ将棋、タイのMak-yakなどが有名である。本稿では、盤面をn×nに拡張した一般化はさみ将棋の計算複雑さについて考察する。ここでは、縦、横方向に自由に動く駒に加えて、不動駒も使用するものとする。また、縦横方向に加えて斜め方向の取りも許すものとし、相手の駒を先に5個取った方が勝ちとする。このとき、任意に与えられた一般化はさみ将棋の盤面について、勝ち・負け・引き分けのいずれであるかを判定する問題が、EXPTIME完全問題であることを証明する。

• 2009-01-23

著者

• 築地 立家

  東京電機大学理工学研究科

• 方波見 尚之

  東京電機大学理工学研究科

• 築地 立家

  東京電機大学大学院理工学研究科情報学専攻

関連論文

• DNA計算によるAES暗号の解読
• Ninf-G上の分散並列計算システムの開発
• 一般化はさみ将棋のEXPTIME完全性
• 最大次数ΔのC_4フリーグラフの(2Δ-4)彩色数を数え上げるためのマルコフ連鎖モンテカルロ法
• Computing Phylogenetic Roots with Bounded Degrees and Errors is Hard (Evolutionary Advancement in Fundamental Theories of Computer Science)
• A-026 インターネット上の遊休PCを利用した量子探索シミュレータの開発(A分野:モデル・アルゴリズム・プログラミング,一般論文)
• RA-004 振幅を制限した無誤り量子計算について(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)

スポンサーリンク