Alpha-Beta

Alpha-Beta search is an advanced version of the Minimax algorithm, where the best possible score in a game after players get to move a certain number of times is determined. alpha and beta are scoring bounds to safely prune subtrees in a search. Like Minimax, the algorithm is only applicable in 2-player games, where the gain of player A is exactly the loss of player B.

Implementation

maxNode(depth, alpha, beta) {
    // Leaf nodes are evaluated
    if (depth == 0)
        return evaluation()

    // Maximize score for all possible moves
    for (move : generateMoves()) {
        playMove(move)
        score = minNode(depth - 1)
        takebackMove(move)

        if (alpha >= beta)
            return beta

        // Keep track of best (highest) score the max player is assured of
        if (score > alpha)
            alpha = score
    }
    return alpha
}

minNode(depth, alpha, beta) {
    // Leaf nodes are evaluated
    if (depth == 0)
        return evaluation()

    // Minimize score for all possible moves
    for (move : generateMoves()) {
        playMove(move)
        score = maxNode(depth - 1)
        takebackMove(move)

        if (score <= alpha)
            return alpha

        // Keep track of best (lowest) score the min player is assured of
        if (score < beta)
            beta = score
    }
    return beta
}

Description

The Alpha-Beta algorithm searches a game tree in a recursive depth first search fashion, just like Minimax. While player A tries to maximize his score, player B tries to minimize the score, since the loss of a player is the other one's gain. After all positions have been considered, the best score for the player to move is propagated back to the root.

The function takes additional parameters alpha and beta to keep track of the best score each player is assured of. Initially, alpha is set to $-\infty$ acting as a lower bound for the maximizing player and beta to $\infty$ acting as the upper bound for the minimizing player. Whenever a player can improve his assured score, the corresponding bound is updated and the alpha-beta bounds are coming closer. If a move turns out to be worse than the known bound, it can safely be pruned since there already exists a move that scores better and will be propagated back instead. The maximizing player prunes moves that score below the lower bound alpha and the minimizing player prunes moves that score above beta.

Finding a good first move to refute other moves early in a position is key to further improve the algorithm. Therefore, move ordering should be considered for fast game tree traversal.

Usage

The Alpha-Beta algorithm dervives from Minimax and is used in similar applications like Chess, Go or Shogi. It acts as artifial intelligfence in order to play the most promising moves and in the game. However, most implementations rely on a modified version called Negamax to avoid redundant code.

The initial call to start the tree search depends on the player to move. The minimizing player calls min(depth, -INFINITY, INFINITY) while the maximizing player finds his best score with max(depth, -INFINITY, INFINITY).

Complexity