Skip to content

Alpha–Beta Pruning

This page provides a brief introduction to the Minimax algorithm and Alpha–Beta pruning.

Minimax Algorithm

The Minimax algorithm, also known as the minimax algorithm, is an algorithm that minimizes the potential loss in the worst-case scenario (i.e., maximum loss).

Process

In deterministic two-player zero-sum games, adversarial search is often required, constructing a search tree where each node represents a specific game state. Odd-numbered layers represent the player's turn (maximizing player), while even-numbered layers represent the opponent's turn (minimizing player). Each leaf node in the search tree is assigned an evaluation value, where a higher value indicates a greater advantage for the player. The player aims to maximize their advantage, while the opponent seeks to minimize it. In the search tree, this is reflected as follows: odd-layer nodes (player nodes) always choose the child node state with the highest advantage, while even-layer nodes (opponent nodes) always choose the child node state with the lowest (player) advantage.

In the Minimax algorithm, the search tree is traversed from top to bottom. During backtracking, subtree information is used to update the answer, ultimately obtaining the value of the root node—this is the maximum score the player can achieve when both sides adopt optimal strategies.

Example

Consider a simple example.

Let the player be MAX and the opponent be MIN, as illustrated below:

For instance, given the following game state, assuming a left-to-right search, the root node's value represents the player's advantage:

The player should choose the middle path. Because if the left path is chosen, the worst-case advantage is \(3\); if the middle path is chosen, the worst-case advantage is \(15\); if the right path is chosen, the worst-case advantage is \(1\). Although the right path may offer an advantage of \(22\), a sufficiently rational opponent will ensure the player only has an advantage of \(1\). After weighing the options, it is clear that the middle path is superior.

In practice, when examining the right path, there is no need to explore branches with advantages of \(12\), \(20\), or \(22\) after discovering that the advantage could be as low as \(1\). Compared to the advantages of the left two paths, it is already certain that the right path is not the best.

The naive Minimax algorithm often requires constructing a massive search tree, making its time and space complexity unacceptable. Alpha–Beta pruning is a method that optimizes Minimax by pruning the search tree using the upper and lower bounds of scores for both players at each node.

It is important to note that for different problems, the value at each node of the search tree may have different meanings, such as evaluation, score, winning probability, etc. For convenience, the term "score" will be used uniformly in the following discussion.

Alpha–Beta Pruning

Alpha–Beta pruning is a search pruning technique for the Minimax algorithm.

Process

In the Minimax algorithm, if the scores of all child nodes of a node are known, the score of that node can be calculated: for a MAX node, take the maximum score; for a MIN node, take the minimum score.

When the search reaches a node but is not yet complete, although the node's score cannot be calculated, the range of scores for both players among the nodes already searched can be determined. During the search, two variables, \(\alpha\) and \(\beta\), are maintained, representing the lower and upper bounds of the scores that the Alpha player (the one seeking the maximum score) and the Beta player (the one seeking the minimum score) can guarantee, respectively, considering all nodes already searched when the game reaches that node.

The pruning strategy of Alpha–Beta pruning depends on the values of \(\alpha\) and \(\beta\) when searching the current node. If the current node is a MAX node, Alpha can continue searching its child nodes to raise the lower bound \(\alpha\). However, if after some search, \(\alpha \ge \beta\) already holds, then this node cannot appear in a game: as long as the game reaches this node, the Alpha player can guarantee a score of at least \(\alpha\); but the Beta player already knows there exists a strategy (deviating from the current path) that can guarantee a score no higher than \(\beta \le \alpha\). Therefore, the Beta player will naturally not allow the game to reach the current node. Similarly, if the current node is a MIN node, and after searching one of its child nodes, it is found that \(\beta \le \alpha\) holds at that node, then there is no need to continue searching other child nodes, because the Alpha player will not allow the game to enter the current node. Summarizing both cases, it can be observed that when \(\alpha \geq \beta\), the remaining branches of the node need not be searched further (i.e., pruning can be performed). Note that when \(\alpha = \beta\), pruning is also necessary because no better result can be achieved, though worse results may exist.

During the search, there is no need to maintain node scores; only \(\alpha\) and \(\beta\) need to be maintained. Initially, set \(\alpha=-\infty\) and \(\beta=+\infty\). When searching downward, the information of \(\alpha\) and \(\beta\) must be passed down to record the alternative strategies of the two players.

When a child node is fully searched, the information at the current node needs to be updated. Suppose the current node \(X\) is a MAX node, and its child node \(Y\) has just been searched. Then, the \(\beta\) value at node \(X\) will not change; only the \(\alpha\) value needs to be updated to the maximum of its current value and the score of child node \(Y\). If child node \(Y\) is a leaf node, directly use the score of child node \(Y\) to update the \(\alpha\) value at node \(X\); otherwise, simply use the \(\beta\) value of child node \(Y\) to update the \(\alpha\) value at node \(X\). At this point, there are three possibilities:

  1. The \(\beta\) value of child node \(Y\) lies strictly between the \(\alpha\) and \(\beta\) values of node \(X\). Since child node \(Y\) inherits the \(\alpha\) value of node \(X\) and does not update it, after searching child node \(Y\), \(\beta > \alpha\) still holds, indicating that no pruning occurred during the search of child node \(Y\). The final \(\beta\) value of child node \(Y\) equals the minimum of the inherited \(\beta\) value from node \(X\) and the scores of all its (child node \(Y\)'s) child nodes. Since this minimum is strictly less than the \(\beta\) value of node \(X\), it must be the minimum score among all child nodes of child node \(Y\). Therefore, as a MIN node, the score of child node \(Y\) is this \(\beta\) value. Using it to update the \(\alpha\) value of node \(X\) is reasonable.
  2. The \(\beta\) value of child node \(Y\) equals the \(\beta\) value of node \(X\). As mentioned above, this indicates that the scores of all child nodes of child node \(Y\) are not less than the \(\beta\) value of node \(X\). This further implies that the Beta player will not allow the game to reach node \(X\): because if the Alpha player chooses child node \(Y\), the Beta player cannot achieve a score lower than \(\beta\). Therefore, using the \(\beta\) value of child node \(Y\) to update the \(\alpha\) value of node \(X\) is to make \(\alpha = \beta\) at node \(X\), triggering the pruning condition. Its effect is the same as using the actual score at \(Y\)—a number greater than or equal to the \(\beta\) value at node \(X\)—to update the \(\alpha\) value of node \(X\).
  3. The \(\beta\) value of child node \(Y\) is less than or equal to the \(\alpha\) value of node \(X\). At this point, child node \(Y\) triggers the pruning condition; its actual score will not exceed the \(\beta\) value of child node \(Y\), let alone the \(\alpha\) value of node \(X\). Using the actual score of child node \(Y\) to update the \(\alpha\) value of node \(X\) will not change the \(\alpha\) value. This has the same effect as using the \(\beta\) value of child node \(Y\) to update the \(\alpha\) value of node \(X\).

This analysis shows that when a child node is fully searched, only in the first case does \(\alpha\) (or \(\beta\)) accurately record the actual score of that child node as a MAX node (or MIN node). In other cases, although it may not be the exact score, the information it provides is sufficient to ensure the correctness of pruning, thus not affecting the score recorded at the root node.

Example

This section analyzes an example to demonstrate how to update the \(\alpha\) and \(\beta\) values at each node during the search. In the process, the scores of the involved nodes are also calculated. This allows observation of the relationship between the actual score at each node and the recorded \(\alpha\) and \(\beta\) values. However, note that when implementing this algorithm, the actual scores of these nodes are not computed.

For the following game state, assume a left-to-right search:

Initialize \(\alpha = -\infty\) and \(\beta = +\infty\), and pass this information down the search path.

When searching node A, since the score of the left child is \(3\), and node A is a MIN node trying to find the move with the smallest score, update the \(\beta\) value to \(3\), because \(3\) is less than the current \(\beta\) value (\(\beta = +\infty\)). Then, the score of the right child of node A is \(17\). At this point, do not update the \(\beta\) value of node A because \(17\) is greater than the current \(\beta\) value (\(\beta = 3\)). Now, all child nodes of node A have been searched, and the score of node A can be calculated as \(3\), which matches the recorded \(\beta\) value at this node (case 1 from earlier).

Node A is a child of node B. After calculating the score of node A, update the \(\alpha\) and \(\beta\) values of node B. Since node B is a MAX node trying to find the move with the largest score, update the \(\alpha\) value to \(3\), because the \(\beta\) value at child node A (\(\beta=3\)) is greater than the current \(\alpha\) value (\(\alpha = -\infty\)). Then, search the right child node C of node B and pass the \(\alpha\) and \(\beta\) values of node B to node C.

For node C, since the score of the left child is \(2\), and node C is a MIN node, update the \(\beta\) value to \(2\). At this point, \(\alpha \geq \beta\), so the remaining child nodes of node C need not be searched, as it can be determined that the Alpha player will not allow the game to reach node C. Node C is a MIN node, and its score is \(2\), which does not exceed the recorded \(\beta\) value (case 3 from earlier). Since all child nodes of node B have been searched, the score of node B can be calculated as \(3\), which matches the recorded \(\alpha\) value (case 1 from earlier).

After calculating the score of node B, node B is a child of node D, so update the \(\alpha\) and \(\beta\) values of node D. Since node D is a MIN node, update the \(\beta\) value to \(3\). Then, node D passes its \(\alpha\) and \(\beta\) values to node E, and node E passes them to node F. For node F, it has only one child with a score of \(15\). Since \(15\) is greater than the current \(\beta\) value, and node F is a MIN node, its \(\beta\) value is not updated. Then, the score of node F can be calculated as \(15\), which is greater than the recorded \(\beta\) value (case 2 from earlier).

After calculating the score of node F, node F is a child of node E, so update the \(\alpha\) and \(\beta\) values of node E. Node E is a MAX node, so update its \(\alpha\) value. Now, \(\alpha \geq \beta\), so the remaining branches of node E (i.e., node G) can be pruned. Then, node E is a MAX node, and its score is set to \(15\), which is strictly greater than the recorded \(\alpha\) value (case 3 from earlier). Use the \(\alpha\) value of node E to update the \(\beta\) value of node D, which remains \(3\). Now, all child nodes of node D have been searched, and the score of node D can be calculated as \(3\), which equals the recorded \(\beta\) value (case 1 from earlier).

After calculating the score of node D, node D is a child of node H, so update the \(\alpha\) and \(\beta\) values of node H. Node H is a MAX node, so update its \(\alpha\) value. Then, following the search order, pass the \(\alpha\) and \(\beta\) values of node H to nodes I, J, and K. For node K, the score of its left child is \(2\), and node K is a MIN node, so update its \(\beta\) value. Now, \(\alpha \geq \beta\), so the remaining branches of node K can be pruned. Then, set the score of node K to \(2\), which is less than or equal to the recorded \(\beta\) value (case 3 from earlier).

After calculating the score of node K, node K is a child of node J, so update the \(\alpha\) and \(\beta\) values of node J. Node J is a MAX node, so update its \(\alpha\) value. However, since the score of node K is less than \(\alpha\), the \(\alpha\) value of node J remains \(3\). Then, pass the \(\alpha\) and \(\beta\) values of node J to node L. Since node L is a MIN node, update its \(\beta\) value to \(3\). Now, \(\alpha \geq \beta\), so the remaining branches of node L can be pruned. Since node L has no remaining branches, no actual pruning occurs here. Then, set the score of node L to \(3\), which is less than or equal to the recorded \(\beta\) value (case 3 from earlier).

After calculating the score of node L, node L is a child of node J, so update the \(\alpha\) and \(\beta\) values of node J. Node J is a MAX node, so update its \(\alpha\) value. However, since the score of node L is less than or equal to \(\alpha\), the \(\alpha\) value of node J remains \(3\). Now, all child nodes of node J have been searched, and the score of node J can be calculated as \(3\), which equals the recorded \(\alpha\) value (case 2 from earlier).

After calculating the score of node J, node J is a child of node I, so update the \(\alpha\) and \(\beta\) values of node I. Node I is a MIN node, so update its \(\beta\) value. Now, \(\alpha \geq \beta\), so the remaining branches of node I can be pruned. It is worth noting that due to the existence of the right child, the actual score of node I is \(2\), which is less than the recorded \(\beta\) value (case 3 from earlier).

After calculating the score of node I, node I is a child of node H, so update the \(\alpha\) and \(\beta\) values of node H. Node H is a MAX node, so update its \(\alpha\) value. However, since the score of node I is less than or equal to \(\alpha\), the \(\alpha\) value of node H remains \(3\). Now, all child nodes of node H have been searched, and the score of node H can be calculated as \(3\), which equals the recorded \(\alpha\) value (case 1 from earlier).

This is the final result.

Implementation

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int alpha_beta(int u, int alph, int beta, bool is_max) {
  if (!son_num[u]) return val[u];
  if (is_max) {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      alph = max(alph, alpha_beta(d, alph, beta, !is_max));
      if (alph >= beta) break;
    }
    return alph;
  } else {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      beta = min(beta, alpha_beta(d, alph, beta, !is_max));
      if (alph >= beta) break;
    }
    return beta;
  }
}

References and Notes

Part of this article is adapted from the blog post 详解 Minimax 算法与α-β剪枝_文剑木然, following the CC 4.0 BY-SA license. The content has been modified.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用