I've been working on Patzer, a chess engine, during my time at RC. The first engine-like thing I implemented for it was alpha-beta pruning, which is a way of pruning out branches of the search tree to significantly speed up search. This is a common algorithm, which I also implemented in my undergrad AI class. That doesn't mean that I fully understood it as I wrote it! It's pretty tricky in the details and not immediately obvious why the pruning works.

In the process of writing it and debugging it, another Recurser and I traced through the execution with a known position where we could calculate the execution. This let us figure out what was going wrong, and also gain some intuition for what the algorithm was doing. I'm going to use that same position here to illustrated alpha-beta pruning. (This is partially so that when I inevitably forget the details, I can come back here and refresh myself!)

We'll start with an overview of the algorithm viewed through the lens of the algorithm it enhances, minimax. Then we will look at the alpha-beta pruning algorithm itself. We'll wrap up by looking at our example position, a hand-constructed position which utilizes a smothered mate, and see how minimax and alpha-beta pruning work on it.

Minimax algorithm

The base algorithm we're using here is called Minimax, and the name comes from what you're trying to do: You want to minimize the cost of the worst case maximum cost.

The intuition here is that under best play, if your opponent is making optimal moves, then they're going to make the moves which put you in the worst possible position. You're trying to pick moves which make your worst case less bad. (And that's ultimately what playing good chess is about: not making mistakes, and taking advantage of your opponent's mistakes.)

Here's Python-esque pseudocode which we could use for a basic Minimax implementation:

def max_step(board, depth):
  if depth == 0:
    return score(board)

  max_score = INT_MIN;

  for move in board.moves():
    next_position = board.make_move(move)
    score = min_step(next_position, depth - 1)
    if score > max_score:
      max_score = score

  return max_score


def min_step(board, depth):
  if depth == 0:
    return -1 * score(board)

  min_score = INT_MAX

  for move in board.moves():
    next_position = board.make_move(move)
    score = max_step(next_position, depth - 1)
    if score < min_score:
      min_score = score

  return min_score

The max_step function is the one that corresponds to the current player: They're trying to maximize among their possible outcomes. The min_step function corresponds to the opponent, who is trying to minimize their opponent's best case.

(As an aside: this is usually written in the Negamax style, which reduces it down to one function. This is how I've implemented it in Patzer, but for clarity I'm presenting it as two separate functions.)

This algorithm will find all the best moves! Unfortunately, it's also slow. It exhaustively explores the entire state space of the game tree. For chess, this gets quite large quite quickly: There are over 6 trillion leaves in the minimax tree after the first 4 complete moves of the game (depth 8). My computer would not ever reach this depth.

So, what are we to do?

Alpha-beta pruning

This is where alpha-beta pruning comes in. It's an optimization for minimax which allows us to prune out major swaths of the search tree.

The core idea of alpha-beta pruning is that there are some branches we know we won't explore, because they're too good or too bad. If a branch has a way that we can guarantee a better outcome than another branch, our opponent won't let us pursue that. If a branch has a way that our opponent can guarantee us a worse outcome than another branch, we won't go down that one, either.

To make this work, we keep track of the lower-bound (alpha) and upper-bound (beta), which let us then eliminate branches once we've confirmed that the branch will violate one of the bounds that we can otherwise guarantee. Note that this is done depth-first, like minimax. This is crucial for finding a leaf quickly to evaluate.

Here's the pseudocode of the algorithm. Again, this is the two-function implementation; you can make it one function at the expense of some readability. I've put some inline comments to highlight the differences between this and minimax. These comments are only in the max step function, but apply equally to both.

# we add two parameters, alpha and beta, which track lower and upper bounds
def alphabeta_max_step(alpha, beta, board, depth):
  if depth == 0:
    return score(board)

  # note that we're not tracking the max or min anymore!
  # these are tracked via alpha and beta now.

  for move in board.moves():
    next_position = board.make_move(move)
    score = alphabeta_min_step(alpha, beta, next_position, depth - 1)

    # when the score is higher than the upper bound, we just fail to the
    # already established upper bound.
    if score >= beta:
      return beta

    # when we find a score that's higher than alpha, our lower bound, we
    # can adopt it as the new lower bound since we know we can achieve
    if score > alpha:
      alpha = score

  return alpha


def alphabeta_min_step(alpha, beta, board, depth):
  if depth == 0:
    return -1 * score(board)

  for move in board.moves():
    next_position = board.make_move(move)
    score = alphabeta_max_step(alpha, beta, next_position, depth - 1)

    if score <= alpha:
      return alpha

    if score < beta:
      beta = score

  return min_score

Using these bounds turns out to be very helpful. Analysis on Chess Programming Wiki indicates that this can cut down the search tree significantly. If we always get the best move first, we would only have to evaluate 5 million positions. Obviously we can't know what the best move is or we would just play it! But there are ways we can order moves to find the best move earlier, and if you order them randomly you will still