CMSC 471 Fall 2002 Class 7 8 Monday September 23 Wednesday September 25 Today s class Game playing Game trees Minimax Alpha beta pruning Adding randomness Deep Blue da chess champeen of da woild Game Playing Chapter 5 Some material adopted from notes by Charles R Dyer University of Wisconsin Madison Why study games Clear criteria for success Offer an opportunity to study problems involving hostile adversarial competing agents Historical reasons Fun Interesting hard problems which require minimal initial structure Games often define very large search spaces chess 35100 nodes in search tree 1040 legal states Typical case 2 person game Players alternate moves Zero sum one player s loss is the other s gain Perfect information both players have access to complete information about the state of the game No information is hidden from either player No chance e g using dice involved Examples Tic Tac Toe Checkers Chess Go Nim Othello Not Bridge Solitaire Backgammon How to play a game A way to play such a game is to Consider all the legal moves you can make Compute the new position resulting from each move Evaluate each resulting position and determine which is best Make that move Wait for your opponent to move and repeat Key problems are Representing the board Generating all legal next boards Evaluating a position Evaluation function Evaluation function or static evaluator is used to evaluate the goodness of a game position Contrast with heuristic search where the evaluation function was a non negative estimate of the cost from the start node to a goal and passing through the given node The zero sum assumption allows us to use a single evaluation function to describe the goodness of a board with respect to both players f n 0 position n good for me and bad for you f n 0 position n bad for me and good for you f n near 0 position n is a neutral position f n infinity win for me f n infinity win for you Evaluation function examples Example of an evaluation function for Tic Tac Toe f n of 3 lengths open for me of 3 lengths open for you where a 3 length is a complete row column or diagonal Alan Turing s function for chess f n w n b n where w n sum of the point value of white s pieces and b n sum of black s Most evaluation functions are specified as a weighted sum of position features f n w1 feat1 n w2 feat2 n wn featk n Example features for chess are piece count piece placement squares controlled etc Deep Blue has about 6000 features in its evaluation function Game trees Problem spaces for typical games are represented as trees Root node represents the current board configuration player must decide the best single move to make next Static evaluator function rates a board position f board real number with f 0 white me f 0 for black you Arcs represent the possible legal moves for a player If it is my turn to move then the root is labeled a MAX node otherwise it is labeled a MIN node indicating my opponent s turn Each level of the tree has nodes that are all MAX or all MIN nodes at level i are of the opposite kind from those at level i 1 Minimax procedure Create start node as a MAX node with current board configuration Expand nodes down to some depth a k a ply of lookahead in the game Apply the evaluation function at each of the leaf nodes Back up values for each of the non leaf nodes until a value is computed for the root node At MIN nodes the backed up value is the minimum of the values associated with its children At MAX nodes the backed up value is the maximum of the values associated with its children Pick the operator associated with the child node whose backed up value determined the value at the root Minimax Algorithm 2 1 2 2 7 1 Static evaluator value 8 2 7 1 8 2 1 2 7 1 8 2 This is the move selected by minimax 2 1 MAX MIN 2 7 1 8 Partial Game Tree for Tic Tac Toe f n 1 if the position is a win for X f n 1 if the position is a win for O f n 0 if the position is a draw Minimax Tree MAX node MIN node f value value computed by minimax Alpha beta pruning We can improve on the performance of the minimax algorithm through alpha beta pruning Basic idea If you have an idea that is surely bad don t take the time to see how truly awful it is Pat Winston MAX MIN 2 2 We don t need to compute the value at this node 1 MAX 2 7 1 No matter what it is it can t affect the value of the root node Alpha beta pruning Traverse the search tree in depth first order At each MAX node n alpha n maximum value found so far At each MIN node n beta n minimum value found so far Note The alpha values start at infinity and only increase while beta values start at infinity and only decrease Beta cutoff Given a MAX node n cut off the search below n i e don t generate or examine any more of n s children if alpha n beta i for some MIN node ancestor i of n Alpha cutoff stop searching below MIN node n if beta n alpha i for some MAX node ancestor i of n Alpha beta example 3 MAX 3 MIN 3 12 8 14 5 2 PRUNE 2 14 5 2 2 Alpha beta algorithm function MAX VALUE state game alpha beta alpha best MAX so far beta best MIN if CUTOFF TEST state then return EVAL state for each s in SUCCESSORS state do alpha MAX alpha MIN VALUE state game alpha beta if alpha beta then return beta end return alpha function MIN VALUE state game alpha beta if CUTOFF TEST state then return EVAL state for each s in SUCCESSORS state do beta MIN beta MAX VALUE s game alpha beta if beta alpha then return alpha end return beta Effectiveness of alpha beta Alpha beta is guaranteed to compute the same value for the root node as computed by minimax with less or equal computation Worst case no pruning examining b d leaf nodes where each node has b children and a d ply search is performed Best case examine only 2b d 2 leaf nodes Result is you can search twice as deep as minimax Best case is when each player s best move is the first alternative generated In Deep Blue they found empirically that alpha beta pruning meant that the average branching factor at each node was about 6 instead of about 35 Games of chance Backgammon is a two player game with uncertainty Players roll dice to determine what moves to make White has just rolled 5 and 6 and has four legal …