組合せゲーム・パズル ミニプロジェクト 第2回ミニ研究集会 2007/03/16に豊橋技術科学大学だそうで. Rogue脱出判定問題のPSPACE完全性:新井滋、武永康彦(電気通信大学) Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかという問題が、空腹度のパラメータを設定した場合PSPACE完全であることを示す。 へぇー( ´・∀・`) Rogueの脱出判定問題:武永康彦(電気通信大学) Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかというパズルがデュードニーの「コンピュータレクリエーション」で紹介されているが、その一般化がNP完全であることを証明する。 空