人工智能游戏开发35480

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Connect Four using Alpha-Beta Pruning,Billy Landowski,CptS 540,7 December 2010,Overview,Background,Connect Four as a search problem,Alpha-beta pruning,Details about winning,Heuristics,Implementation/Demo,Conclusion,Background,Sold by Milton Bradley in February 1974,2 players,Alternate turns,Goal:Connect four tiles in a row horizontally,vertically,or diagonally,Connect Four as a Search Problem,7 possible moves per turn,Enumerate each move,Continue for each board configuration,Player 1,Player 2,Connect Four as a Search Problem,States,:Any board configuration with at most one players tile in each location,Initial State,:An empty game board with no tiles.,Actions,:Place a tile of the current players color into any column that is not full.,Transition Model,:Returns a board configuration with a tile added to the specified column.,Goal/Terminal Test,:A player has four of her tiles in a line either horizontally,vertically,or diagonally,or the game board is full(indicating a tie).,Utility,:+if player has connected four,0 if board is full,if opponent has connected four.,Alpha-beta pruning,O,(,b,d,/2,)time complexity,b,=branching factor=7,d,=depth=7 6=42,Computationally intensive,Need cut-off depth,Can also add heuristics,Winning Connect Four,To win,player needs a“winning line”of 4,3-out-of-4 Heuristic,To win,player needs a“near”winning line of 3,3-out-of-4 Heuristic(cont.),Count total 3-out-of-4“unblocked”winning lines,Compare to opponent,Utility(p,G)=f(p,G)f(opponent(p),G),f(a,G)=#of 3-out-of-4 winning lines for player a on board G,Scoreboard Heuristic,Extend 3-out-of-4 heuristic to,n,-out-of-4 for,n,3,Award weighted points based on the value of,n,Score(p,G)=100(,n,3,)+10(,n,2,)+1(,n,1,),n,i,is the number of,i,-out-of-4 winning lines for player p on game board G,Scoreboard Heuristic(cont.),Five 1-out-of-4 winning lines(,n,1=5),Five 2-out-of-4 winning lines(,n,2=5),Score=100(0)+10(5)+1(5)=,55,Scoreboard Heuristic(cont.),Compare players scores,Utility(p,G),=Score(p,G)Score(opponent(p),G),Implementation,Written in C#under.NET Framework,Microsoft Visual Studio 2008,Windows Forms application,CPU Difficulties,4 difficulties,Beginner random,Moderate alpha-beta pruning with cutoff-depth 3 and simple utility function,Hard alpha-beta pruning with cutoff-depth 6 and 3-out-of-4 heuristic,Expert alpha-beta pruning with cutoff-depth 6 and scoreboard heuristic,Aspect of randomness,Comparison of CPU Difficulties,Demonstration,演讲完毕，谢谢观看！,