Build a Connect Four opponent

What you are building

Connect Four has seven columns and six rows. A move drops one disc into a non-full column, and the first player to make a horizontal, vertical, or diagonal line of four wins. The rules are short, but the search grows quickly. A full-width tree has 343 paths at depth three and more than 40 million at depth nine.

Start from the app in the small web app project. Store the board as data and render the screen from that state. Search must use temporary moves on the data without changing the visible board, so keep game rules, opponent logic, and rendering in separate functions.

Teal entries are build milestones. Magenta entries explain a limitation and link to the lesson needed to address it. Benchmark each opponent against earlier versions using the same starting-player policy and the same set of test positions.

Project milestones

1. Render the board and accept legal moves.

   Draw a seven-column, six-row board. A click adds a disc to the lowest empty cell in that column and changes the active player. Ignore clicks on full columns and while a computer move is being calculated.

2. Detect wins and draws.

   After a move, inspect horizontal, vertical, and both diagonal directions through the new disc. Count matching discs on both sides and include the new disc. Four or more is a win. If no legal columns remain and nobody won, record a draw. Stop accepting moves after either result.

3. Separate game rules from the screen.

   The opponent needs to test moves without displaying them. If every state change redraws the board, search will flash temporary positions on screen and can leave state behind when a branch returns early.

   What you need

   Write rule functions that list legal moves, apply a move, undo a move, and detect the game result. Give every opponent the same interface: a position goes in and a legal column comes out. Render only after the chosen real move. Test that applying and undoing any legal move restores a byte-for-byte copy of the original board and active player.

   step 8Naming a recipe step 11Drawing the screen from data
4. Add a random legal opponent.

   Choose uniformly from the legal columns. Run random against random without rendering the intermediate boards. This becomes the simplest automated check for illegal moves, unfinished games, and state that leaks between matches.

5. Create a repeatable benchmark.

   A few games against a person cannot separate a real improvement from random variation. Human play also changes between versions. Use automated matches, controlled starting conditions, and enough repetitions to expose the size of the difference.

   What you need

   Run at least 200 machine-against-machine games and alternate which opponent moves first. Record wins, losses, draws, and positions evaluated per move. Fix the random seed when comparing code changes, then repeat with several seeds before drawing a conclusion. Node count is useful across computers; elapsed time is still worth measuring on the target device.

   step 1Counting, not timing
6. Save the random-player baseline.

   Alternate the starting player and report results by seat as well as in total, since Connect Four favours the first player. A large unexplained asymmetry can indicate a rules or reset bug. Save this row unchanged as the comparison baseline.

7. Take immediate wins and block immediate losses.

   Create two test positions: one with a winning move and one where only a block avoids an immediate loss. The random opponent will often miss both. Keep these positions as fixed regression tests for every later version.

   What you need

   Test every legal move. Choose an immediate win if one exists. Otherwise reject moves that allow the opponent to win on the next turn, then choose among the remaining columns. This is a one-ply tactical policy, not a generally correct greedy solution. Positions with two simultaneous threats show its limit.

   step 11Take the biggest bite
8. Benchmark the one-ply opponent.

   Record its results against the random baseline. Also record how many legal moves it evaluates, which will vary as columns fill. Add a fork position where one move creates two threats; the one-ply policy cannot plan the setup or defend after it is complete.

9. Search beyond one reply.

   Use the saved fork position to determine the minimum search depth that avoids it. Count depth in plies, where one ply is one player's move, and document whether the current position is depth zero or depth one. Off-by-one definitions make benchmark results difficult to compare.

   What you need

   Use recursive depth-first search with terminal cases for a win, loss, draw, or depth limit. In minimax, one level chooses the maximum score and the other chooses the minimum because the players have opposing goals. Keep the score convention explicit: for example, always score from the computer player's point of view.

   step 8Recursion, and the same work twice step 9Breadth first, depth first
10. Search four plies with a position evaluator.

    A depth limit often stops before the game ends, so write an evaluation function for non-terminal positions. Terminal wins and losses must outweigh any heuristic score. For other positions, count playable threats and open lines for each side. Test the function separately and check that swapping players negates the score if that symmetry is part of your definition.

11. Measure search growth and repeated positions.

    Log node counts at increasing depths. The theoretical upper bound multiplies by as many as seven each ply, although filled columns and finished games reduce it. Count repeated positions too. Different move orders can reach the same board, so recalculating those states wastes much of the search budget.

    What you need

    A full-width search examines roughly b^d nodes for branching factor b and depth d, although full columns and early wins reduce the real count. Store completed position values in a transposition table. Its key must encode every fact that affects the result, including the board and side to move. If the key is only a fixed-size hash, handle or verify collisions rather than assuming they cannot occur.

    step 12Fill in a table instead step 13Shapes, and measuring rather than guessing step 3Find a word in a page without re-reading it
12. Measure transposition-table reuse.

    Report table probes, valid hits, replacements, and total nodes. Do not assume a particular hit rate; it depends on position, depth, key design, replacement policy, and move ordering. Verify that enabling the table leaves chosen moves and scores unchanged on fixed positions.

13. Prune branches that cannot affect the choice.

    Follow one decision. It finds a column worth three. It starts on the next column and, two moves down, discovers a reply of yours worth minus five. It then searches the whole of that branch anyway, thoroughly, to establish exactly how bad the branch it has already ruled out is.

    What you need

    Alpha-beta pruning carries lower and upper bounds through minimax. Stop a branch when its result cannot improve the choice already available to the player at that level. It returns the same move as unpruned minimax. Move ordering changes how much it saves: with near-perfect ordering, the best case approaches O(b^d/2); poor ordering can still require O(b^d).

    step 1Find the median without sorting the list
14. Reach depth nine within the move budget.

    Use iterative deepening so the search completes depth one, then depth two, and continues until its time or node budget expires. Return the move from the last completed depth. Record nodes, completed depth, table hit rate, and elapsed time for both typical and worst-case positions.

15. Compare every opponent version.

    Run the full benchmark for random play, one-ply tactics, depth-four minimax, transposition-table search, and depth-nine alpha-beta search. Report win, loss, and draw rates with the starting-player policy. Include median and worst-case nodes per move. Keep the test positions so later changes can be compared with the same cases.

Review the game in four passes

Review the same implementation for basic behaviour, edge cases, search cost, and recovery.

Course links for each pass

Use these lessons when the corresponding test fails.

1. Test search boundaries.
   Make it correct

   This is the oldest bug in the subject and it has a canonical example. Binary search was published in 1946, and a version correct for lists of every length took another sixteen years to appear in print. The idea is easy and the boundaries are not. Your search has boundaries too: depth zero, a column with one slot left, a board with one slot left and a win made on the final disc. None of them turn up in an ordinary game, so each has to be built on purpose and tested.

   step 3Halving, and the traps in it
2. Judging a position without examining every branch.
   Make it fast

   There is another way to put a number on a position, and it does not look at every branch: play the game out from there at random, hundreds of times, and count how often each side ends up winning. It is sometimes wrong, and how often it is wrong is a number you choose by deciding how many of those playouts to spend. Trading certainty for cost on purpose, with the odds written down, is a family of methods the strongest game programs are built on.

   step 2Check two huge files match, and choose your own odds
3. Restore a saved game.
   Make it survive

   Write the position and whose turn it is into the store the browser keeps for your app after every move, and read it back when the page opens. The store holds text and a board is a list of lists, so the pair of conversions is most of the work. Then close the tab in the middle of a game, reopen it, and compare every restored cell and the active player with the saved value.

   step 12Remembering after you close it

Optional extension: learn a position value from self-play

Keep the minimax player. It supplies a known reference for legal moves and small positions. The learned version should earn its place by reaching a useful decision faster or handling a larger board under the same time limit.

1. Generate positions and exact labels.

   Play many games with varied legal strategies. For positions small enough to search completely, label win, draw or loss from the side to move. Keep symmetric or nearby positions in one split so copies do not leak into the test.

2. Train a small value model, then use it only at search leaves.

   The search still generates legal moves and alternates players correctly. The model estimates positions where the depth limit stops. Compare it with the original hand-written evaluation under identical node and time budgets.

3. Add self-play without grading the model on its own games alone.

   Run a fixed tournament against random, minimax and earlier checkpoints across held-out starts and seeds. Report wins, draws, losses, illegal moves, decision time and uncertainty, not one selected match.

4. Keep an exact endgame check.

   When few moves remain, solve the position completely and reject a learned choice that disagrees with the proven result. This makes a hybrid opponent: learned where approximation saves work and exact where the tree is small.

Relevant lessons: Introduction to Machine Learning, Neural Networks, and transfer and evaluation boundaries.

Related projects and courses

A position you can change and undo exactly, a search that alternates between two opposite intentions, a table that stops it working the same thing out twice, and a bound that lets it stop early. Those four are what sits underneath the programs that took draughts, chess and Go off human champions. What changed between those three is the part you hand wrote here: the number that says how good a position is. What comes next is a program that works that number out from games it has played rather than being told it by you.

All builds or read Introduction to Algorithms and Algorithm Design straight through, which cover the same ground in order and go considerably further.