| [+] NP & PSPACE Video Games. Base PSPACE-complete problems: QSAT, Schaefer, planar Q3SAT, planar 1-in-3 Q3SAT. Viglietta metatheorems: location traversal, single-use paths, tokens, toll roads, pressure plates, buttons, doors. Applications to video games: Pac Man, FPSs (Doom, Quake, Heretic, Hexen), RPGs (Eye of the Beholder), adventure games (SCUMM), platformers (Prince of Persia, Sonic the Hedgehog, The Lost Vikings, Tomb Raider, Zelda II, Donkey Kong Country 1, 2, 3, Super Mario Bros., Lemmings) | |||||
|
Back to fun hardness of video games! We'll prove a bunch of “metatheorems”: video games with a few basic features are NP-hard or PSPACE-hard. Then we'll apply these metatheorems to prove NP-hardness of Boulderdash, Lode Runner, Zelda II, and Pac Man; and PSPACE-hardness of FPSs (e.g. Doom), RPGs (e.g. Eye of the Beholder), adventure games (e.g. SCUMM), Prince of Persia, Legend of Zelda: A Link to the Past, Donkey Kong Country 1, 2, and 3, and Lemmings. | |||||
In this week's class, we'll briefly revisit Σk from the perspective of 2-player games (mate-in-k), mention the real-valued analogs to NP/PSPACE, and cover the bounded 2-player case of the general theory of gadgets. | |||||
|
Handwritten notes, page 1/4 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/4 • [previous page] • [next page] • [PDF] |
|
|
Slides, page 1/33 •
[previous page] •
[next page] •
[PDF]
http://giovanniviglietta.com/papers/gaming2.pdf Slides, page 1/33 • [previous page] • [next page] • [PDF] |
