人工智能游戏开发.pptx

人工智能游戏开发.pptx

《人工智能游戏开发.pptx》由会员分享，可在线阅读，更多相关《人工智能游戏开发.pptx（16页珍藏版）》请在冰点文库上搜索。

ConnectFourusingAlpha-BetaPruning,BillyLandowskiCptS5407December2010,Overview,BackgroundConnectFourasasearchproblemAlpha-betapruningDetailsaboutwinningHeuristicsImplementation/DemoConclusion,Background,SoldbyMiltonBradleyinFebruary19742playersAlternateturnsGoal:

Connectfourtilesinarowhorizontally,vertically,ordiagonally,ConnectFourasaSearchProblem,7possiblemovesperturnEnumerateeachmoveContinueforeachboardconfiguration,ConnectFourasaSearchProblem,States:

AnyboardconfigurationwithatmostoneplayerstileineachlocationInitialState:

Anemptygameboardwithnotiles.Actions:

Placeatileofthecurrentplayerscolorintoanycolumnthatisnotfull.TransitionModel:

Returnsaboardconfigurationwithatileaddedtothespecifiedcolumn.Goal/TerminalTest:

Aplayerhasfourofhertilesinalineeitherhorizontally,vertically,ordiagonally,orthegameboardisfull（indicatingatie）.Utility:

+ifplayerhasconnectedfour,0ifboardisfull,ifopponenthasconnectedfour.,Alpha-betapruning,O（bd/2）timecomplexityb=branchingfactor=7d=depth=76=42ComputationallyintensiveNeedcut-offdepthCanalsoaddheuristics,WinningConnectFour,Towin,playerneedsa“winningline”of4,3-out-of-4Heuristic,Towin,playerneedsa“near”winninglineof3,3-out-of-4Heuristic（cont.）,Counttotal3-out-of-4“unblocked”winninglinesComparetoopponentUtility（p,G）=f（p,G）f（opponent（p）,G）f（a,G）=#of3-out-of-4winninglinesforplayeraonboardG,ScoreboardHeuristic,Extend3-out-of-4heuristicton-out-of-4forn3AwardweightedpointsbasedonthevalueofnScore（p,G）=100（n3）+10（n2）+1（n1）niisthenumberofi-out-of-4winninglinesforplayerpongameboardG,ScoreboardHeuristic（cont.）,Five1-out-of-4winninglines（n1=5）Five2-out-of-4winninglines（n2=5）Score=100（0）+10（5）+1（5）=55,ScoreboardHeuristic（cont.）,CompareplayersscoresUtility（p,G）=Score（p,G）Score（opponent（p）,G）,Implementation,WritteninC#under.NETFrameworkMicrosoftVisualStudio2008WindowsFormsapplication,CPUDifficulties,4difficultiesBeginnerrandomModeratealpha-betapruningwithcutoff-depth3andsimpleutilityfunctionHardalpha-betapruningwithcutoff-depth6and3-out-of-4heuristicExpertalpha-betapruningwithcutoff-depth6andscoreboardheuristicAspectofrandomness,ComparisonofCPUDifficulties,Demonstration,