Minimax - Alpha-Beta Pruning

a game is defined by:

• initial state - the environment setup
• operators - defines the legal moves
• terminal test - test when game is over
• utility or payoff function - which says who won, and by how much

Minimax

• in two-player games with perfect information, minimax algorithm can determine the best move for a player (assuming the opponent plays perfectly) by enumerating the entire game tree

Alpha Beta Pruning

• simulation
• does the same calculation as minimax, but is more efficient by pruning irrelevant branches of search tree

function minimax(node, depth, isMaximizingPlayer, alpha, beta):
 
    if node is a leaf node :
        return value of the node
    
    if isMaximizingPlayer :
        bestVal = -INFINITY 
        for each child node :
            value = minimax(node, depth+1, false, alpha, beta)
            bestVal = max( bestVal, value) 
            alpha = max( alpha, bestVal)
            if beta <= alpha:
                break
        return bestVal
 
    else :
        bestVal = +INFINITY 
        for each child node :
            value = minimax(node, depth+1, true, alpha, beta)
            bestVal = min( bestVal, value) 
            beta = min( beta, bestVal)
            if beta <= alpha:
                break
        return bestVal
 

Cut-Off and Evaluation Function

• usually not feasible to consider the whole game tree (even with alpha-beta pruning), so:
  • cut off the search at some point
  • apply an evaluation function to estimate the utility of the state