Playing games with algorithms Algorithmic combinat

PlayingGameswithAlgorithms:AlgorithmicCombinatorialGameTheory¤ErikD.DemaineyJune10,2001AbstractCombinatorialgamesleadtoseveralinteresting,cleanproblemsinalgorithmsandcomplexitytheory,manyofwhichremainopen.Thepurposeofthispaperistoprovideanoverviewoftheareatoencouragefurtherresearch.Inparticular,webeginwithgeneralbackgroundincombinatorialgametheory,whichanalyzesidealplayinperfect-informationgames.Thenwesurveyresultsaboutthecomplexityofdeterminingidealplayinthesegames,andtherelatedproblemsofsolvingpuzzles,intermsofbothpolynomial-timealgorithmsandcomputationalintractabilityresults.Ourreviewofbackgroundandsurveyofalgorithmicresultsarebynomeanscomplete,butshouldserveasausefulprimer.1IntroductionManyclassicgamesareknowntobecomputationallyintractable:one-playerpuzzlesareoftenNP-complete(asinMinesweeper),andtwo-playergamesareoftenPSPACE-complete(asinOthello)orEXPTIME-complete(asinCheckers,Chess,andGo).Surprisingly,manyseeminglysimplepuzzlesandgamesarealsohard.Otherresultsarepositive,provingthatsomegamescanbeplayedoptimallyinpolynomialtime.Insomecases,particularlywithone-playerpuzzles,thecomputationallytractablegamesarestillinterestingforhumanstoplay.AfterreviewingsomeofthebasicconceptsincombinatorialgametheoryinSection2,Sections3{5surveyseveralofthesealgorithmicandintractabilityresults.Section6concludeswithasmallsampleofdi±cultopenproblemsinalgorithmiccombinatorialgametheory.Combinatorialgametheoryistobedistinguishedfromotherformsofgametheoryarisinginthecontextofeconomics.Economicgametheoryhasapplicationsincomputerscienceaswell,mostnotablyinthecontextofauctions[dVV01]andanalyzingbehaviorontheInternet[Pap01].2CombinatorialGameTheoryAcombinatorialgametypicallyinvolvestwoplayers,oftencalledLeftandRight,alternatingplayinwell-de¯nedmoves.However,intheinterestingcaseofacombinatorialpuzzle,thereisonlyoneplayer,andforcellularautomatasuchasConway'sGameofLife,therearenoplayers.Inall¤ApreliminaryversionofthispaperappearsintheProceedingsofthe26thInternationalSymposiumonMathe-maticalFoundationsofComputerScience,LectureNotesinComputerScience,CzechRepublic,August2001.yDepartmentofComputerScience,UniversityofWaterloo,Waterloo,OntarioN2L3G1,Canada,[e-mail].1cases,norandomnessorhiddeninformationispermitted:allplayersknowallinformationaboutgameplay(perfectinformation).Theproblemisthuspurelystrategic:howtobestplaythegameagainstanidealopponent.Itisusefultodistinguishseveraltypesoftwo-playerperfect-informationgames[BCG82,pp.16{17].Acommonassumptionisthatthegameterminatesaftera¯nitenumberofmoves(thegameis¯niteorshort),andtheresultisauniquewinner.Ofcourse,thereareexceptions:somegames(suchasLifeandChess)canbedrawnoutforever,andsomegames(suchastic-tac-toeandChess)de¯netiesincertaincases.However,inthecombinatorial-gamesetting,itisusefultode¯nethewinnerasthelastplayerwhoisabletomove;thisiscallednormalplay.If,ontheotherhand,thewinneristhe¯rstplayerwhocannotmove,thisiscalledmisµereplay.(Wewillnormallyassumenormalplay.)Agameisloopyifitispossibletoreturntopreviouslyseenpositions(asinChess,forexample).Finally,agameiscalledimpartialifthetwoplayers(LeftandRight)aretreatedidentically,thatis,eachplayerhasthesamemovesavailablefromthesamegameposition;otherwisethegameiscalledpartizan.Aparticulartwo-playerperfect-informationgamewithouttiesordrawscanhaveoneoffouroutcomesastheresultofidealplay:playerLeftwins,playerRightwins,the¯rstplayertomovewins(whetheritisLeftorRight),orthesecondplayertomovewins.Onegoalinanalyzingtwo-playergamesistodeterminetheoutcomeasoneofthesefourcategories,andto¯ndastrategyforthewinningplayertowin.Anothergoalistocomputeadeeperstructuretogamesdescribedintheremainderofthissection,calledthevalueofthegame.Abeautifulmathematicaltheoryhasbeendevelopedforanalyzingtwo-playercombinatorialgames.ThemostcomprehensivereferenceisthebookWinningWaysbyBerlekamp,Conway,andGuy[BCG82],butamoremathematicalpresentationisthebookOnNumbersandGamesbyConway[Con76].Seealso[Con77,Fra96]foroverviewsand[Fra94]forabibliography.Thebasicideabehindthetheoryissimple:atwo-playergamecanbedescribedbyarootedtree,eachnodehavingzeroormoreleftbranchescorrespondtooptionsforplayerLefttomoveandzeroormorerightbranchescorrespondingtooptionsforplayerRighttomove;leavescorrespondingto¯nishedgames,thewinnerbeingdeterminedbyeithernormalormisµereplay.Theinterestingpartsofcombinatorialgametheoryaretheseveralmethodsformanipulatingandanalyzingsuchgames/trees.Wegiveabriefsummaryofsomeofthesemethodsinthissection.2.1Conway'sSurrealNumbersArichlystructuredspecialclassoftwo-playergamesareJohnH.Conway'ssurrealnumbers1[Con76,Knu74,Gon86,All87],avastgeneralizationoftherealandordinalnumbersystems.Basically,asurrealnumberfLjRgisthe\simplestnumberlargerthanallLeftoptions(inL)andsmallerthanallRightoptions(inR);forthistoconstituteanumber,allLeftandRightoptionsmustbenumbers,de¯ningatotalorder,andeachLeftoptionmustbelessthaneachRightoption.See[Con76]formoreformalde¯nitions.Forexample,thesimplestnumberwithoutanylarger-thanorsmaller-thanconstraints,denotedfjg,is0;thesimplestnumberlargerthan0a