Tic tac toe Essay Example

Tic tac toe Essay Example Tic tac toe Paper Tic tac toe Paper 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 33 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 MAXS turn), assuming: MAX will make the move that maximizes MAXS utility MIN will make the move that minimizes MAXs 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/seco nd 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 dont 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