Minimax and Alpha Beta Pruning

Algorithm to calculate the best future move

function(position, depth, maximizingPlayer) {
    if depth == 0 or game over in position
        return state evaluation of position
    if maximizingPlayer # white chess piece
        maxEval = -infinity
        for each child of position
            eval = minimax(child, depth - 1, false)
            maxEval = max(maxEval, eval)
        return maxEval
    else
        minEval = +infinity
        for each child of position
            eval = minimax(child, depth - 1, true)
        return maxEval
}

Some moves can waste computation

Alpha Beta Pruning

function minimax(position, depth, alpha, beta, maximizingPlayer)
    if depth == 0 or game over in position
        return static evaluation of position
    if maximizingPlayer
        maxEval = -infinity
        for each child of position
            eval = minimax(child, depth - 1, alpha, beta, false)
            maxEval = max(maxEval, evam)
            alpha = max(alpha, maxEval)
        return maxEval
    else 
        minEval = +infinity
        for each child of position
            eval = minimax(child, depth - 1, alpha, beta, true)
            minEval = min(minEval, eval)
        return minEval