资源描述：
《Gaming is a hard job， but someone has to do it!.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Gamingisahardjob,butsomeonehastodoit!GiovanniVigliettaUniversityofPisa,Italy,viglietta@gmail.comAbstract.Weestablishsomegeneralschemesrelatingthecomputa-tionalcomplexityofavideogametothepresenceofcertaincommonele-mentsormechanics,suchasdestroyablepaths,collectingitems,doorsac-t
2、ivatedbyswitchesorpressureplates,etc..Thenweapplysuchmetathe-orems"toseveralvideogamespublishedbetween1980and1998,includ-ingPac-Man,Tron,LodeRunner,BoulderDash,De
ektor,Mindbender,PipeMania,Skweek,PrinceofPersia,Lemmings,Doom,PuzzleBob-ble3,andStarcraft.Weobtainbothnewresults,
3、andimprovementsoralternativeproofsofpreviouslyknownresults.1IntroductionThisworkwasinspiredmainlybytherecentpapersonthecomputationalcomplexityofvideogamesbyForisek[4]andCormode[2],alongwiththeexcellentsurveysonthetopicbyKendalletal.[6]andDemaineetal.[3],andmayberegardedastheir
4、continuationonthesamelineofresearch.Ourpurposeistosingleoutcertainrecurringfeaturesormechanicsinavideogamethatenablegeneralreductionschemesfromknownhardproblemstothegamesweareconsidering.Tothisend,inSection2wepro-duceseveralmetatheoremsthatwillbeappliedinSection3toawealthoffamo
5、uscommercialvideogames,inordertoautomaticallyestablishtheirhardnesswithrespecttocertaincomputationalcomplexityclasses(withacoupleofexceptions).BecausemostrecentcommercialgamesincorporateTuring-equivalentscriptinglanguagesthateasilyallowtode-signundecidablepuzzlesaspartofthegame
6、play,wewillfocusprimarilyarXiv:1201.4995v1[cs.GT]24Jan2012onolder,scriptless"games.Ourselectionincludesgamespublishedbe-tween1980and1998,presentedinalphabeticalorderforbetterreference.Duetospacelimitations,noteverygameisproperlyintroduced,butourconstructionsshouldbepromptlyund
7、erstoodbyanycasualplayer.Severalopenproblemsremain:Wheneveronlythehardnessofagameisprovedwithrespecttosomecomplexityclass,theobviouslyimpliedquestioniswhetherthegameisalsocompleteforthatclass.Di erentvariantsofeachgamemaybestudied,obtainedforinstancebyfurtherrestrictingthesetof
8、gameelementsusedinourhardnessproofs.Thereaderisassumed
