外文资料--Machine learning and games.pdf

MachLearn(2006)63:211215DOI10.1007/s10994-006-8919-xGUESTEDITORIALMachinelearningandgamesMichaelBowlingJohannesFurnkranzThoreGraepelRonMusickPublishedonline:10May2006SpringerScience+BusinessMedia,LLC2006Thehistoryoftheinteractionofmachinelearningandcomputergame-playinggoesbacktotheearliestdaysofArtificialIntelligence,whenArthurSamuelworkedonhisfamouschecker-playingprogram,pioneeringmanymachine-learningandgame-playingtechniques(Samuel,1959,1967).Sincethen,bothfieldshaveadvancedconsiderably,andresearchintheintersectionofthetwocanbefoundregularlyinconferencesintheirrespectivefieldsandingeneralAIconferences.ForsurveysofthefieldwerefertoGinsberg(1998),Schaeffer(2000),Furnkranz(2001)；editedvolumeshavebeencompiledbySchaefferandvandenHerik(2002)andbyFurnkranzandKubat(2001).Inrecentyears,thecomputergamesindustryhasdiscoveredAIasanecessaryingredienttomakegamesmoreentertainingandchallengingand,viceversa,AIhasdiscoveredcom-putergamesasaninterestingandrewardingapplicationarea.TheindustrysperspectiveiswitnessedbyaplethoraofrecentbooksongentleintroductionstoAItechniquesforgameprogrammers(Collins,2002；Champanard,2003；Bourg&Seemann,2004；Schwab,2004)oraseriesofeditedcollectionsofarticles(Rabin,2002,2003,2006).AIresearchoncomputergamesbegantofollowdevelopmentsinthegamesindustryearlyon,butsinceJohnLairdskeynoteaddressattheAAAI2000conference,inwhichheadvocatedInteractiveComputerGamesasachallengingandrewardingapplicationareaforAI(Laird&vanLent,2001),numerousworkshops(Fu&Orkin,2004；Ahaetal.,2005),conferences,andspecialissuesofjournals(Forbus&Laird,2002)demonstratethegrowingimportanceofgame-playingapplicationsforArtificialIntelligence.M.Bowling(envelopeback)e-mail:bowlingcs.ualberta.caJ.Furnkranze-mail:fuernkranzinformatik.tu-darmstadt.deT.Graepele-mail:R.Musicke-mail:Springer212MachLearn(2006)63:211215Games,whethercreatedforentertainment,simulation,oreducation,providegreatop-portunitiesformachinelearning.ThevarietyofpossiblevirtualworldsandthesubsequentML-relevantproblemsposedfortheagentsinthoseworldsislimitedonlybytheimagination.Furthermore,notonlyisthegamesindustrylargeandgrowing(havingsurpassedthemovieindustryinrevenueafewyearsback),butitisfacedwithatremendousdemandfornoveltythatitstrugglestoprovide.Againstthisbackdrop,machinelearningdrivensuccesseswoulddrawhigh-profileattentiontothefield.Surprisinglyhowever,themorecommercialthegametodate,thelessimpactlearninghasmade.Thisisquiteunlikeothergreatmatchesbetweenapplicationanddata-drivenanalyticssuchasdataminingandOLAP.Topicsofparticularimportanceforsuccessfulgameapplicationsincludelearninghowtoplaythegamewell,playermodeling,adaptivity,modelinterpretationandofcourseperfor-mance.Theseneedscanberecastasacallfornewpracticalandtheoreticaltoolstohelpwith:learningtoplaythegame:Gameworldsprovideexcellenttestbedsforinvestigatingthepoten-tialtoimproveagentscapabilitiesvialearning.Theenvironmentcanbeconstructedwithvaryingcharacteristics,fromdeterministicanddiscreteasinclassicalboardandcardgamestonon-deterministicandcontinuousasinactioncomputergames.Learningalgorithmsforsuchtaskshavebeenstudiedquitethoroughly.Probablythebest-knowninstanceofalearninggame-playingagentistheBackgammon-playingprogramTD-Gammon(Tesauro,1995).learningaboutplayers:Opponentmodeling,partnermodeling,teammodeling,andmultipleteammodelingarefascinating,interdependentandlargelyunsolvedchallengesthataimatimprovingplaybytryingtodiscoverandexploittheplans,strengths,andweaknessesofaplayersopponentsand/orpartners.OneofthegrandchallengesinthislineofworkaregameslikePoker,whereopponentmodelingiscrucialtoimproveovergame-theoreticallyoptimalplay(Billingsetal.,2002).behaviorcaptureofplayers:Creatingaconvincingavatarbasedonaplayersin-gamebe-haviorisaninterestingandchallengingsupervisedlearningtask.Forexample,inMassiveMultiplayerOnlineRole-playingGames(MMORGs)anavatarthatistrainedtosimulateausersgame-playingbehaviorcouldtakehiscreatorsplaceattimeswhenthehumanplayercannotattendtohisgamecharacter.FirststepsinthisareahavebeenmadeincommercialvideogamessuchasForzaMotorsport(Xbox)wheretheplayercantraina“Drivatar”thatlearnstogoaroundthetrackinthestyleoftheplayerbyobservingandlearningfromthedrivingstyleofthatplayerandgeneralizingtonewtracksandcars.modelselectionandstability:Onlinesettingsleadtowhatiseffectivelytheunsupervisedconstructionofmodelsbysupervisedalgorithms.Methodsforbiasingtheproposedmodelspacewithoutsignificantlossofpredictivepowerarecriticalnotjustforlearningefficiency,butinterpretiveabilityandend-userconfidence.optimizingforadaptivity:Buildingopponentsthatcanjustbarelyloseininterestingwaysisjustasimportantforthegameworldascreatingworld-classopponents.Thisrequiresbuildinghighlyadaptivemodelsthatcansubstantivelypersonalizetoadversariesorpart-nerswithawiderangeofcompetenceandrapidshiftsinplaystyle.Byintroducingaverydifferentsetofupdateandoptimizationcriteriaforlearners,awealthofnewresearchtargetsarecreated.modelinterpretation:“Whatsmynextmove”isnottheonlyquerydesiredofmodelsinagame,butitiscertainlytheonewhichgetsthemostattention.Creatingtheillusionofintelligencerequires“paintingapicture”ofanagentsthinkingprocess.TheabilitytodescribethecurrentstateofamodelandtheprocessofinferenceinthatmodelfromSpringerMachLearn(2006)63:211215213decisiontodecisionenablesqueriesthatprovidethefoundationforahostofsocialactionsinagamesuchaspredictions,contracts,counter-factualassertions,advice,justification,negotiation,anddemagoguery.Thesecanhaveasmuchormoreinfluenceonoutcomesasactualin-gameactions.performance:Resourcerequirementsforupdateandinferencewillalwaysbeofgreatimpor-tance.TheAIdoesnotgetthebulkoftheCPUormemory,andthemachinesdrivingthemarketwillalwaysbeunderpoweredcomparedtotypicaldesktopsatanypointintime.Thisspecialissuecontainsthreearticlesandoneresearchnotethatspanthewiderangeofresearchintheintersectionofgameplayingandmachinelearning.Inthefirstcontribution,AdaptiveGameAIwithDynamicScripting,Sproncketal.tackletheproblemofadaptivitybydynamicallymodifyingtheruleswhichgoverncharacterbe-haviorin-game.Thispaperistargetedatthecommercialgamesindustry,andprovidessomegoodinsightintoproblemsfacedbythecreatorsoftodaysroleplayinggames.Theauthorsproposefourfunctionalandfourcomputationalrequirementsforon-linelearningingames.Theythenproceedtoshowhowdynamicscriptingfitsintothoserequirements,andprovideexperimentalevidenceofthepotentialpromiseofthisapproach.Dynamicscriptingcanbecharacterizedasstochasticoptimization.Theauthorsevaluatedynamicscriptingonboththetaskofprovidingthetoughestopponentpossible,andonthetaskofdifficultyscaling.Gooddifficultyscalingunderpinswhatmakesmostgamesfun,andsolvingthisproblemisoftenverychallengingandthesolutionsarealmostalwaysad-hoc.TheauthorspresentexperimentaldatathatcomparesdynamicscriptingtostaticopponentsandthosecontrolledbyQ-LearningandMonteCarlo.Thetestenvironmentsincludebothsimulatedgamesandanactualcommercialgame(NeverwinterNights),andhelptopresentaveryinterestingstudywhichissuretoblazeapathforfurtherinterestingresearch.Thesecondpaper,UniversalParameterOptimizationinGamesBasedonSPSAbySzepesvariandKocsis,considerstheproblemofoptimizingparameterstoimprovetheperfor-manceofparameterizedpoliciesforgameplay.TheyconsidertheSimultaneousPerturbationStochasticApproximation(SPSA)methodintroducedbySpall(1992)whichisageneralgra-dientfreeoptimizationmethodthatisapplicabletoawiderangeofoptimizationproblems.TheauthorsdemonstratethatSPSAisapplicabletoawiderangeoftypicaloptimizationproblemsingamesandproposeseveralmethodstoenhancetheperformanceofSPSA.Theseenhancementsincludetheuseofcommonrandomnumbersandantitheticvariables,acombinationwithRPROPandthereuseofsamples.TheapplicationtogamesconsidersthedomainoflearningtoplayOmahaHi-LoPokerwiththeirpokerprogramMcRaise.SPSAcombinedwiththeirproposedenhancementsleadstopokerperformancecompetitivewithTD-learning,themethodsosuccessfullyusedbyTesauro(1995),forlearningaworld-classevaluationfunctionforBackgammonandstillusedintodaysworldclassbackgammonprogramssuchasJellyFishandSnowie.Thethirdcontribution,LearningtoBidinBridgebyMarkovitchandAmit,addressestheproblemofbiddinginthegameofBridge.WhileresearchinBridgeplayinghaspioneeredMonteCarlosearchalgorithmsfortheplayingphaseofcardgamesandresultedinprogramsofconsiderablestrength(Ginsberg,1999),thebiddingphase,inwhichthegoal(theso-calledcontract)ofthesubsequentplayingphaseisdetermined,isstillamajorweaknessofexistingBridgeprograms.ThispaperisaboutanapproachthatsupportsthedifficultbiddingphaseinthegameBridgewithtechniquesfrommachinelearning,inparticularopponentmodelingviathelearningofdecisionnetsandviamodel-basedMonteCarlosamplingtoaddresstheproblemofhiddeninformation.Theevaluationclearlyestablishesthatthesystemimproveswithlearning,anditseemsthatthelevelofplayachievedbythisprogramsurpassesthelevelSpringer214MachLearn(2006)63:211215ofthebiddingmoduleofcurrentstate-of-the-artprogramsandapproachesthatofanexpertplayer.Finally,SadikovandBratkopresentaresearchnoteonLearningLong-termChessStrate-giesfromDatabases.Theyaddresstheproblemofknowledgediscoveryingamedatabases.Formanygamesorsubgames(suchaschessendgames),therearegamedatabasesavailable,whichcontainperfectinformationaboutthegameinthesensethatforeverypossibleposi-tion,thegame-theoreticoutcomeisstoredinadatabase.However,althoughthesedatabasescontainallinformationtoallowperfectplay,theyarenotamenabletohumananalysis,andaretypicallynotverywellunderstood.Forexample,chessGrandmasterJohnNunnanalyzedsev-eralsimplechessendgamedatabasesresultinginaseriesofwidelyacknowledgedendgamebooks(Nunn,1992,1994b,1995),butreadilyadmittedthathedoesnotyetunderstandallaspectsofthedatabasesheanalyzed(Nunn,1994a).Thispaperreportsonanattempttomakeheadwaybyautomaticallyconstructingplayingstrategiesfromchessendgamedatabases.Itdescribesamethodforbreakinguptheproblemintodifferentgamephases.Foreachphase,itisthenproposedtolearnaseparateevaluationfunctionvialinearregression.Experimentsinthethekingandrookvs.king,orkingandqueenvs.kingandrookendgamesshowencouragingresults,butalsoillustratethedifficultyoftheproblem.MachinelearninghasbeeninstrumentaltodateinbuildingsomeoftheworldsbestplayersinBackgammonandhasleadtointerestingresultsingameslikeChessandGo.Tomoveintomainstreamcommercialgames,machinelearningresearchhastofacewhatinmanywaysaretheharderproblemsoflosingininterestingways,creatingmoreusefulillusionsofintelligence,hyper-fastadaptation,andtakingonpersona.Thearticlesinthisspecialissueprovideaglimpseintodifferentfacetsofalloftheseproblems.ReferencesAha,D.W.,Munoz-AvilaH.M.,&vanLent,M.(Eds.),(2005).Reasoning,representation,andlearningincomputergames:ProceedingsoftheIJCAIworkshop.Edinburgh,Scotland:NavalResearchLaboratory,NavyCenterforAppliedResearchinArtificialIntelligence.TechnicalReportAIC-05-127.Billings,D.,Pena,L.,Schaeffer,J.,&Szafron,D.(2002).Thechallengeofpoker.ArtificialIntelligence,134(12),201240,SpecialIssueonGames,ComputersandArtificialIntelligence.Bourg,D.M.,&SeemannG.(2004).AIforgamedevelopersCreatingintelligentbehavioringames.OReilly.Champanard,A.(2003).AIgamed