Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 46 ยท Projects

Project: Connect Four AI

Build a Connect Four AI in Python: bitboards, evaluation, alpha-beta with move ordering, iterative deepening, an MCTS opponent and a round-robin tournament harness.

Connect Four is small enough to search deeply and rich enough to need real engineering. In this project you build a complete game-playing program from the pieces of the adversarial-search chapter: a fast board representation, an evaluation function, alpha-beta pruning with move ordering, iterative deepening under a budget, and a Monte Carlo tree search opponent. A tournament harness then tells you, with data, which player is stronger.

If any of those terms are new, read games and minimax and evaluation functions and depth limits first. Each program below runs live in your browser, and node counts are exact and repeatable, so you can check your own implementation against ours.

The plan

graph LR
    B["Bitboard game<br/>play, win test"] --> E["Evaluation<br/>69 windows"]
    E --> S["Negamax +<br/>alpha-beta"]
    S --> O["Move ordering"]
    O --> I["Iterative deepening<br/>with a node budget"]
    B --> M["MCTS<br/>random playouts"]
    I --> T["Tournament<br/>harness"]
    M --> T

Two independent players built on one shared game model, compared by one harness.

Step 1: A fast game model with bitboards

The board has 7 columns and 6 rows. A naive representation (a list of lists) is easy to read but slow to copy and to scan for four in a row. A game-playing program does this millions of times, so we use bitboards: the whole board in a couple of integers, where each cell is one bit.

  • Each column uses 7 bits (6 cells plus one spare "sentinel" bit at the top), so cell (column c, row r) is bit c*7 + r. Row 0 is the bottom.
  • A state is a triple (pos, mask, moves). mask has a 1 for every occupied cell. pos has a 1 for every stone belonging to the player to move. The opponent's stones are pos ^ mask.
  • To drop a stone in a column, add the bottom bit of that column to mask: mask + BOTTOM[c] carries into the lowest empty cell, because the occupied cells below it are all 1s. Then swap sides with pos ^ mask, a single XOR (the player who just moved becomes "the other player").
  • Four in a row is a handful of shifts. For a direction with shift s (1 for vertical, 7 for horizontal, 6 and 8 for diagonals), m = pos & (pos >> s) marks pairs, and m & (m >> 2s) marks four. The spare bit per column keeps stones from "wrapping" from the top of one column into the bottom of the next.

Our evaluation looks at every window: each set of four cells in a line. There are 69 on a 7x6 board (24 horizontal, 21 vertical, 24 diagonal). A window containing stones of only one player is an open line for that player, and the more stones it holds the better. A window with stones of both players is dead and counts for nothing. We weight windows by how many stones they hold: 1, 4 and 24 points for one, two and three stones. The evaluation is the mover's total minus the opponent's total.

Python The bitboard model and a first look at evaluation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bottom row holds three X stones with both ends open, so X threatens to win in columns 0 and 4. It is O's turn, but O cannot block both ends: the position is lost. Notice what the static evaluation says: it likes column 3 best (+8), because O would build three in a row on row 1. That is a bad move, since X wins immediately by playing column 0 or 4. A static evaluation sees patterns but not tactics; looking ahead is the job of search.

Step 2: Negamax with alpha-beta

In a zero-sum game, one player's gain is the other's loss, so a single function can serve both sides. Negamax evaluates a state from the mover's point of view and negates the child's value: value = max(-negamax(child)). The code is shorter than minimax with separate max and min cases and has the same result.

Alpha-beta pruning carries a window (alpha, beta) of values that still matter. If a move proves to be at least as good as beta for the mover, the opponent would never allow this position, so the remaining moves can be skipped. Pruning never changes the final value; it only avoids work.

Three details matter for a good Connect Four searcher:

  • Immediate wins first. At every node we check whether the mover can win at once (wins_now) before searching deeper. A win scores 1000 - moves played, so sooner wins are better and sooner losses are worse.
  • Terminal and draw handling. A full board scores 0.
  • Move ordering. Alpha-beta prunes most when the best move is tried first. In Connect Four the central columns are statistically the strongest, so searching them first (3, 2, 4, 1, 5, 0, 6) is an excellent static ordering.

Step 3: Measure move ordering and iterative deepening

Iterative deepening searches to depth 1, then 2, then 3, and so on. It looks wasteful, but it is how real programs handle time: you can stop whenever the budget runs out and play the best move of the last completed depth. Each iteration also hands the next one a good move to try first. Our budget is a count of nodes, which keeps the results repeatable; production code uses a clock.

The program searches a fixed position with plain minimax, with alpha-beta in left-to-right order and with alpha-beta in center-first order, and checks that all of them return the same score.

Python Minimax versus alpha-beta, ordering and iterative deepening

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results show how much work the pruning and ordering save:

Depth Minimax Alpha-beta, left to right Alpha-beta, center first
4 2,129 988 362
5 12,467 4,727 1,194
6 not run 17,054 2,398
  • Pruning alone roughly halves the work at depth 4 and cuts it by about 2.6 times at depth 5, and the gap widens with depth.
  • Good ordering is worth even more: center first beats left to right by 7 times at depth 6, and it reaches depth 8 in 16,164 nodes, fewer than left-to-right needs for depth 6. Alpha-beta with perfect ordering would examine about the square root of what minimax does, and good ordering gets close to that.
  • Iterative deepening is cheap insurance. Searching every depth from 1 to 6 costs 4,102 nodes against 2,398 for a direct depth-6 search: about 70 percent more, because the last iteration dominates the total. In exchange you get an answer at any moment, and the node-budget table shows it: 500 nodes reach depth 3, 2,000 reach depth 5 and 8,000 reach depth 6.
  • Search finds what evaluation misses. In the double-threat position from Step 1, the search reports a forced loss (-994) after only 8 nodes.

When you port this to a larger game, always add an assertion that your pruned search returns the same value as the unpruned one on a few positions, as the program does. Move ordering bugs and pruning bugs both show up as silently wrong scores.

Step 4: An MCTS opponent

Alpha-beta needs an evaluation function, which takes expertise to write. Monte Carlo tree search needs none: it plays thousands of random games to the end and learns which moves win more often. Each simulation has four phases, repeated:

  1. Selection: walk down the tree, at each node choosing the child with the best UCB1 score, which balances moves that have done well against moves that have been tried little.
  2. Expansion: add one untried child.
  3. Simulation: play random moves to the end of the game.
  4. Backpropagation: update the win counts on the path back to the root (from the right player's viewpoint at each node).

After a fixed number of simulations, play the most-visited move at the root. Our implementation stores the reward at each node for the player who moved into it, which is the detail beginners most often get wrong.

Step 5: The tournament

The harness is a function that takes two players (functions from a state to a column) and plays a game with a few random opening moves, so that not every game is identical. For fairness each opening is played twice, once with each side moving first. The tournament runs every pair and totals the points: win 1, draw one half.

The four players:

  • random: any legal column, the baseline.
  • MCTS 100: 100 simulations per move.
  • AB depth 2: alpha-beta to a fixed depth of 2.
  • ID 500 nodes: iterative deepening with a budget of 500 nodes per move.
Python Round-robin tournament: random, MCTS and alpha-beta players

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see this table:

Pairing Result for the first player (W-D-L)
random vs MCTS 100 0-0-4
random vs AB depth 2 0-0-4
random vs ID 500 nodes 0-0-4
MCTS 100 vs AB depth 2 1-0-3
MCTS 100 vs ID 500 nodes 0-0-4
AB depth 2 vs ID 500 nodes 2-0-2

The final points are ID 500 with 10.0, AB depth 2 with 9.0, MCTS 100 with 5.0 and random with 0.

What to take from it:

  • Every searching player crushes random play, as it should.
  • Iterative deepening finishes first. Even with a tiny 500-node budget, which reaches only about three plies in the middle of the opening, it sees threats that a fixed depth-2 search misses. But 2-0-2 against depth 2 shows how thin the margin is.
  • MCTS with only 100 simulations loses to the searchers (1-0-3 against depth 2), though it has no evaluation function and no knowledge of Connect Four at all, and it still beats random play every time. Its strength grows steadily with the number of simulations; try 1,000 and watch the cost in time.
  • Four games per pairing is a tiny sample. Differences like 2-0-2 are noise. For real conclusions, play hundreds of games and report a confidence interval; the harness above is ready for that, you only change games_per_pair.

Make it stronger

  • Transposition table. Different move orders reach the same position. Store scores in a dictionary keyed by (pos, mask) and reuse them. In Connect Four this can reduce the node counts by a large factor.
  • Better ordering. Try moves that win or block first, then use the previous iteration's best move at every node, not only the root (the "principal variation" or killer-move ideas).
  • Tune the evaluation. Change WEIGHT, or add a bonus for stones in the center column, and use the tournament to check whether the change is real.
  • Smarter MCTS. Play immediate wins and blocks inside the random playouts, and give the root more simulations.
  • Solve the game. Connect Four has been solved: with perfect play the first player wins by starting in the center column. The best solvers use bitboards, a large transposition table and opening books, much like the ideas in this project, to prove it in a few seconds in a fast language.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why are bitboards a good representation for Connect Four search?

    A move is a handful of integer operations, and the win test uses shifts and ANDs. That speed matters when a search visits millions of positions.
  2. 2. What does negamax rely on?

    In a zero-sum game the opponent's gain is your loss, so one function with a sign flip replaces separate max and min functions.
  3. 3. Why does searching the center columns first make alpha-beta faster?

    Alpha-beta prunes best when the best move is searched first. Center moves are usually strongest, so they raise alpha early. The final value stays the same.
  4. 4. What is the main practical advantage of iterative deepening?

    Iterative deepening costs somewhat more in total, but it always has a complete answer ready when time or budget runs out.
  5. 5. In MCTS, what does the simulation phase do?

    Simulation (rollout) plays out the game with random moves. The result is then propagated back up the tree to update win statistics.

Summary

  • Bitboards store a Connect Four position in a few integers; moves and win tests are shifts and ANDs.
  • An evaluation function over the 69 four-cell windows scores open lines, but it cannot see tactics such as a double threat.
  • Negamax plus alpha-beta returns the same value as minimax with far fewer nodes, and center-first ordering reaches depth 8 in about 16,000 nodes.
  • Iterative deepening trades about 70 percent extra nodes for an answer at any moment, and in the tournament it won.
  • MCTS needs no evaluation function and still beats random play, but with 100 simulations it loses to a depth-2 alpha-beta.
  • Small tournaments are noisy: play many games before drawing conclusions.

Next: Project: Robot Maze Navigator.