Alpha–Beta Pruning

Minimax, also called the minimax algorithm, is an algorithm that minimizes potential loss in the worst-case (that is, maximum-loss) situation. This page briefly introduces the Minimax algorithm and Alpha–Beta pruning.

Minimax Algorithm

Minimax, also called the minimax algorithm, is an algorithm that minimizes potential loss in the worst-case (that is, maximum-loss) situation.

Process

In a two-player zero-sum game with a determined state, adversarial search is often needed to construct a search tree in which every node is a definite state. Odd levels correspond to the first player, and even levels correspond to the opponent. Each leaf node in the search tree is assigned a score; a larger score means a greater chance of our side winning. Our side seeks a larger chance of winning, while the opponent tries to reduce our side's chance of winning. On the search tree, this means that nodes at odd levels (our nodes) always choose the child state with the greatest chance of winning, while nodes at even levels (the opponent's nodes) always choose the child state with the smallest chance of winning for our side.

The Minimax algorithm traverses the search tree from top to bottom and updates the answer with subtree information while backtracking, finally obtaining its value of the root node—the maximum score our side can obtain when both sides adopt optimal strategies.

Example

Consider a simple example.

Call our side MAX and the opponent MIN, as shown below:

For the following position, suppose the search proceeds from left to right, and its value of the root node represents our chance of winning:

We should choose the middle route. If the left route is chosen, its worst-case chance of winning is $3$; if the middle route is chosen, its worst-case chance is $15$; if the right route is chosen, its worst-case chance is $1$. Although the right route may have a chance of winning of $22$, a sufficiently rational opponent will leave our side with only a chance of $1$. Thus, after weighing the options, the middle route is clearly better.

In fact, when examining the right route, once a possible chance of winning of $1$ is found, there is no need to examine the branches with chances of winning of $12$, $20$, and $22$. Compared with the chances of winning on the two routes to the left, it is already certain that the right route is not the best.

The naive Minimax algorithm often needs to construct a huge search tree, making both its time and space complexity unacceptable. Alpha–Beta pruning is a method that uses the upper and lower bounds of the scores of both sides at each node in the search tree to prune and optimize Minimax.

Note that the meaning of its value at each node of the search tree differs between problems: it may be a heuristic value, a score, a probability of winning, and so on. For convenience, the following text uniformly calls it a score.

Alpha–Beta Pruning

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

Process

In the Minimax algorithm, if the scores of all children of a node are known, the score of that node can be calculated: a MAX node takes the maximum score, while a MIN node takes the minimum score.

When the search has reached a node but is not yet complete, its score cannot be calculated, but the range of scores that both sides can obtain among the nodes searched so far can be calculated. During the search, maintain two variables, $\alpha$ and $\beta$, representing, among all nodes already searched when the game reaches this node, the lower and upper bounds of the scores that the Alpha player (the side seeking the maximum score) and Beta player (the side seeking the minimum score) can guarantee, respectively.

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 children to raise the lower bound $\alpha$. However, if some search results in $\alpha\ge\beta$, this node cannot occur in an actual game: once a node is reached, the Alpha player can guarantee a score of at least $\alpha$; but the Beta player already knows a strategy (deviating from the current path) that guarantees a score no greater than $\beta\le\alpha$, so Beta naturally will not allow the game to develop to the current node. Similarly, if the current node is a MIN node and, after searching one of its children, $\beta\le\alpha$ holds at that node, there is no need to continue searching its other children, because the Alpha player will not allow the game to enter the current node. In summary, when $\alpha \geq \beta$, the remaining branches of a node need not be searched (that is, pruning can be performed). Note that pruning is also required when $\alpha = \beta$, because no better result is possible, although a worse result may be possible.

During the search, it is unnecessary to maintain node scores; maintaining only $\alpha$ and $\beta$ is sufficient. Initially, set $\alpha=-\infty,~\beta=+\infty$. When searching downward, pass the information of $\alpha$ and $\beta$ along with the search to record the alternatives of the two players.

When a child has been searched, the information at the current node must be updated. Suppose the current node $X$ is a MAX node and its child $Y$ has just been searched. The $\beta$ value at node $X$ does not change; only $\alpha$ needs to be updated with the maximum of its current value and the score of child $Y$. If child $Y$ is a leaf node, directly use child $Y$'s score to update $\alpha$ at $X$; otherwise, only the $\beta$ value of $Y$ needs to be used to update $\alpha$ at $X$. There are three possibilities:

1. The $\beta$ value of child $Y$ lies strictly between the $\alpha$ and $\beta$ values of node $X$. Since $Y$ inherited the $\alpha$ value of $X$ and does not update it, having $\beta > \alpha$ after the search of $Y$ is complete means that no pruning occurred while searching $Y$. The final $\beta$ value of $Y$ equals the smaller of the $\beta$ value inherited from $X$ and the scores of all children of $Y$. Since this minimum is strictly less than the $\beta$ value of $X$, it must be the minimum score among all children of $Y$. Therefore, as a MIN node, the score of $Y$ is this $\beta$ value. It is valid to use it to update the $\alpha$ value of $X$.
2. The $\beta$ value of child $Y$ equals the $\beta$ value of node $X$. As described above, this means that all children of $Y$ have scores no less than the $\beta$ value of $X$. This further means that the Beta player will not allow the game to enter node $X$: if the Alpha player chooses child $Y$, Beta cannot obtain a score lower than $\beta$. Thus, using the $\beta$ value of $Y$ to update the $\alpha$ value of $X$ makes $\alpha=\beta$ at $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 $X$—to update the $\alpha$ value of $X$.
3. The $\beta$ value of child $Y$ is less than or equal to the $\alpha$ value of $X$. In this case, $Y$ triggered the pruning condition, so child $Y$'s actual score is no greater than its $\beta$ value and certainly no greater than the $\alpha$ value of $X$. Using the actual score of $Y$ to update $\alpha$ at $X$ would not change $\alpha$. This has the same effect as using the $\beta$ value of $Y$ to update $\alpha$ at $X$.

This analysis shows that after a child has been searched, $\alpha$ (or $\beta$) accurately records the actual score of that child as a MAX node (or MIN node) only in the first case. In the other cases, although it may not be the exact score, it provides enough information to ensure that pruning is performed correctly and therefore does not affect the score recorded at the root.

Example

This section analyzes an example to show how the $\alpha$ and $\beta$ values at each node are updated during the search. The scores at the involved nodes are also calculated along the way. Thus, the relationship between the actual score at each node and its recorded $\alpha$ and $\beta$ values can be observed. However, note that an implementation of this algorithm does not calculate the actual scores of these nodes.

For the following position, suppose the search proceeds from left to right:

Initially, set $\alpha = -\infty,~\beta = +\infty$, and pass this information down along the search path.

When node A is reached, because the score of its left child is $3$ and A is a MIN node seeking a small score, its $\beta$ value is changed to $3$, since $3$ is less than the current $\beta$ value ($\beta = +\infty$). The score of A's right child is then $17$, but A's $\beta$ value is not changed because $17$ is greater than the current $\beta$ value ($\beta = 3$). At this point all children of A have been searched, so A's score can be calculated as $3$, consistent with the $\beta$ value recorded at a node (case 1 above).

Node A is a child of node B. After calculating A's score, B's $\alpha$ and $\beta$ values can be updated. Since B is a MAX node seeking a large score, its $\alpha$ value is changed to $3$, because the $\beta$ value at A ($\beta=3$) is greater than the current $\alpha$ value ($\alpha = -\infty$). Next, search B's right child C and pass B's $\alpha$ and $\beta$ values to C.

For node C, the score of its left child is $2$ and C is a MIN node, so its $\beta$ value is changed to $2$. Now $\alpha \geq \beta$, so C's remaining children need not be searched, because it can be determined that the Alpha player will not allow the game to develop to C. C is a MIN node, so its score is $2$, no greater than the recorded $\beta$ value (case 3 above). Since all children of B have been searched, B's score can be calculated as $3$, equal to its recorded $\alpha$ value (case 1 above).

After B's score is calculated, B is a child of D, so D's $\alpha$ and $\beta$ values can be updated. Since D is a MIN node, its $\beta$ value is changed to $3$. D then passes $\alpha$ and $\beta$ to E, which passes them on to F. F has only one child with score $15$. Since $15$ is greater than the current $\beta$ value and F is a MIN node, its $\beta$ value is not updated. F's score can then be calculated as $15$, greater than the recorded $\beta$ value (case 2 above).

After F's score is calculated, F is a child of E, so E's $\alpha$ and $\beta$ values can be updated. E is a MAX node, so its $\alpha$ value is updated; now $\alpha \geq \beta$, so E's remaining branches (that is, node G) can be pruned. E is a MAX node, so set its score to $15$, strictly greater than its recorded $\alpha$ value (case 3 above). Use E's $\alpha$ value to update D's $\beta$ value, which remains $3$. At this point all children of D have been searched, so D's score can be calculated as $3$, equal to its recorded $\beta$ value (case 1 above).

After D's score is calculated, D is a child of H, so H's $\alpha$ and $\beta$ values can be updated. H is a MAX node, so update $\alpha$. Then, in search order, pass H's $\alpha$ and $\beta$ values to I, J, and K in turn. For K, the score of its left child is $2$, and K is a MIN node, so update $\beta$. Now $\alpha \geq \beta$, and K's remaining branches can be pruned. Then set K's score to $2$, less than or equal to its recorded $\beta$ value (case 3 above).

After K's score is calculated, K is a child of J, so J's $\alpha$ and $\beta$ values can be updated. J is a MAX node, so update $\alpha$. However, because K's score is less than $\alpha$, J's $\alpha$ value remains $3$. Then pass J's $\alpha$ and $\beta$ values to L. Since L is a MIN node, update $\beta = 3$. Now $\alpha \geq \beta$, so L's remaining branches can be pruned. Since L has no remaining branches, no actual pruning occurs here. Then set L's score to $3$, less than or equal to its recorded $\beta$ value (case 3 above).

After L's score is calculated, L is a child of J, so J's $\alpha$ and $\beta$ values can be updated. J is a MAX node, so update $\alpha$. However, because L's score is less than or equal to $\alpha$, J's $\alpha$ value remains $3$. At this point all children of J have been searched, so J's score can be calculated as $3$, equal to its recorded $\alpha$ value (case 2 above).

After J's score is calculated, J is a child of I, so I's $\alpha$ and $\beta$ values can be updated. I is a MIN node, so update $\beta$. Now $\alpha \geq \beta$, and I's remaining branches can be pruned. It is worth noting that because the right child exists, I's actual score is $2$, less than the recorded $\beta$ value (case 3 above).

After I's score is calculated, I is a child of H, so H's $\alpha$ and $\beta$ values can be updated. H is a MAX node, so update $\alpha$. However, because I's score is less than or equal to $\alpha$, H's $\alpha$ value remains $3$. At this point all children of H have been searched, so H's score can be calculated as $3$, equal to its recorded $\alpha$ value (case 1 above).

This is the final result.

Implementation

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

• Minimax Algorithm - Wikipedia
• Alpha–beta pruning - Wikipedia

This article partially quotes the blog post An In-Depth Explanation of the Minimax Algorithm and Alpha–Beta Pruning _Wenjianmuran, under the CC 4.0 BY-SA license. The content has been modified.