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 acting as a lower bound for the maximizing player and beta
to 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
Time
For a branching factor and depth :
Space
For a maximum number of child nodes for all nodes and depth :