一般化将棋について知らないことが多いという話
「一般化将棋はEXPTIME完全」だと、つい最近まで全く疑っていなかった訳です。
そう言ってる論文もあるし。
なので、下の記事を見て、
はぇ～･･･まじか･･･
と思いました。
（記事終了）
例えば、こんなWikipediaの記事があって、
囲碁に超コウ（同一局面が現れることを禁止する）を入れた場合の計算複雑性について、
Robson showed that if the superko rule, that is, “no previous position may ever be recreated”, is added to certain two-player games that are EXPTIME-complete, then the new games would be EXPSPACE-complete. Intuitively, this is because an exponential amount of space is required even to determine the legal moves from a position, because the game history leading up to a position could be exponentially long.
と書いてあります。
つまり、当該Wikipedia記事の註にある、
Robsonの"Combinatorial games with exponential space complete decision problems"を読めよ☆ってことです。
その上で、最後の審判を噛ませたシロモノを･･･
誰か作りませんか･･･？（丸投げ）
そういえば、将棋って4回目の同一局面になる手を禁じてる訳ではなくない？
（追記）
Robsonの論文って、私が以前「うーん、パス！ｗ」した、"Provably difficult combinatorial gemes"って論文(Stockmeyer & Chandra 1979)がベースっぽい･･････
勉強はちゃんとしておきましょう･･････
続いた
