審判込みの一般化詰将棋問題を考えよう その⑥

文献パート

 

前回

uso-800-plus-alpha.hatenablog.com

 

 

そのうちちゃんと書くとしたら、ちゃんとしたリファレンスを書きます。

(ちゃんとしたものを書くとは言っていない)

 

今回EXPTIME論文と呼んでいたもの

横田 雅也ほか「一般化詰将棋問題の指数時間完全性」『電子情報通信学会論文誌』2001, D-1.

変数操作パーツや交差パーツなどは、多少の補正を除いてほぼそのまま。

 

G_3の元ネタ

Stockmeyer, L. J and Chandra, A. K, "Provably difficult combinatorial games," SIAM. J. Comput., vol.8, no.2, 1979.

G_1G_6のゲームを定義し、それらのEXPTIME完全性を証明していく論文。将棋や詰将棋には、その中のG_3が用いられた。

 

 G_3'の元ネタ

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.

上記論文のG_1に no-repetition rule を入れたG_1'や、より複雑なルールを入れたG_1^*の計算複雑性を議論している。G_3'については、

In fact such reduction would exist using the already published reductions to G_2, G_3, chess and checkers except for one minor snag: the original reduction from G_1 to G_2 produces multiple G_2 configurations for one at G_1. However this problem is easily removed (...), establishing exponential space completeness for G_2', G_3', chess' and checkers'.

らしいので、使っても大丈夫と判断。

というか、今回の構成は「1ターンに1変数しか変更できない」というルールをフル活用した構成になっているので、「いくつでもいいよ」な他のルールじゃないといけないとなるとツラい。 

 

最後の審判詰将棋作品)

詰将棋作品?『最後の審判』 (Koji Nuida)

連続王手の千日手と禁手に関する議論と、単純打歩・完全打歩に関する議論がそれぞれあると思うが、今回は深入りしない。

 

その他コメント

uso-800-plus-alpha.hatenablog.com