《[精选]人工智能游戏开发》由会员分享，可在线阅读，更多相关《[精选]人工智能游戏开发（17页珍藏版）》请在金锄头文库上搜索。
1、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:
2、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,Connect Four as a Search Problem,States: Any board configuration with at most one players tile in each location Ini
3、tial 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 horizonta
4、lly, 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 (bd/2) time complexity b = branching factor = 7 d = depth = 7 6 = 42 Computationally intensive Need cut-off
5、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)
6、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(n3) + 10(n2) + 1(n1) ni is the number of i-out-of-4 winning lines for player p on game board G,Scoreboa
7、rd Heuristic (cont.),Five 1-out-of-4 winning lines (n1 = 5) Five 2-out-of-4 winning lines (n2 = 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
8、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,演讲完毕，谢谢观看！,
