五子棋游戏编程

ComputerGo:AnAIorientedsurveyArtificialIntelligence,Volume132,Issue1,October2001,Pages39-103BrunoBouzy,TristanCazenave2004.10.14劉思源Outline1.Introduction(Go)2.Othergames3.Results4.Evaluation5.Movegeneration6.Treesearch7.Optimization8.Combinatorialgametheory9.Automaticgenerationofknowledge10.MonteCarloGo11.Mathematicalmorphology12.Cognitivescience13.ConclusionIntroductionmindgameshavebeenstudiedasapplicationfieldsforAItheydonotenabletheAIcommunitytobuildastrongGoprogramthecurrentcornerstoneingameprogrammingistheAlpha-BetaalgorithmIntroductionGoprogramshavepoorrankingsinthehumanrankingsystemGoprogramsexhibitstructureatdifferentlevelsInordertobecompetitive,everylevelofaGoprogramhastobeoptimizedThereforeGoprogrammersspendmuchoftheirtimeonoptimizationsIntroductionThegameofGoisaglobalgamethatcanbebrokendownintomanylocalsub-gamesAlthoughlocalsub-gamesaregenerallydependent,thecombinatorialgametheoryoffersanappropriatemodelforthegameofGoAprobleminherentinComputerGoisthatthemodelswiththebestresultsusealotofknowledgeIntroductionThegameofGoisaveryvisualgameGoissocomplexthatitcanbeusedtoperforminterestingcognitiveexperimentsWethinkthatComputerGoremainsanewdomainforcomputerscience,andsofar,nocleartheoreticalmodelhasemergedOthergamesGo-moku變形五子棋Backgammon西洋雙陸棋Othello黑白棋Checkers西洋跳棋Draughts英式象棋Chess西洋棋Shogi將棋OthergamesTheoreticalcomplexitySpacestatesandgametreecomplexityofothergamesthespacestatescomplexity(E)asthenumberofpositionsyoucanreachfromthestartingpositiongametreecomplexity(A)asthenumberofnodesinthesmallesttreenecessarytosolvethegameComplexityofGoOthergamesOthergamesResultsHistoryofComputerGo(Since1963)ComputerGocompetitions(theINGcup,FOSTcup,ladder)ProgramsversushumanplayersTsume-GoCombinatorialgametheoryProgramsversushumanplayersaftereachFOSTcup,thethreebestprogramsplayagainsthumanplayersHandtalkreceivedaJapanese3rdKyudiplomaforwinningitsgamesJaniceKimbeatHandtalk,despiteanenormoushandicapofmorethantwentystones.Recently,MartinMüllerbeatManyFacesofGo,despiteahugehandicapoftwenty-ninestones.AlthoughGoprogramshavebeenimprovedoverthelastfewyears,theyarestillmuchweakerthanhumanplayers.Tsume-GoGoToolsisaverystrongTsume-GoproblemsolverItcansolve5-danproblems(anamateur5-danisroughlyequivalenttoaprofessional1-danGoplayer)IthasevenspottedanerrorinadictionaryofTsume-GoproblemsItcananalyzecomplexsituationscompletely,andfinduniquewinningmovesthatGoplayersfindwithgreatdifficultyHowever,GoToolsisrestrictedtocompletelyenclosedproblemsthatcontainthirteenorfeweremptyintersectionsCombinatorialgametheoryCombinatorialgametheoryhasalsobeenusedtofindthenumberofeyesofagroup,thusenablingaprogramtobreakdownalifeanddeathproblemintoasumofgames,soastoreduceitscomplexityEvaluationthemajordifficultyofComputerGo—buildingtheEvaluationFunction(EF)TheevaluationofapositionisnecessaryforaprogramthatwantstoassociateascorewithagameFindinga“good”EFisveryhard,andisundoubtedlythebiggestobstacleinComputerGoThereforethetaskofpresentingaGoEFisfarfrombeingeasyEvaluationEvaluationConcreteevaluation具體的評估Conceptualevaluation概念式的評估Connectedgroup相連的棋塊“Inside”,“outside”and“morphologicalgroup”ThebuildingofgroupsNumberof“eyes”“Interaction”“Death”,“inversion”,“aggregation”explicit-control&implicit-controlConnectedgroupConnectedgroupFig.4iscalleda“connector”Itsnotationwillbe‘’,soastoindicatethattheoutcomeofthiselementarygameisaneffectiveconnectionwhoeverplaysfirstInthecase(Fig.8),thefinalstateoftheconnectordependsonwhomovesfirst,andwegivethevalue‘*’totheconnectorThen,the“connectedgroups”aredefinedasgroupsofstringslinkedwithconnectors‘’Averyimportantpoint:theconstructionofconnectedgroupsimpliestheuseofresultsfromlocaltreesearcheshavingthegoalofconnection.TheEFusesTreeSearch.ThisisoneimportantaspectoftheEFinGoInside,outsideandmorphologicalgroupThebuildingofgroupsForhumanplayers,thenotionofgroupcorrespondsneithertotheconnectedgroupnotionnortothemorphologicalgroupnotion,buttoacertainextenttobothnotionsForprograms,thequestionofknowingwhichnotionisbetterremainsanopenproblemNevertheless,thismaybespeededupbyusingpatterns,butthentheproblemishowtohandlethepatternsdatabaseNumberof“eyes”Onthewhole,forsize-one-two-or-threeconnectedsets,thenumberofeyesdependsonitsboundary,andopponentstones.Forsizesfromfourtoaboutsix,italsodependsonitsshapeandontheshapeofprisoners.Forexample,Goplayerssaythat“straight4isalive”and“square4isdead”.Forsizebiggerthanaboutsix,thenumberofeyesbecomesgreaterthantwo.EachGoprogrammustcontainsuchexpertiseincountingeyesofaconnectedset.ItisverydifficulttodefinecompleteandadequaterulesfordeterminingthenumberofeyesofgroupsInteractionInteractionThedifferencebetweenthenumberoflibertiesofthetwogroupswillbecrucialindecidingwhichgroupdominatestheotherWhenthevalue(relativetozero)oftheinteractiondependsonwhoplaysfirst,itsvalueisdesignated‘*’Suchisthecaseinourexample.Whenonegroupdominatestheotherwhoeverplaysfirst,theinteractionis‘’forthedominatingcolorForexample,theinteractionbetweentheblackgroup(correspondi