← Blog

Connect Four AI: the minimax algorithm behind Neon Drop

2026-07-06

Every good phone game needs an opponent that answers quickly, plays a fair game, and can be beaten when you want it to be. For Neon Drop, my four-in-a-row game, that opponent is a classic minimax search with alpha-beta pruning and a small evaluation function. This post walks through how the Connect Four AI actually works, what its heuristic reveals about good four-in-a-row strategy, and where a depth-limited search falls short of perfect play.

(Four-in-a-row is the public-domain game mechanic; “Connect Four” is a Hasbro trademark. The algorithms are identical, so I use both terms.)

Minimax for Connect Four

Minimax treats the game as a tree of moves. From the current board, the AI (the maximizing player) considers every legal column, then imagines your best reply (the minimizing player), then its reply, and so on. Leaf positions are scored: a win for the AI is +10,000,000, a win for you is −10,000,000, and a draw is 0. The AI plays the move whose worst-case outcome is best.

In language-neutral form, the whole algorithm is this:

function minimax(board, depth, maximizing):
    if AI has won:        return WIN_SCORE
    if human has won:     return -WIN_SCORE
    moves = legal moves
    if moves is empty:    return 0
    if depth <= 0:        return evaluate(board)

    if maximizing:
        best = -infinity
        for column in moves:
            child = play AI piece in column
            best = max(best, minimax(child, depth - 1, false))
        return best
    else:
        best = +infinity
        for column in moves:
            child = play human piece in column
            best = min(best, minimax(child, depth - 1, true))
        return best

The root decision is a separate, simpler step:

best column =
    legal move with the highest
    minimax(resulting board, depth - 1, minimizing)

One ordering detail matters: the terminal win and loss checks come before the depth cutoff. If the depth test ran first, a win created on the final searched move would be scored by the heuristic instead of the terminal score, and the search would sometimes walk past a forced win.

The depth limit matters, because the full tree is enormous. With seven columns the branching factor is about seven, so looking six moves ahead reaches on the order of a hundred thousand positions before any pruning.

Alpha-beta pruning

Alpha-beta pruning is what makes that depth practical on a phone. It tracks the best score the maximizer can already guarantee (alpha) and the best the minimizer can guarantee (beta). Once a branch can no longer change the decision, the search drops it. The move it returns is exactly the one plain minimax would pick, found by evaluating far fewer positions.

Here is the same search with pruning, in compact Python (I verified this implementation against a plain minimax on random positions at depths zero through four; it returns identical values and moves, and it passes immediate-win and immediate-block checks):

from math import inf

AI, HUMAN = 2, 1
WIN = 10_000_000

def minimax(board, depth, alpha, beta, maximizing):
    if winner(board, AI):
        return WIN
    if winner(board, HUMAN):
        return -WIN
    moves = legal_moves(board)
    if not moves:
        return 0
    if depth <= 0:
        return evaluate(board)

    if maximizing:
        value = -inf
        for column in moves:
            child = play(board, column, AI)
            value = max(value, minimax(child, depth - 1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value

    value = inf
    for column in moves:
        child = play(board, column, HUMAN)
        value = min(value, minimax(child, depth - 1, alpha, beta, True))
        beta = min(beta, value)
        if alpha >= beta:
            break
    return value

def choose_move(board, depth):
    moves = legal_moves(board)
    if not moves:
        return None
    return max(
        moves,
        key=lambda column: minimax(play(board, column, AI), depth - 1, -inf, inf, False),
    )

Four helpers carry the board mechanics: legal_moves(board) returns the columns that are not full, play(board, column, piece) returns a copied board after dropping the piece, winner(board, piece) detects four connected pieces in any direction, and evaluate(board) is the scoring function described in the next section. They are short, but win detection and board representation are where the real engineering time goes.

Pruning correctness does not depend on move order, but pruning performance does. A one-line improvement is to search the center columns first:

ORDER = [3, 2, 4, 1, 5, 0, 6]

def legal_moves(board):
    return [column for column in ORDER if board[0][column] == 0]

Center moves participate in more potential lines, so good moves surface earlier and cutoffs happen sooner, with deterministic center-favoring tie breaks as a side effect. The chart above measured the original left-to-right ordering; center-first would prune more.

The evaluation function

Minimax produces exact values only at terminal positions. At a depth-limited leaf, the evaluation function stands in for the rest of the game: it approximates position quality, and the approximation is a heuristic score rather than a probability of winning. Its scale stays far below the +/-10,000,000 terminal scores, so a real win or loss always dominates any heuristic judgment.

When the search hits its depth limit without a win or loss, it has to estimate how good the position is. Neon Drop scores every window of four cells (horizontal, vertical, and both diagonals) and adds a bonus for the center column, where the most winning lines pass through.

// score one window of four cells, from the AI's point of view
if pieceCount == 4 { score += 1000 }
else if pieceCount == 3 && emptyCount == 1 { score += 10 }
else if pieceCount == 2 && emptyCount == 2 { score += 4 }
if opponentCount == 3 && emptyCount == 1 { score -= isHard ? 80 : 15 }  // block threats

Difficulty levels

Search depth on its own makes a stiff, robotic ladder. Neon Drop’s three levels combine depth with two other knobs.

enum Difficulty {
    case easy, medium, hard
    var searchDepth: Int {   // plies to look ahead
        switch self { case .easy: return 2; case .medium: return 4; case .hard: return 6 }
    }
    var blunderChance: Int { // percent chance of a random legal move
        switch self { case .easy: return 30; case .medium: return 10; case .hard: return 0 }
    }
}

Easy looks two moves ahead and plays a random legal move 30% of the time; Medium looks four ahead and blunders 10%; Hard looks six ahead, never blunders, and weights blocking your threats more heavily. The blunder chance is what makes the easier levels feel human: they slip the way a casual player does, instead of playing a weaker but still machine-consistent game.

What the AI reveals about Connect Four strategy

The heuristic weights are a compact summary of good four-in-a-row strategy:

• Play the center. The center column sits on the most horizontal, vertical, and diagonal lines, so it earns an explicit bonus. Strong players open in the center for the same reason.
• Build and block threes. A three-in-a-row with an open fourth cell is one move from winning, which is why it scores far above a two, and why the AI drops everything to block yours.
• Aim for two threats at once. The real winning idea is a fork: two threats a single block cannot both stop. Minimax finds these on its own, because a position that forces a win a few moves later already scores as a win.

The same evaluation that drives the AI works as a checklist for a human: control the center, respect threes, and set up double threats. (For a very different game-modeling problem, I wrote about predicting the next pitch in baseball.)

Is Connect Four solved?

Yes. Standard 7x6 four-in-a-row is a solved game: with perfect play the first player wins by starting in the center column, a result proved by Victor Allis in 1988. For working solver code, see John Tromp’s solver and Pascal Pons’s step-by-step solver series. Neon Drop’s AI is a strong heuristic player rather than a perfect solver: it searches a limited depth and leans on the evaluation function, which is fast and fun to play against without being the game-theoretic optimum.

Scope and limits

The engine is a clean, standard implementation, and it leaves a few things on the table. Competition-grade solvers usually replace the two-dimensional grid with bitboards, packing a position into machine-word bit operations so legal moves and four-in-a-row checks become much cheaper, and they add a transposition table that caches positions reached through different move orders instead of searching them repeatedly. Both improve speed without changing the underlying minimax decision rule; Neon Drop deliberately keeps the simpler grid implementation, and it also has no opening book. The search also reasons about the base drop game only: the power-ups (Bomb, Blocker, Undo) and the 5x5 and 8x8 boards work in the app, but the AI does not plan around them. On the larger boards the same code still searches, over more columns.

Try it

Neon Drop is free on the App Store. Pick a difficulty and see how far ahead you can think.

The figures come from a faithful Python port of the app’s Swift AI, run to measure node counts and tactical accuracy; the numbers are illustrative of the method.

This is an independent project I build on my own time. The views are my own and do not represent any current or former employer.