審判込みの一般化詰将棋問題を考えよう その⑥
文献パート
前回
uso-800-plus-alpha.hatenablog.com
そのうちちゃんと書くとしたら、ちゃんとしたリファレンスを書きます。
(ちゃんとしたものを書くとは言っていない)
今回EXPTIME論文と呼んでいたもの
横田 雅也ほか「一般化詰将棋問題の指数時間完全性」『電子情報通信学会論文誌』2001, D-1.
変数操作パーツや交差パーツなどは、多少の補正を除いてほぼそのまま。
の元ネタ
Stockmeyer, L. J and Chandra, A. K, "Provably difficult combinatorial games," SIAM. J. Comput., vol.8, no.2, 1979.
~のゲームを定義し、それらのEXPTIME完全性を証明していく論文。将棋や詰将棋には、その中のが用いられた。
の元ネタ
Robson, J, "Combinatorial games with exponential space complete decision problems," Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. 176, 1984.
上記論文のに no-repetition rule を入れたや、より複雑なルールを入れたの計算複雑性を議論している。については、
In fact such reduction would exist using the already published reductions to , , chess and checkers except for one minor snag: the original reduction from to produces multiple configurations for one at . However this problem is easily removed (...), establishing exponential space completeness for , , chess' and checkers'.
らしいので、使っても大丈夫と判断。
というか、今回の構成は「1ターンに1変数しか変更できない」というルールをフル活用した構成になっているので、「いくつでもいいよ」な他のルールじゃないといけないとなるとツラい。
連続王手の千日手と禁手に関する議論と、単純打歩・完全打歩に関する議論がそれぞれあると思うが、今回は深入りしない。
その他コメント