Rogue 脱出判定問題の PSPACE完全性 新井滋、武永康彦 （電通大） Rogueについて 1980年ごろに製作されたダンジョン探索型の 1人用コンピュータRPG 地下迷宮の奥深くにある宝を取って脱出す ることが目的 画面上のキャラクターやアイテム、通路、部 屋など全てテキスト文字で表される ローグの一般的なルール プレイヤーと魔物は交互に行 動する 行動とは ・上下左右と斜めの8方向に 移動する ・移動せずその場に留まる ・攻撃、など ローグの一般的なルール 起きている魔物はプレイヤーに近づく方向に移動 最も近づく方向に移動不可能なら、その 両側のいずれかに移動 プレイヤーは以下の場合死亡 ・攻撃を受け体力がなくなる ・空腹で餓死 Rogue脱出判定問題 入力：初期盤面、手数（１進表記） 問題：与えられた盤面において、プレイヤーが必ず 階段から脱出できるか プレイヤー 起きている魔物 寝ている魔物 階段 Rogue脱出判定問題 部屋はひとつのみで通路はない 階段は1個 寝ている魔物は攻撃しない限り起きない 魔物が寝ているかどうかは区別できる プレイヤーの性質 プレイヤーからは攻撃できず、魔物から一度でも 攻撃を受けた時点で死亡 （体力が限界にきている） 満腹度が減りすぎると餓死する 手数制限（ｔ 手以内）にあたる 規定手数以内に脱出できない場合は餓死 Rogue脱出判定問題 定理 Rogue脱出判定問題はPSPACE完全である。 証明 PSPACEへの所属性 盤面の変化を示す木を探索 必要な領域は盤面のサイズと手数の多項式 PSPACE困難性の証明 Generalized Geographyから帰着 2人のプレイヤーが開始頂点からスタートして、 有向グラフの辺を交互に辿る 既に訪れた頂点を再度訪問すると負け 先手必勝か？ ・グラフが二部グラフで、 （入次数、出次数）＝（１，１）、（１，２）、（２，１） に制限されている場合でもPSPACE完全 盤面の設計 頂点集合VA、VE VA：プレイヤーが再度訪れると死亡 出次数２のとき、魔物の移動方向により プレイヤーの進行方向が決まる VE：プレイヤーが再度訪れると脱出できる 出次数２のとき、プレイヤーが進路を選択 開始頂点はVE 通路 ・・・ 辺に対応 寝ている魔物を並べて通路を作る 盤面全体の構造 グラフを多項式時間でグリッド上に平面埋め込み可能 頂点部品と同じｘ、ｙ座標上に他の頂点部品、 および通路の折れ曲がりが存在しないように配置 VEの各頂点からは階段への道が存在 階段 VE VA VA 交差点 VE 頂点部品 VA（入次数２、出次数１） 入口→ 入口→ →出口 頂点部品 VA（入次数２、出次数１） 初期配置において プレイヤーの後ろに魔物 →後退、停止できない 頂点部品 VA（入次数２、出次数１） 1回目は通過可能 頂点部品 VA（入次数２、出次数１） 外を通っている限り 魔物は脱出しない 頂点部品 VA（入次数２、出次数１） 2回目は通過不可能 × 頂点部品 VA（入次数２、出次数１） 出口から進入不可能 × × 頂点部品 VE（入次数２、出次数１） 頂点部品 通過すると魔物が ロックされる VE（入次数２、出次数１） 頂点部品 VE（入次数２、出次数１） ２回目の通過 頂点部品 VA（出次数２） 分岐部 頂点部品 VA(出次数２）分岐部 ↓ → ↓ 頂点部品 VA(出次数２）部分図 ↓ → ↓ 交差点の部品 通 路 右から進入の時のみ 魔物がロックされる 至階段← ← 交差点の部品 通 路 魔物は ロックされない 至階段← ↑ おわりに Rogue脱出判定問題のPSPACE完全性を証明 考察 ・アイテム、飛び道具など ほとんどのものは使用できてもPSPACE完全 ・歩数制限がない場合 ・・・ EXPTIME完全？ ・歩数制限なし、魔物の行動が一意に定まる場合 ・・・ PSPACE完全？
© Copyright 2024 ExpyDoc
