Building Intelligent Agents for Connect-4: Final Considerations

Determination of the Game-Theoretic Values of Inner Nodes
Evaluation of a Position at the Search Horizon
Measured Effects of the Techniques
Discarded Approaches
The Cost of all of this
A Perfect Player without Learned Knowledge
Learning as an Alternative to Search
Overview of the Series
Source Code
References

This post is the 9th part of a series of 9 articles:

In this last post of the series a few additional methods are described which can be used to speed up the tree search for a Connect-4 agent somewhat further, together with an accounting of what the whole exercise actually bought, the ideas which did not work, and finally the question which the series has been building towards.

There is, after all, something rather unsatisfying about a perfect player. It plays flawlessly and can even prove that it does, and yet it understands nothing at all. If the board were changed to eight columns, the layout-specific masks, encoders and databases would have to be rebuilt even though the general search algorithms would remain useful. This is not a small caveat, and it is the reason why the story continues in a second series.

Determination of the Game-Theoretic Values of Inner Nodes

Probably the most valuable technique in a game solver is the recognition of a decided position before it is expanded at all. Many situations of the Connect-4 game allow a player to immediately put the opponent into an impasse, so that the game can be won in the next turn. Typically there are three types of such winning positions:

At the end of the game, situations often arise in which one player can only move under a threat of the opponent and then loses the game, which is a compulsory move.
In some cases one player succeeds in creating two immediate threats with a single move. The opponent can only neutralize one of the two and has therefore lost.
If a column contains two threats of a player which lie directly on top of each other, the player in question only has to move under the first threat in order to win the game.

**Figure 1:** The three patterns, one example each. **Left:** the zugzwang case — blue is to move, the dashed cells (b3 and e1) are the only playable ones, and both lie directly beneath a red winning cell (amber, with the completing four-in-a-row traced). Whatever blue plays, red wins on the reply. **Middle:** the green move creates two immediate threats at once (amber, on either side of the horizontal line); the opponent can block only one of them. **Right:** the case `doubleThreat()` detects without any search — the green move sits beneath two of blue’s own stacked threats (amber), so red has to block the lower one, which immediately opens the upper one. The figure is generated by `tools/connect4/make_winning_patterns.py`, which replays each example against the engine and asserts the pattern (`generateNonLosingMoves() == 0` for the first, an empty reply set for the second, a firing `doubleThreat()` for the third) before drawing it.

The first point is already handled: it is exactly the case in which generateNonLosingMoves() from part 4 returns an empty mask and the node reports a loss without generating anything at all. BitBully recognizes the other two patterns differently. findThreats() identifies a move which creates two separate immediate threats and places it first in the move order; after that move, the opponent’s empty reply set establishes the loss. The stacked pattern of point 3 is the one detected directly by doubleThreat(), so its exact value can be returned without expanding the move at all.

BitBully runs the relatively cheap non-losing move filter at every ordinary search node, but restricts the more expensive threat ordering and stacked-threat check to shallower nodes. The first pattern removes losing replies, the second resolves after one child is entered, and the third cuts off the node immediately. Together, this tactical recognition avoids the complete analysis of numerous subtrees and accelerated the search by approximately 20% in my 2012 measurements.

The legacy CFour search has one further, minimal shortcut. When exactly 40 tokens are on the board, its first-player routine inspects the two remaining cells and returns the exact last-two-ply outcome without recursing through them. BitBully has no separate branch for this case; its general search resolves the same small remainder.

Evaluation of a Position at the Search Horizon

Positions for simple games such as Tic-Tac-Toe can be analyzed with the help of a tree search without any particular problems, since the game tree can be expanded up to the leaves. With a much greater complexity, as is the case for Connect-4, this is no longer possible without further effort, and the search depth often has to be limited to an acceptable value. If the search reaches the horizon, a function is required which can estimate the game-theoretic value of the current position. This assessment is usually not trivial, since on the one hand a high quality of the evaluation function is expected, while on the other hand it has to be computed within a reasonable time in order to avoid further unnecessary restrictions on the search depth. In order to resolve this conflict of objectives, a high degree of creativity and very detailed knowledge of the game in question are necessary.

Connect-4 differs from chess in one respect which is easy to overlook: with a very large amount of programming effort, and with everything described in this series, the terminal nodes can actually be reached. For this reason no particular importance was attached to the static position evaluation at the search horizon in my work, since a perfect tree search was only required as a comparison for the TD learning experiments.

The 2012 engine does contain such a function nevertheless, and its structure is instructive. While the material ratio plays an important role in chess, the relevant feature for Connect-4 is the number of threats of both players and their arrangement, since every token is identical here. The function evaluate() therefore first determines all threats of the players, collects them into bit boards, and then applies the odd/even parity rules from part 4:

// More threats are deliberately left unresolved by this evaluator.
if (numThreats > 2)
    return -1;

switch (numThreats) {
case 0:
    return 0;
case 1:
    if (threatsP2 != 0) {
        if ((threatsP2 & EVENROWS) != 0L)
            return -500;
        return 0;
    }
    if ((threatsP1 & ODDROWS) != 0L)
        return 500;
    return 0;
// ... the generated two-threat cases follow ...
}

The routine is deliberately incomplete: it evaluates positions with at most two threats and returns -1 as an unresolved sentinel when it encounters a third. A comment in the 2012 source estimates that the covered cases account for more than 70% of boards, although it does not record the sample behind that estimate. The useful point is therefore not the percentage but the restricted design: the bit masks make a small set of common horizon cases cheap, rather than attempting a complete strategic evaluation.

BitBully takes the other road, which was described in part 7. Instead of evaluating features at the horizon, rollout() plays the game out using the centre-first non-losing heuristic and returns the terminal score of that heuristic playout. This is not the game-theoretic value of the horizon position, but it is expressed in the same units as the full search. It therefore requires no feature engineering, tuning or calibration, and it reuses machinery which exists for other reasons anyway.

Measured Effects of the Techniques

The following table pulls together the measurements from across the series. They are not additive, since each of them was taken against a different baseline and on a different workload, and the entries marked as 2012 originate from my original development notes for the Java agent rather than from a rerun today. In my opinion the ranking is the useful part here, rather than the individual digits:

Technique	Part	Measured effect	Source
Threat-based move ordering	4	~2× faster overall	2012
Double-threat / stacked-threat cutoffs	4, 9	~20% faster	2012
Mirror-symmetry deduplication	5	~50% of the state space	measured
12-ply opening book	6	1.8M nodes → 21 nodes at 10 stones	measured
MTD(f) vs. wide-window negamax	7, 8	1.13–1.62× faster, \(p < 10^{-4}\)	measured
All of it, vs. a strong reference solver	8	1.96× on the empty board	measured

Bit boards, which were the subject of part 3, are deliberately absent from this table, since there is no honest way of giving them a row of their own. They are not an optimization which is layered onto a working solver, but rather the substrate on which every other line of the table is built. The bottom row compares two complete engines and cannot isolate the effect of the representation either, so this series offers no standalone speed-up factor for bit boards.

The overall pattern is nevertheless worth naming. The largest factors come from not searching at all, that is, from the opening book, from the threat cutoffs which return an exact value, and from the move ordering which allows alpha-beta to prune in the first place. The choice of root driver — MTD(f) rather than wide-window negamax — contributes a respectable but comparatively modest factor of at most about 1.6 in this run. This ordering is, in my experience, not specific to Connect-4.

Discarded Approaches

Negative results are usually the part which everyone omits, so I would like to list a few of them here.

Iterative deepening is standard practice in chess programming and was implemented in the 2012 engine, but it was removed again since it produced no runtime advantage. Chess programs need it because they cannot reach the terminal nodes and have to answer when the clock runs out, whereas a Connect-4 solver searches to the end, so that the intermediate iterations only pay for themselves through an improved move ordering. The threat-based ordering of part 4 had already taken most of that.

Linear probing in the transposition table was tried and measured and brought no improvement, so that the always-replace strategy won. With a stored key a bad slot is detected rather than believed, and the additional probes cost more than the additional hits return. A related replacement rule retained entries from nodes closer to the root rather than allowing deeper-in-tree nodes to evict them, on the reasoning that a hit nearer the root can cut off a larger subtree. It was also tried and is still sitting in the BitBully source code as a commented-out block with the verdict “Does not help!” attached to it.

Finally, everything I tried for the deep stage of the move ordering beyond the trivial centre-out order made the deep search slower, since there are simply not enough nodes below a deep cutoff to repay any per-node analysis.

Still open and so far unmeasured are the prefetching of transposition-table entries, larger tables, and a parallelization of the search at the root.

The Cost of all of this

At the time of writing the documentation, the final Java agent contained nearly 7000 lines of source code, a substantial fraction of which was generated automatically. The price for this was listed already in part 3: high programming effort, poor readability, difficult maintenance and rather tedious troubleshooting. Everything described in part 8 exists because of the last of these.

For this particular problem I would say that the effort was worthwhile, since the resulting solver still runs today and compares favourably with the independent reference implementation measured in part 8. The honest summary, however, is that this is a rather poor way of writing software in general and an effective way of solving one specific, fixed and well-defined problem. This brings us to the limitation which no amount of further optimization can touch.

A Perfect Player without Learned Knowledge

BitBully plays Connect-4 perfectly and can also prove that it does so. Nevertheless, there are a number of rather fundamental limitations.

The implementation does not transfer automatically to a different board. If the board were widened to \(8 \times 7\), the layout-specific masks, the nine-bit column stride, the Huffman encoder and both databases would have to be regenerated or redesigned. The general search algorithms would remain applicable, but most of the encoded domain knowledge belongs to this particular board.

Furthermore, perfect play here relies on being able to search all the way to terminal positions. Everything described in this series helps prune a game tree whose unpruned complexity is roughly \(10^{21}\), but an exhaustive terminal solution does not scale to Go or chess. Alpha-beta search remains useful there, but it must stop at a horizon and evaluate positions rather than solve the whole tree.

For its full-depth use, the agent also has no learned notion of a good position; it computes a solved outcome and distance. Its depth-limited modes fall back to hand-designed procedures: CFour uses the small threat evaluator shown above, whereas BitBully uses the deterministic rollout from part 7. Neither transfers knowledge learned from experience.

Finally, and most importantly, the program has learned nothing. Every piece of knowledge in those 7000 lines was put there by a human, whether it is the centre-out priors, the odd/even threat theory or the pattern of stacked threats, and the program contributed none of it itself.

Humans do not play solely by exhaustive terminal search. A decent human player recognizes a shape which has been seen before, draws an analogy to a position which is not quite the same, and generalizes from a handful of games to a whole class of positions. This is a completely different kind of competence, and it is the one which scales to problems in which the tree cannot be enumerated.

Learning as an Alternative to Search

There is a second approach to the same game, and it inverts essentially every assumption made above. Instead of proving the values by enumeration, one can learn them from experience. An agent plays against itself, receives a reward at the end of each game, and adjusts a value function in such a way that its estimate of a position moves towards what actually happened afterwards. Over many games, the value function comes to encode something resembling positional judgement. With a shared function approximator, similar positions reuse parameters, so the estimate can generalize to positions which the agent has never seen before. This generalization is neither guaranteed nor exact, but the same method can be applied to games whose trees cannot be enumerated at all.

This is reinforcement learning, and specifically temporal difference learning (Sutton, 1988)(Sutton & Barto, 1998). The machinery from this series does not go to waste, either — it becomes the foundation:

The bit board representation of part 3 is reused to simulate many games in parallel on a GPU. As described there, the batched variant applies essentially the same expressions to tensors of positions instead of to single integers, and the legal-move generation and win detection carry over directly.
The insights about threats and about the parity of rows from part 4 inform how positions are described by features.
The old Java framework already contains the other half of this story: nTupleTD/ValueFuncC4.java implements the n-tuple value function used by the TD-learning agent, and mcts/ a Monte-Carlo tree search agent, both of which sit alongside the alpha-beta agent, which is not a coincidence. There is even a small tool, CountRealizableStates.java, which counts how many of the states an n-tuple can formally take are actually realizable on a Connect-4 board — a question that becomes relevant the moment a value function is built from such tuples, and one the learning series will return to.

If you would like to go further in this direction, Wolfgang Konen’s General Board Game framework (GBG) is worth a look. It is a Java framework for general board game learning and playing which supports one-, two- and n-player games, ships with a range of built-in agents from reinforcement learning to tree search, and standardizes the interfaces sufficiently that agents and games can be combined and benchmarked fairly against each other. Its technical report explains the architecture in detail.

Most usefully of all, however, BitBully becomes the referee in these experiments. The hardest problem in evaluating a learning agent is knowing how good it actually is, since self-play win rates are circular and beating a weak opponent proves very little. A perfect solver removes this ambiguity entirely, because every move which the learner makes can be scored against the game-theoretic optimum, so that the term “near-perfect” stops being a figure of speech and becomes a measurement.

This will be the subject of the next series: the same game, the opposite method, and the solver built here as the opponent to beat. If this series was about computing the answer, the next one is about learning to guess it well, and about why, for almost every genuinely interesting problem, approximation is the only practical option.

Overview of the Series

First Steps — why board games, why Connect-4, and how big the problem is
Tree Search Algorithms — alpha-beta and negamax
Board Representations — two integers, sentinel bits, and four-in-a-row by shifting
Move Ordering — threats, parity, and not generating losing moves
Transposition Tables — Zobrist hashing, and when you can skip it
Opening Databases — four million positions in 21 MB
MTD(f) and Null-Window Search — score conventions and zero-width windows
Verification and Benchmarking — how to know it is right, and faster
Final Considerations — this post

Source Code

BitBully — GitHub · PyPI · Docs · project page · and an interactive board to play against it:
bitbully-databases — GitHub · PyPI · Docs · project page
General Board Game framework (GBG) — GitHub · technical report
John Tromp — Connect-4 page
CFour (the 2012 Java framework, including the TD-learning and MCTS agents) — GitHub
Measurement scripts for parts 3–8 live in tools/connect4/ in the source of this blog.

References

Learning to Predict by the Methods of Temporal Differences.

Richard S. Sutton

Machine Learning, 1988
Reinforcement Learning: An Introduction

Richard S. Sutton and Andrew G. Barto

1998

Several paragraphs of this post are adapted from my Master’s thesis, a translation of my Bachelor thesis, and some earlier project work.