Building Intelligent Agents for Connect-4: Tree Search Algorithms

The Alpha-Beta Search
- The Negamax Variant
Source Code

This post is the 2nd part of a series of 9 articles:

To play Connect-4 perfectly, an agent must be able to prove the game-theoretic value of a position, potentially by searching all the way to terminal states 42 plies from the empty board. It need not visit every branch (the purpose of the methods in this series is precisely to avoid that), but the search effort still grows exponentially with depth.

This post isolates the first improvement I made to the plain Minimax agent: alpha-beta search. The method does not change the value returned by Minimax, but it avoids branches which can no longer affect that value. All later techniques in the series either help it reach such a cutoff sooner or reuse work which an earlier search has already performed.

The Alpha-Beta Search

The alpha-beta search carries two bounds through the Minimax recursion. Alpha is the best score the maximizing player can already guarantee, and beta is the best score the minimizing player can already guarantee. If a maximizing node finds a move with a value at least beta, the minimizing player has a better alternative elsewhere and will not permit this line, so the remaining moves can be discarded. This is a fail-high, and in a fail-hard implementation the node returns beta. Conversely, if no move improves the alpha with which the node was entered, the result is only known to be at most alpha, which is a fail-low. Only a result strictly inside the incoming window $[\alpha,\beta]$ is established as exact by that window alone.

The recurrence itself remains unchanged, and the savings depend almost entirely on the order in which the moves are tried. A good first move supplies a useful bound to all of its siblings, whereas a poor order may leave almost the complete Minimax tree intact. The cutoff can occur at every level of the recursion, so a small improvement near the root also removes all descendants which would otherwise have been generated below it.

The mechanics are easier to see on a small example than in prose. The tree below is searched from left to right: the first branch is resolved completely and establishes $\alpha = 3$, and from that point on every further branch only has to answer the question whether it can beat 3. The second branch cannot, since its first leaf already shows that the minimizer can hold it to at most 2, and the third one is abandoned as soon as its second leaf brings it down to 3, which is no improvement either. The greyed subtrees are never generated at all.

**Figure 1:** Alpha-beta pruning on a 3-ply example tree, searched left to right with a fail-hard driver. The edges are annotated with the window $[\alpha, \beta]$ each MIN node receives: the first branch is searched with the full window and returns 3, after which $\alpha = 3$ narrows the window for everything that follows. In the second branch the very first leaf yields $2 \le \alpha$, so its remaining leaves are pruned and the red node records the upper bound $\le 2$ rather than an exact value; the fail-hard return passed upwards is $\alpha$. The third branch is cut the same way after its second leaf. Alpha-beta evaluates six of the nine leaves and still returns the same root value as a full Minimax search; with a different leaf order it could have been more or fewer, which is why move ordering later gets a post of its own. The figure is generated by `tools/connect4/make_alphabeta_figure.py`, which runs that small fail-hard search over the tree and draws the result. BitBully’s loop below is fail-soft: it uses the same cutoffs but returns the searched value.

The original Java implementation expresses the two players in separate methods and is more than a thousand lines long once its generated move ordering and threat cases are included. The modern C++ engine uses the equivalent Negamax form described below. The following is the actual inner loop for its early search stage, with comments and one assertion removed:

int value = -(1 << 10);
if (depth < 20) {
  auto mvList = b.sortMoves(moves);

  auto mv = mvList.pop();
  for (; mv && alpha < beta; mv = mvList.pop()) {
    auto moveValue = -negamax(b.playBitMaskOnCopy(mv), -beta, -alpha,
                              depth + 1, maxDepth);
    value = std::max(value, moveValue);
    alpha = std::max(alpha, value);
  }
}

The condition alpha < beta is the cutoff. As soon as a child raises alpha to beta, the loop ends without searching another child. The complete function then records value <= oldAlpha as an upper bound, value >= beta as a lower bound, and an interior value as exact. These details can be checked directly in the pinned BitBully.h; the corresponding two-method implementation remains in AlphaBetaAgent.java. The opening book, transposition table, move ordering, symmetry handling and board representation appearing around this loop receive their own posts later in the series.

The Negamax Variant

In BitBully I use the Negamax variant of the Minimax algorithm. Negamax is mathematically equivalent to Minimax, but it takes advantage of the symmetry between maximizing and minimizing players and represents both with a single recursive function. The idea is based on the relation:

\[\min(a, b) = -\max(-a, -b)\]

At each step, the function calls itself with the signs and window reversed, thereby switching the point of view to the other player. This does not change the nodes which alpha-beta has to visit, but it removes the nearly identical maximizing and minimizing functions found in the Java agent. The corresponding negamax implementation can be found in the pinned BitBully.h.

Alpha-beta is not quite the end of the story, though. The recursive function above still needs somebody to decide which window to call it with at the root, and in the paired measurements of part 8 this engine’s repeated null-window searches were faster on average than one search with a wide window. That driver, and the scoring convention that makes it work, are the subject of part 7.

Source Code

The complete implementations are available as the modern C++/Python BitBully solver and the earlier Java CFour framework. BitBully is also available on PyPI, while its project page collects the documentation and usage examples.

The Alpha-Beta Search

The Negamax Variant

Source Code

Enjoy Reading This Article?