五子棋游戏编程.ppt

《五子棋游戏编程.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerGo:AnAIorientedsurveyArtificialIntelligence,Volume132,Issue1,October2001,Pages39-103BrunoBouzy,TristanCazenave2004.10.14劉思源OutlineIntroduction(Go)OthergamesResultsEvaluationMovegenerationTreesearchOptimizationCombinatorialgametheoryAutomaticgenerationo

2、fknowledgeMonteCarloGoMathematicalmorphologyCognitivescienceConclusionIntroductionmindgameshavebeenstudiedasapplicationfieldsforAItheydonotenabletheAIcommunitytobuildastrongGoprogramthecurrentcornerstoneingameprogrammingistheAlpha-BetaalgorithmIntroductionGopr

3、ogramshavepoorrankingsinthehumanrankingsystemGoprogramsexhibitstructureatdifferentlevelsInordertobecompetitive,everylevelofaGoprogramhastobeoptimizedThereforeGoprogrammersspendmuchoftheirtimeonoptimizationsIntroductionThegameofGoisaglobalgamethatcanbebrokendow

4、nintomanylocalsub-gamesAlthoughlocalsub-gamesaregenerallydependent,thecombinatorialgametheoryoffersanappropriatemodelforthegameofGoAprobleminherentinComputerGoisthatthemodelswiththebestresultsusealotofknowledgeIntroductionThegameofGoisaveryvisualgameGoissocomp

5、lexthatitcanbeusedtoperforminterestingcognitiveexperimentsWethinkthatComputerGoremainsanewdomainforcomputerscience,andsofar,nocleartheoreticalmodelhasemergedOthergamesGo-moku變形五子棋Backgammon西洋雙陸棋Othello黑白棋Checkers西洋跳棋Draughts英式象棋Chess西洋棋Shogi將棋OthergamesTheoret

6、icalcomplexitySpacestatesandgametreecomplexityofothergamesthespacestatescomplexity(E)asthenumberofpositionsyoucanreachfromthestartingpositiongametreecomplexity(A)asthenumberofnodesinthesmallesttreenecessarytosolvethegameComplexityofGoOthergamesOthergamesRe

7、sultsHistoryofComputerGo(Since1963)ComputerGocompetitions(theINGcup,FOSTcup,ladder)ProgramsversushumanplayersTsume-GoCombinatorialgametheoryProgramsversushumanplayersaftereachFOSTcup,thethreebestprogramsplayagainsthumanplayersHandtalkreceivedaJapanese3rdKyudip

8、lomaforwinningitsgamesJaniceKimbeatHandtalk,despiteanenormoushandicapofmorethantwentystones.Recently,MartinMüllerbeatManyFacesofGo,despiteahugehandicapoftwenty-ninestones.Although