– Tln01nga goal ? weak methods: depth-first search (DFS), breadth-first search (BFS), constraint satisfaction (CSP) ? strong methods: use ‘heuristics’, A* search s goal nodes Tic Tac Toe Playing Strategies Two players human computer. The objective is to write a computer program in such a way that computer wins most of the time. Three approaches are presented to play this game which increase in – Complexity – Use of generalization – Clarity of their knowledge – Extensibility of their approach These approaches will move towards being representations of what we will call A1 techniques.
Tic Tac Toe Board- (or Noughts and crosses, Xs and Os) It is two players, X and O, game who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. 2 4 5 6 8 9 7 positions Zero-Sum Games ? Focus primarily on “adversarial games” ? Two-player, zero-sum games As Player 1 gains strength Player 2 loses strength and vice versa The sum of the two strengths is always O.
Search Applied to Adversarial Games ? Initial state – Current board position (description of current game state) ? Operators – Legal moves a player can make ? Terminal nodes – Leaf nodes in the tree Indicate the game is over ? Utility function – Payoff function – Value of the outcome of a game – Example: tic tac toe, utility is -1, O, or 1 Game Trees ? Tic tac toe ? Two players, MAX and MIN ? Moves (ana levels) alternate Detween two players Minimax Algorithm ? Search the tree to the end ? Assign utility values to terminal nodes ? Find the best move for MAX (on MAX’S turn), assuming: – MAX will make the move that maximizes MAX’S utility – MIN will make the move that minimizes MAX”s utility ? Here, MAX should make the leftmost move ? Minimax applet Minimax Properties ? Complete if tree is finite ? Optimal if play against opponent with same strategy (utility function) ? Time complexity is O(bm) ? Space complexity is O(bm) (depth-first exploration) ? If we have 100 seconds to make a move – Can explore 104 nodes/second – Can consider 106 nodes / move ? Standard approach is – Apply a cutoff test (depth limit, quiescence) – Evaluate nodes at cutoff (evaluation function estimates desirability of position) Alpha-Beta Pruning ? Typically can only look 3-4 ply in allowable chess time ? Alpha-beta pruning simplifies search space without eliminating optimality – By applying common sense If one route allows queen to be captured and a better move is available – Then don’t search further down bad path – If one route would be bad for opponent, ignore that route also Max 71 No need to look here! Maintain [alpha, beta] window at each node during depth-first search alpha bound, change at max levels beta = upper bound, change at min levels = lower Alpha Beta Properties ? Pruning does not affect final result ? Good move ordering improves effectiveness of pruning ? With perfect ordering, time complexity is Goals To reduce the space complexity Game can be played one or two players Builds High-Level Game Contain Levels