Intuition for alpha & beta in game tree search

2023-03-06

There’s a wealth of useful information online about the alpha-beta search algorithm - the more efficient and no-less-accurate improvement on minimax for solving zero-sum, perfect information games like chess. Despite plenty of material, I’ve found most of it lacking in conveying a decent intuition on what the eponymous values alpha and beta actually represent in the algorithm itself. This is a problem because the many heuristic improvements layered on top of simple alpha-beta in a strong game-playing program tend to require a proper grasp on these concepts. This note attempts to record some useful hard-won intuition.

For the sake of completeness, I’ve also included quite a detailed introduction to minimax and alphabeta. Scroll down to the Appendix if you need to get up to speed on these first.

Alpha and beta

Almost every real implementation of minimax or alpha-beta uses the “negamax framework”: a single function that calls itself recursively and uses minus signs at the call sites to flip between the two players’ perspectives. It’s the tidiest way to write the algorithm, and there’s a version in the Appendix. For building intuition, we avoid that framing, and maintain a single coherent view of node values throughout. In all the discussion that follows, both players inhabit a single, shared number line: Max always trying to make the score as large as possible, Min always trying to make it as small as possible. I’ll call the players Max and Min throughout. Here’s a reference implementation in this style:

function alpha_beta_max(alpha, beta, depth_left) {
  if (depth_left == 0) return evaluate();

  for (move in legal_moves) {
    make_move(move);
    score = alpha_beta_min(alpha, beta, depth_left - 1);
    unmake_move(move);

    if (score >= beta) return beta; // fail-hard beta-cutoff

    if (score > alpha) alpha = score; // alpha tracks Max's best so far
  }

  return alpha;
}

The mirror image alpha_beta_min is shown in the appendix (where Max maximizes by ratcheting alpha up as he finds better moves, Min minimizes, ratcheting beta downwards).

The key line in the snippet above is the early return if (score >= beta). The whole schtick here is to find “cutoffs” - early-exits from that loop over all available moves. Achieving such an early exit can cut massive subtrees¹1. Since chess has a large branching factor and we want to search as deeply as we can, a cutoff at a shallow ply can remove tens of millions of nodes that it was always going to be uninformative to search. out of the search and lead to gigantic speedups with no loss of accuracy at all.

The first thing to notice is that alpha plays a role very much akin to max in the minimax algorithm. As we iterate through the possibilities, it tracks what the best move from Max’s perspective has been so far.

Step through the search above. Squares are Max nodes, circles are Min nodes; the blue (α, β) label shows each node’s live window. Notice some branches get ‘pruned’.

Looking at the diagram above, let’s imagine running alpha_beta_max at the root node, which eventually must return the true value, $6$ , for the whole tree.

Let’s think through how the values of alpha and beta change as the iteration proceeds over the three possible moves from left to right. I’ll write the values as a tuple $(\alpha, \beta)$ for ease. At the top of the function, this being a root node, we have $(-\infty, \infty)$ . First, we try the leftmost child. This subtree eventually returns us $3$ (step 15), which exceeds the current value of alpha, so we update the range to $(3, \infty)$ . Next, the second move is examined and this ends up returning $6$ (step 29), which again beats the current alpha. We update to $(6, \infty)$ .

Now let’s consider what happens when we drop down into the third possible move. This is a Min node, and it inherits the window $(6, \infty)$ we’ve arrived at — Max’s guarantee of $6$ from higher up travels down into it unchanged. The first move Min looks at returns $5$ , and that immediately triggers a cutoff (step 37). Here’s why: $5$ is no better for Max than the $6$ he can already provably secure above (in fact it’s worse), and since Min is minimizing, this node can only slide further below $5$ as she examines more moves. So Max is never going to choose to come down into this node — he’ll take his $6$ elsewhere. There’s no point Min refining a value Max will certainly discard, so we can save time and return early. Because the trigger was a move landing at or below alpha, this one is called an “alpha-cutoff”.

So the meaning of alpha in the algorithm becomes clear:

Alpha: the best score Max can already guarantee himself somewhere higher up the tree. As I (Min) search this node its value only falls, and the moment it lands at alpha or below I can stop: I’ve found a line at least as good for me as that alpha, and Max — who does the choosing higher up — will never come down here. He’ll take his guaranteed alpha elsewhere rather than let me have something better. No point searching on.

And beta is the equivalent tracker of Min’s best available option so far. For example, at step 11, Max has been handed beta=3 but proves that his node is going to be worth at least $7$ . So there’s no point searching the next child, since Min would never choose to descend to this node anyway.

Beta: the best score Min can already guarantee herself somewhere higher up the tree. As I (Max) search this node its value only increases, and the moment it lands at beta or above I can stop: I’ve found a line at least as good for me as that beta, and Min — who does the choosing higher up — will never come down here. She’ll take her guaranteed beta elsewhere rather than let me have something better. No point searching on.

So alpha and beta have a global interpretation. alpha is the best outcome Max has pinned down anywhere in the tree searched so far — not just in this node — and it only ever rises; beta is the mirror, the best Min has pinned down so far, only ever falling. This is exactly how alpha_beta improves on plain minimax: there, each node tracks only its own best outcome in a local max (or min), whereas here every node inherits full knowledge of what each player can already force elsewhere, and prunes accordingly.

The two bounds therefore combine to produce a window on the shared number line that narrows as the search proceeds — beta pressing down from above as Min finds good replies, alpha pushing up from below as Max does. This narrowing-window picture is exactly the convention we’ve been using all along — Max and Min sharing one number line. Be aware that in the negamax framework used in most real-world code (see Appendix), the window is somewhat harder to visualise, because the values keep swapping places and being negated at every ply. All that’s happening is that, in any given node, the player to move is deemed to be maximising, and we achieve this by judicious use of minus signs.

Move ordering

How much value the alpha-beta algorithm delivers is closely tied to how good your ‘move ordering’ is. Those juicy cutoffs we seek happen exactly when you find a move strong enough to breach the window. So the order in which you try the moves at a node governs how much you get to prune. Try the best move first and its siblings become quick cutoffs. Try it last and you’ll end up searching everything as if you’re stuck on plain old minimax. With perfect ordering the effect is dramatic — alpha-beta examines on the order of the square root of the nodes minimax would, which is to say it can search roughly twice as deep for the same cost.

Of course, there’s a conspicuous circularity here: the whole point of searching is to find out how good the moves are, yet we’d like them sorted by strength before we start. What actually happens is that engines lean on fast heuristics to try plausible moves first. The alpha-beta search becomes a kind of proof layer on top of all the heuristic techniques you adopt to try and guess the best move with minimal effort. Much of the art of chess program resides in these heuristics.

Some vocabulary

There’s a clutch of frequently used vocabulary associated with the alpha-beta algorithm which is much easier to understand now we have a more intuitive grasp over the fundamentals. Here’s a little glossary:

Principal Variation - the single thread of moves through the game tree which represents optimal play by both sides. This is effectively the desired output from minimax, alphabeta etc. There is an algorithm called Principal Variation Search (PVS), which attempts to be an even more efficient improvement on alpha-beta, by focusing on the Principal Variation and searching other nodes with a deliberately narrow window, promoting faster cutoffs. A detailed discussion of this algorithm is outside the scope of this note, but there’s more on Wikipedia and Chess Programming Wiki.
Fail-high - an alternative name for a beta-cutoff. Represents a situation where we discover that a node is too good for the player whose turn it is, meaning we can eschew searching further moves. On the minimizing player’s turn the mirror event is an alpha-cutoff instead (as with the third move in our first diagram); the names “fail-high” and “fail-low” are handy precisely because they stay neutral between the two framings.
Fail-low - this refers to the opposite scenario. We sometimes search through every move at a node and discover that none of them improves upon alpha. This node now fails to be part of the Principal Variation, but we had to do more searching to learn that. Since the value of this node failed to improve upon alpha, it’s less good than some other move we already have elsewhere in the ancestor tree. Dropping down into this node from the parent is very good for our opponent - in fact, we have a better choice elsewhere so there will be a cutoff in our parent node as soon as we return.
Fail-hard - looking at the pseudocode alpha-beta algorithm above, we can see that if a node fails to improve on alpha, we actually return alpha rather than the best available move (which was something less than alpha). This is known as a “fail-hard framework”.
Fail-soft - in fact, you can make a small change to the algorithm and use a local max variable to track the largest value of the node, and return that instead (despite it possibly being less than alpha). This has no effect on the overall accuracy or output of the algorithm. A discussion on TalkChess goes over some of the pros and cons.
Node Types - the nodes of a game tree can be categorised into three types based on their behaviour during execution of the alpha-beta search algorithm. Here’s a quick summary, focusing on intuition, for what each node type means. Note that these terms can be applied both to the idea of what the node is expected (or hoped) to be before searching it, and what it turns out to be after the search returns. Tick shade node types on the first diagram to colour each node as the search classifies it.
- PV node - nodes which have a score that ends up being inside the $(\alpha, \beta)$ window. For example, the leftmost branch of the tree comprises all PV nodes. In fact, the leftmost child of a PV node is itself always a PV node. Confusingly, the actual Principal Variation returned at the end of the search may not be the same as these. It is merely hoped that the real Principal Variation is searched first because we want to search moves in order of strength to promote cutoffs.
- Cut-node - a cut-node is a node where a cutoff happens. More interestingly, an expected cut-node is one where we hope for a beta cutoff to happen. If we really do manage to achieve good move ordering and search a very strong (PV) node first, all its siblings will be expected cut nodes. We anticipate that these nodes will be able to prune some of their children by virtue of having useful information available from when the PV sibling node was searched first.
- All-node - an all-node is one where all the moves get searched and none of them improves alpha (see fail-low above). Its parent is necessarily a cut-node.

Summary

The alpha-beta window is tracking already-known information about optimal decisions the two players can make in this node, and ancestor nodes higher up the tree. Because we already know things about what they will be inclined to do higher up, we can narrow down the moves that are interesting to us in this subtree.
Alpha and beta are telling us about the optimal choices that Max and Min can make higher up the tree. If it’s Max’s turn, Max can already do as well as alpha somewhere higher up. Min can already do as well as beta somewhere higher up. As soon as Max finds a move in this position which is better than beta, we’d be wasting time looking at this node any further. Max would choose something at least as good as beta here. But Min, somewhere above this node, would make a choice that is more favourable for her. So who cares how high this node might be. As soon as it’s higher than beta, it’s definitely not PV.
Although we are maximizing and would like the highest score possible, beta constrains us. It says, “don’t waste your time looking at crazily good moves here, because your opponent is not going to let you arrive at a node where you have such good options when they can make a more favourable choice higher up.” So beta tells us how high it is worth looking at a node before it becomes unreasonably good.

Appendix

The Minimax principle

In a game like chess - I focus on chess throughout, because I know it best, but everything applies to many other games - we each have perfect information about the state of the board and the possible moves available to us. The game is zero-sum: if I win, you lose and vice versa. To work out what to play in a given situation, you might find yourself doing a bit of reasoning that sounds like this: “well, I can go here, here or here. But if I go here, he can checkmate me, and if I go here, he can also checkmate me! But if I go here instead, he gets three possibilities and no matter which of those he plays… I can checkmate him!” This “I go here, you go there” thinking is formalised in the game theoretic concept called minimax. The basic principle is that there is a single score, which one player is attempting to maximize while the other tries to minimize. Because the game is zero-sum, that one number captures both sides at once: whatever is good for one player is bad for the other by exactly the same amount. A diagram should make this clear.

Step through the plain minimax walk above — no pruning yet, just values bubbling up from the leaves. Squares are Max nodes (taking the largest child), circles are Min nodes (taking the smallest).

In this diagram, we have two players, Max and Min, and a range of numeric values across the leaf nodes at the bottom. We should interpret these as:

$+\infty$ : Max wins
$-\infty$ : Min wins
$> 0$ : Max has the advantage
$< 0$ : Min has the advantage

Side note: in theory, a search tree for a game like chess only has three values $-\infty, 0, +\infty$ , representing loss, draw, win for white. Every game must end at a leaf node with one of these three outcomes. In practice, the game tree is far too massive to search exhaustively so we assign real-number scores to nodes when we have gone as deep down the tree as we can. These scores are inexact - a heuristic assessment of who appears to be doing best based on centuries of accumulated chess knowledge.

Imagine that only the bottom row of the diagram is filled in with numbers. We want to work out what Max should do at the very top of the tree. The way to analyse this is to start at the bottom and steadily work up. Starting at the left of the first row up, we see that if this position were reached it would be Min’s turn and she would be trying to pick the least bad of $10$ and $+\infty$ . That is of course $+10$ , so the node (i.e. position) is already worth $+10$ (step 9) because Min, acting rationally in that position, will pick the first move of the two, taking the board to a position worth $+10$ . Continue in this way along the row. Then move a row up and do the same again, this time from Max’s perspective who wishes to pick the maximum from the alternatives he has available. Working up the tree we eventually get $-7$ for the initial position (step 58), and conclude that Min is winning. Max has two options, both bad, and he should play the second option - the least bad of the two.

Here’s a typical implementation of minimax in pseudocode.

function maxi(depth) {
  if (depth == 0) return evaluate();

  max = -infinity;

  for (move in legal_moves) {
    make_move(move);
    score = mini(depth - 1);
    unmake_move(move);

    if (score > max) max = score;
  }

  return max;
}

function mini(depth) {
  if (depth == 0) return evaluate();

  min = +infinity;

  for (move in legal_moves) {
    make_move(move);
    score = maxi(depth - 1);
    unmake_move(move);

    if (score < min) min = score;
  }

  return min;
}

We have two implementations of the same idea, one for the maximizer, one for the minimizer. The function works recursively. If we reach a search depth of 0, we statically evaluate the current node and return that. Otherwise, we iterate through each available move in this position and call the ‘opposite function’ on the resulting position. As we get values back from each child subtree, we maintain a max variable (or min in the mini case), which tracks the most compelling option so far. At the end, we return whatever was the value of the best move for the current player. Everything propagates up the tree in this way and eventually the game is solved.

Note that in real life, nobody implements the algorithm in this duplicative manner. Instead, you can write a single function with a smattering of minus signs to produce the same result (the negamax style). This is obviously cleaner and more DRY, but somewhat harder to parse on a first read.

Improving efficiency with alpha-beta

Minimax works perfectly. It yields the best move in every position on the whole tree. The trouble is size. Chess has a branching factor of about 35 and game lengths average around 80 plies. So the tree is on the order of $35^{80} \approx 3 \times 10^{123}$ nodes — many more nodes than atoms in the universe. Even searching a handful of ply and evaluating heuristically at the leaves is a gigantic computation. Alpha-beta’s first insight is that we can prune whole subtrees out of the search, at zero cost to the answer.

Here’s the tree again, this time with pruning switched on:

Let’s again imagine traversing this tree from left to right. We’ll descend down the leftmost branch all the way to the leaf $5$ (step 5). We would then step back up, drop down the next leaf branch to $6$ , and conclude the parent node (a Min node) has value $5$ (step 9). We then step back up and descend down the sibling, to another Min node. We iterate through its children, discovering first a $7$ and then a $4$ . And this is where we can make a nifty observation. That $4$ we just found is the child of a Min node, so the Min node must have a value of at most $4$ (for Min would never voluntarily pick something larger than she has to). But wait! The parent of the Min node is a Max node which we already discovered earlier has a child of value $5$ . So in that node, Max is guaranteed to pick the $5$ or something higher. So combining these two facts, we’ve already seen enough to know that any further searching of the Min node is pointless wasted time - it can’t influence the value of the Max node above! Hence, in the diagram, we see the final child of the Min node (leading down to a $5$ ) pruned out (step 15). We don’t need to search it at all! Try changing that $5$ to any other number at all and discover that whatever you set it to, the $5$ two plies higher (and indeed the whole tree above that) is unaffected.

So the key to alpha-beta is to be smart about using bounds as we search the tree. We don’t typically need to know the exact value of every node to solve the tree. In many parts of the analysis, merely bounding the value of a node is sufficient to tell other nodes what they need to know.

The alpha-beta algorithm

So how you do implement this? Where do our friends alpha and beta enter the fray? Here’s some pseudocode:

function alpha_beta_max(alpha, beta, depth_left) {
  if (depth_left == 0) return evaluate();

  for (move in legal_moves) {
    make_move(move);
    score = alpha_beta_min(alpha, beta, depth_left - 1);
    unmake_move(move);

    if (score >= beta) return beta; // fail-high beta-cutoff

    if (score > alpha) alpha = score; // alpha acts like max in minimax
  }

  return alpha;
}

function alpha_beta_min(alpha, beta, depth_left) {
  if (depth_left == 0) return evaluate();

  for (move in legal_moves) {
    make_move(move);
    score = alpha_beta_max(alpha, beta, depth_left - 1);
    unmake_move(move);

    if (score <= alpha) return alpha; // alpha-cutoff

    if (score < beta) beta = score; // beta acts like min in minimax
  }

  return beta;
}

One would invoke this at the root node by calling

score = alpha_beta_max(-infinity, infinity, 10);

The algorithm is clearly very similar to the minimax algorithm we started with. Now, however, we are passing around these alpha and beta variables. Evidently, they are tracking those bounds of interest and, at certain times, we return early from the function - a so-called “fail-high cutoff”.

Negamax version

For completeness, here’s the algorithm modified to the “negamax” form I alluded to above. We don’t really want a different function for each perspective when we can achieve the same thing with some minus signs. This approach can be a bit confusing at first, but it’s certainly cleaner.

function alpha_beta(alpha, beta, depth_left) {
  if (depth_left == 0) return evaluate();

  for (move in legal_moves) {
    make_move(move);
    score = -alpha_beta(-beta, -alpha, depth_left - 1);
    unmake_move(move);

    if (score >= beta) return beta; // fail hard beta-cutoff

    if (score > alpha) alpha = score; // alpha acts like max in minimax
  }

  return alpha;
}

Hopefully by comparing with the previous version, you can see that this is really the same thing. Everything is now done as if both players are maximisers. Whenever it is Min’s turn, she works with the negation of the real score, which makes her a maximizer. Slightly less obviously, our slippery pals alpha and beta get swapped back-and-forth in the recursive call to alpha_beta. This is because they are being used like a range or window on the number line, and when we negate everything, the top end of the range becomes the bottom and vice versa. For the main discussion about what the variables alpha and beta represent, return to the top.

Footnotes

Since chess has a large branching factor and we want to search as deeply as we can, a cutoff at a shallow ply can remove tens of millions of nodes that it was always going to be uninformative to search. ↩