资源预览需要最新版本的Flash Player支持。
您尚未安装或版本过低,建议您
MachLearn200663211–215DOI10.1007/s10994-006-8919-xGUESTEDITORIALMachinelearningandgamesMichaelBowlingJohannesFurnkranzThoreGraepelRonMusickPublishedonline10May2006SpringerScienceBusinessMedia,LLC2006Thehistoryoftheinteractionofmachinelearningandcomputergame-playinggoesbacktotheearliestdaysofArtificialIntelligence,whenArthurSamuelworkedonhisfamouschecker-playingprogram,pioneeringmanymachine-learningandgame-playingtechniquesSamuel,1959,1967.Sincethen,bothfieldshaveadvancedconsiderably,andresearchintheintersectionofthetwocanbefoundregularlyinconferencesintheirrespectivefieldsandingeneralAIconferences.ForsurveysofthefieldwerefertoGinsberg1998,Schaeffer2000,Furnkranz2001；editedvolumeshavebeencompiledbySchaefferandvandenHerik2002andbyFurnkranzandKubat2001.Inrecentyears,thecomputergamesindustryhasdiscoveredAIasanecessaryingredienttomakegamesmoreentertainingandchallengingand,viceversa,AIhasdiscoveredcom-putergamesasaninterestingandrewardingapplicationarea.Theindustry’sperspectiveiswitnessedbyaplethoraofrecentbooksongentleintroductionstoAItechniquesforgameprogrammersCollins,2002；Champanard,2003；BourgSeemann,2004；Schwab,2004oraseriesofeditedcollectionsofarticlesRabin,2002,2003,2006.AIresearchoncomputergamesbegantofollowdevelopmentsinthegamesindustryearlyon,butsinceJohnLaird’skeynoteaddressattheAAAI2000conference,inwhichheadvocatedInteractiveComputerGamesasachallengingandrewardingapplicationareaforAILairdvanLent,2001,numerousworkshopsFuOrkin,2004；Ahaetal.,2005,conferences,andspecialissuesofjournalsForbusLaird,2002demonstratethegrowingimportanceofgame-playingapplicationsforArtificialIntelligence.M.Bowlingenvelopebacke-mailbowlingcs.ualberta.caJ.Furnkranze-mailfuernkranzinatik.tu-darmstadt.deT.Graepele-mailthoregmicrosoft.comR.Musicke-mailmusickikuni.comSpringer212MachLearn200663211–215Games,whethercreatedforentertainment,simulation,oreducation,providegreatop-portunitiesachinelearning.ThevarietyofpossiblevirtualworldsandthesubsequentML-relevantproblemsposedfortheagentsinthoseworldsislimitedonlybytheimagination.Furthermore,notonlyisthegamesindustrylargeandgrowinghavingsurpassedthemovieindustryinrevenueafewyearsback,butitisfacedwithatremendousdemandfornoveltythatitstrugglestoprovide.Againstthisbackdrop,machinelearningdrivensuccesseswoulddrawhigh-profileattentiontothefield.Surprisinglyhowever,themorecommercialthegametodate,thelessimpactlearninghasmade.Thisisquiteunlikeothergreatmatchesbetweenapplicationanddata-drivenanalyticssuchasdataminingandOLAP.Topicsofparticularimportanceforsuccessfulgameapplicationsincludelearninghowtoplaythegamewell,playermodeling,adaptivity,modelinterpretationandofcourseperfor-mance.TheseneedscanberecastasacallfornewpracticalandtheoreticaltoolstohelpwithlearningtoplaythegameGameworldsprovideexcellenttestbedsforinvestigatingthepoten-tialtoimproveagents’capabilitiesvialearning.Theenvironmentcanbeconstructedwithvaryingcharacteristics,fromdeterministicanddiscreteasinclassicalboardandcardgamestonon-deterministicandcontinuousasinactioncomputergames.Learningalgorithmsforsuchtaskshavebeenstudiedquitethoroughly.Probablythebest-knowninstanceofalearninggame-playingagentistheBackgammon-playingprogramTD-GammonTesauro,1995.learningaboutplayersOpponentmodeling,partnermodeling,teammodeling,andmultipleteammodelingarefascinating,interdependentandlargelyunsolvedchallengesthataimatimprovingplaybytryingtodiscoverandexploittheplans,strengths,andweaknessesofaplayer’sopponentsand/orpartners.OneofthegrandchallengesinthislineofworkaregameslikePoker,whereopponentmodelingiscrucialtoimproveovergame-theoreticallyoptimalplayBillingsetal.,2002.behaviorcaptureofplayersCreatingaconvincingavatarbasedonaplayer’sin-gamebe-haviorisaninterestingandchallengingsupervisedlearningtask.Forexample,inMassiveMultiplayerOnlineRole-playingGamesMMORGsanavatarthatistrainedtosimulateauser’sgame-playingbehaviorcouldtakehiscreator’splaceattimeswhenthehumanplayercannotattendtohisgamecharacter.FirststepsinthisareahavebeenmadeincommercialvideogamessuchasForzaMotorsportXboxwheretheplayercantraina“Drivatar”thatlearnstogoaroundthetrackinthestyleoftheplayerbyobservingandlearningfromthedrivingstyleofthatplayerandgeneralizingtonewtracksandcars.modelselectionandstabilityOnlinesettingsleadtowhatiseffectivelytheunsupervisedconstructionofmodelsbysupervisedalgorithms.sforbiasingtheproposedmodelspacewithoutsignificantlossofpredictivepowerarecriticalnotjustforlearningefficiency,butinterpretiveabilityandend-userconfidence.optimizingforadaptivityBuildingopponentsthatcanjustbarelyloseininterestingwaysisjustasimportantforthegameworldascreatingworld-classopponents.Thisrequiresbuildinghighlyadaptivemodelsthatcansubstantivelypersonalizetoadversariesorpart-nerswithawiderangeofcompetenceandrapidshiftsinplaystyle.Byintroducingaverydifferentsetofupdateandoptimizationcriteriaforlearners,awealthofnewresearchtargetsarecreated.modelinterpretation“What’smynextmove”isnottheonlyquerydesiredofmodelsinagame,butitiscertainlytheonewhichgetsthemostattention.Creatingtheillusionofintelligencerequires“paintingapicture”ofanagent’sthinkingprocess.TheabilitytodescribethecurrentstateofamodelandtheprocessofinferenceinthatmodelfromSpringerMachLearn200663211–215213decisiontodecisionenablesqueriesthatprovidethefoundationforahostofsocialactionsinagamesuchaspredictions,contracts,counter-factualassertions,advice,justification,negotiation,anddemagoguery.Thesecanhaveasmuchormoreinfluenceonoutcomesasactualin-gameactions.peranceResourcerequirementsforupdateandinferencewillalwaysbeofgreatimpor-tance.TheAIdoesnotgetthebulkoftheCPUormemory,andthemachinesdrivingthemarketwillalwaysbeunderpoweredcomparedtotypicaldesktopsatanypointintime.Thisspecialissuecontainsthreearticlesandoneresearchnotethatspanthewiderangeofresearchintheintersectionofgameplayingandmachinelearning.Inthefirstcontribution,AdaptiveGameAIwithDynamicScripting,Sproncketal.tackletheproblemofadaptivitybydynamicallymodifyingtheruleswhichgoverncharacterbe-haviorin-game.Thispaperistargetedatthecommercialgamesindustry,andprovidessomegoodinsightintoproblemsfacedbythecreatorsoftoday’sroleplayinggames.Theauthorsproposefourfunctionalandfourcomputationalrequirementsforon-linelearningingames.Theythenproceedtoshowhowdynamicscriptingfitsintothoserequirements,andprovideexperimentalevidenceofthepotentialpromiseofthisapproach.Dynamicscriptingcanbecharacterizedasstochasticoptimization.Theauthorsuatedynamicscriptingonboththetaskofprovidingthetoughestopponentpossible,andonthetaskofdifficultyscaling.Gooddifficultyscalingunderpinswhatmakesmostgamesfun,andsolvingthisproblemisoftenverychallengingandthesolutionsarealmostalwaysad-hoc.TheauthorspresentexperimentaldatathatcomparesdynamicscriptingtostaticopponentsandthosecontrolledbyQ-LearningandMonteCarlo.ThetestenvironmentsincludebothsimulatedgamesandanactualcommercialgameNeverwinterNights,andhelptopresentaveryinterestingstudywhichissuretoblazeapathforfurtherinterestingresearch.Thesecondpaper,UniversalParameterOptimizationinGamesBasedonSPSAbySzepesvariandKocsis,considerstheproblemofoptimizingparameterstoimprovetheperfor-manceofparameterizedpoliciesforgameplay.TheyconsidertheSimultaneousPerturbationStochasticApproximationSPSAintroducedbySpall1992whichisageneralgra-dientfreeoptimizationthatisapplicabletoawiderangeofoptimizationproblems.TheauthorsdemonstratethatSPSAisapplicabletoawiderangeoftypicaloptimizationproblemsingamesandproposeseveralstoenhancetheperanceofSPSA.Theseenhancementsincludetheuseofcommonrandomnumbersandantitheticvariables,acombinationwithRPROPandthereuseofsamples.TheapplicationtogamesconsidersthedomainoflearningtoplayOmahaHi-LoPokerwiththeirpokerprogramMcRaise.SPSAcombinedwiththeirproposedenhancementsleadstopokerperancecompetitivewithTD-learning,thesosuccessfullyusedbyTesauro1995,forlearningaworld-classuationfunctionforBackgammonandstillusedintoday’sworldclassbackgammonprogramssuchasJellyFishandSnowie.Thethirdcontribution,LearningtoBidinBridgebyMarkovitchandAmit,addressestheproblemofbiddinginthegameofBridge.WhileresearchinBridgeplayinghaspioneeredMonteCarlosearchalgorithmsfortheplayingphaseofcardgamesandresultedinprogramsofconsiderablestrengthGinsberg,1999,thebiddingphase,inwhichthegoaltheso-calledcontractofthesubsequentplayingphaseisdetermined,isstillamajorweaknessofexistingBridgeprograms.ThispaperisaboutanapproachthatsupportsthedifficultbiddingphaseinthegameBridgewithtechniquesfrommachinelearning,inparticularopponentmodelingviathelearningofdecisionnetsandviamodel-basedMonteCarlosamplingtoaddresstheproblemofhiddenination.Theuationclearlyestablishesthatthesystemimproveswithlearning,anditseemsthatthelevelofplayachievedbythisprogramsurpassesthelevelSpringer214MachLearn200663211–215ofthebiddingmoduleofcurrentstate-of-the-artprogramsandapproachesthatofanexpertplayer.Finally,SadikovandBratkopresentaresearchnoteonLearningLong-termChessStrate-giesfromDatabases.Theyaddresstheproblemofknowledgediscoveryingamedatabases.anygamesorsubgamessuchaschessendgames,therearegamedatabasesavailable,whichcontainperfectinationaboutthegameinthesensethatforeverypossibleposi-tion,thegame-theoreticoutcomeisstoredinadatabase.However,althoughthesedatabasescontainallinationtoallowperfectplay,theyarenotamenabletohumananalysis,andaretypicallynotverywellunderstood.Forexample,chessGrandmasterJohnNunnanalyzedsev-eralsimplechessendgamedatabasesresultinginaseriesofwidelyacknowledgedendgamebooksNunn,1992,1994b,1995,butreadilyadmittedthathedoesnotyetunderstandallaspectsofthedatabasesheanalyzedNunn,1994a.Thispaperreportsonanattempttomakeheadwaybyautomaticallyconstructingplayingstrategiesfromchessendgamedatabases.Itdescribesaforbreakinguptheproblemintodifferentgamephases.Foreachphase,itisthenproposedtolearnaseparateuationfunctionvialinearregression.Experimentsinthethekingandrookvs.king,orkingandqueenvs.kingandrookendgamesshowencouragingresults,butalsoillustratethedifficultyoftheproblem.Machinelearninghasbeeninstrumentaltodateinbuildingsomeoftheworld’sbestplayersinBackgammonandhasleadtointerestingresultsingameslikeChessandGo.Tomoveintomainstreamcommercialgames,machinelearningresearchhastofacewhatinmanywaysaretheharderproblemsoflosingininterestingways,creatingmoreusefulillusionsofintelligence,hyper-fastadaptation,andtakingonpersona.Thearticlesinthisspecialissueprovideaglimpseintodifferentfacetsofalloftheseproblems.ReferencesAha,D.W.,Mu˜noz-AvilaH.M.,vanLent,M.Eds.,2005.Reasoning,representation,andlearningincomputergamesProceedingsoftheIJCAIworkshop.Edinburgh,ScotlandNavalResearchLaboratory,NavyCenterforAppliedResearchinArtificialIntelligence.TechnicalReportAIC-05-127.Billings,D.,Pe˜na,L.,Schaeffer,J.,Szafron,D.2002.Thechallengeofpoker.ArtificialIntelligence,1341–2,201–240,SpecialIssueonGames,ComputersandArtificialIntelligence.Bourg,D.M.,SeemannG.2004.AIforgamedevelopersCreatingintelligentbehavioringames.O’Reilly.Champanard,A.2003.AIgamedevelopment.NewRidersPublishing.Collins,M.2002.AdvancedAIgamedevelopment.WordwarePublishingInc.Forbus,K.D.,LairdJ.E.2002.Guesteditors’introductionAIandtheentertainmentindustry.IEEEIntelligentSystems,174,15–16.Fu,D.OrkinJ.Eds.,2004.ChallengesofgameAIProceedingsoftheAAAI-04workshop.AAAIPress.TechnicalReportWS-04-04.Furnkranz,J.2001.MachinelearningingamesAsurvey.InFurnkranzandKubat,2001,pp.11–59.Furnkranz,J.,KubatM.Eds.,2001.Machinesthatlearntoplaygames.Huntington,NYNovaSciencePublishers.Ginsberg,M.L.1998.Computers,gamesandtherealworld.ScientificAmericanPresents94.SpecialIssueonExploringIntelligence.Ginsberg,M.L.1999.GIBStepstowardanexpert-levelbridge-playingprogram.InProceedingsoftheInternationalJointConferenceonArtificialIntelligenceIJCAI-99,pp.584–589,Stockholm,Sweden.Laird,J.E.,vanLent,M.2001.Human-levelAI’skillerapplicationInteractivecomputergames.AIMagazine,222,15–26.Nunn,J.1992.Secretsofrookendings.Batsford.Nunn,J.1994a.Extractinginationfromendgamedatabases.InH.J.vandenHerik,I.S.Herschberg,andJ.W.H.M.UiterwijkEds.,Advancesincomputerchess7,pp.19–34.Maastricht,TheNetherlandsUniversityofLimburg.Nunn,J.1994b.Secretsofpawnlessendings.Batsford.Springer