A wooden tic-tac-toe board with black X's and O's

Build an unbeatable tic-tac-toe AI with minimax

Learn how the minimax algorithm works by building an unbeatable tic-tac-toe AI in JavaScript. Watch it look ahead at every possible move, then speed it up with alpha-beta pruning. Finally, take the AI to a bigger game: four in a row, which you might know as Connect Four.

Before you read on, try to beat the AI below. You play X, and the AI plays O. Click or tap a square to make your move. Under the board, you can pick who goes first.

The best you can get is a draw, because the AI looks at every possible move, all the way to the end of the game. By the time you finish this tutorial, you'll know exactly how it does that:

First move

What is the minimax algorithm?

The minimax algorithm picks the best move in a game for two players who take turns, like tic-tac-toe, checkers or chess. It looks at every move the AI can make, every reply the opponent can make to that move, and so on, until the game ends. Then it picks the move that leads to the best result. While it does that, it assumes that the opponent always plays their best move too.

To compare the results, minimax gives every finished game a score. In tic-tac-toe, a win for the AI scores +1, a draw scores 0 and a loss scores -1. The AI wants the score to be as high as possible, so it's the maximizing player. You want the score to be as low as possible, so you're the minimizing player. That's where the name comes from: one player maximizes the score, and the other minimizes it.

Together, all the moves that minimax looks at form a game tree. At the top is the board as it is right now. Below it, there's a branch for every move the AI can make, and below each of those, a branch for every reply you can make. At the bottom are the finished games, each with its score. Here's the game tree for a game in which the AI went first. It's the AI's turn again, with three empty squares left:

Minimax fills in the scores from the bottom up. A finished game gets its score: +1, 0 or -1. Then every board above it gets a score from the boards below it. On your turn, minimax takes the lowest score, because it assumes you'll pick the move that's worst for the AI. On the AI's turn, it takes the highest. On each small board, the mark from the last move is in full color, and the older marks are faded. Press Step to go through the tree one step at a time.

In this position, you have two X's in the middle row. If the AI doesn't take the last square of that row, you take it and win, so both of the AI's other moves score -1. Only the move that blocks you scores 0, and that's the move minimax picks. After that block, the AI has two O's in the right column, so you have to block it, and the game ends in a draw. It's not a win, but a draw is the best the AI can get here.

Set up a tic-tac-toe board

Before the AI can think, it needs a board to think about. The easiest way to store a tic-tac-toe board is as an array of 9 strings, one for every square. An empty square is '', and the other squares hold 'X' or 'O'. The squares are numbered from 0 to 8, row by row, starting in the top-left corner:

let board = [
    '', '', '', // Squares 0, 1 and 2
    '', '', '', // Squares 3, 4 and 5
    '', '', ''  // Squares 6, 7 and 8
];

To find out if someone has won, check the 8 lines of three squares: three rows, three columns and two diagonals. For each line, a, b and c are the numbers of its three squares. getWinner() returns 'X' or 'O' if all three squares of a line hold the same mark, and null if nobody has three in a row yet. A game also ends when the board is full, and isFull() checks for that with includes():

const lines = [
    [0, 1, 2], [3, 4, 5], [6, 7, 8], // Rows
    [0, 3, 6], [1, 4, 7], [2, 5, 8], // Columns
    [0, 4, 8], [2, 4, 6]             // Diagonals
];

function getWinner(board) {
    for (const [a, b, c] of lines) {
        const mark = board[a];
        if (mark != '' && mark == board[b] && mark == board[c]) {
            return mark;
        }
    }
    return null;
}

function isFull(board) {
    return !board.includes('');
}

When you click the board, the square under the mouse gets your mark. In the code below, canvas is the canvas element on your page, and the board fills the whole canvas. So x and y give the position of the click on the board, from 0 at the left or top edge to 1 at the opposite edge. Multiply them by 3 and round down, and you get the column and the row. Then multiply the row by 3 and add the column, and you have the number of the square:

canvas.addEventListener('click', function (event) {
    const rect = canvas.getBoundingClientRect();
    const x = (event.clientX - rect.left) / rect.width;
    const y = (event.clientY - rect.top) / rect.height;
    const column = Math.floor(x * 3);
    const row = Math.floor(y * 3);
    const square = row * 3 + column;
    if (board[square] == '') {
        board[square] = 'X';
        draw();
    }
});

A click always places your X. Once there's an AI, it places its O by itself, right after your move. The tutorial about game controls for keyboard, mouse and touch explains clicks on the canvas in more detail.

The draw() call clears the canvas and draws the grid and the marks. It uses lines and circles, as in the tutorial about drawing on the canvas. The example code at the end of this page has the whole draw() function.

There's no AI yet in the demo below, so you place the O's yourself: your clicks switch between X and O. The code under the board shows what the board array looks like:

Live demo The code updates as you play around
let board = [
    '', '', '',
    '', '', '',
    '', '', ''
];
// getWinner(board) returns null

Start with an AI that follows simple rules

Most people who play tic-tac-toe follow a few rules of thumb, so why not give those to the AI? The AI in this section checks these rules in order, and follows the first one that applies:

  • Win - If the AI can complete a line, it does.
  • Block - If you could complete a line on your next move, the AI takes the square you need.
  • Center - If the center square is free, the AI takes it.
  • Corner - If a corner is free, the AI takes the first free one, counting from square 0.
  • Anything else - Otherwise, it takes the first empty square.

That sounds pretty smart, and against most moves, it is. But it has a weak spot: the fork, a move that creates two threats at once. The AI can only block one of them, and you win with the other.

Try it below:

  1. Step 1 - Start in a corner. The AI takes the center.
  2. Step 2 - Take the opposite corner. The AI takes another corner, which gives it two O's on a diagonal.
  3. Step 3 - Block that diagonal, and see what happens.

Your block on the diagonal also gives you two lines with two X's, and the AI can't block both. You could add a rule for forks, and people have written sets of rules for tic-tac-toe that never lose. But every game needs its own rules, and for bigger games, nobody knows all the right ones. Minimax doesn't need any rules about strategy. It only needs to know which moves are allowed and who has won, and it works out the rest by looking ahead.

Write a recursive minimax function

Minimax fits in a single function that calls itself. A function like that is called a recursive function. minimax() takes a board and whose turn it is, and returns the score of that board. That's the score the game ends with if both players play perfectly from there. Here's the whole function:

function minimax(board, isAiTurn) {
    // If the game is over, return its score
    const winner = getWinner(board);
    if (winner == 'O') {
        return 1;
    }
    if (winner == 'X') {
        return -1;
    }
    if (isFull(board)) {
        return 0;
    }

    // Try every empty square, and keep the best score for this player
    let bestScore = isAiTurn ? -Infinity : Infinity;
    for (let i = 0; i < 9; i++) {
        if (board[i] != '') {
            continue;
        }
        board[i] = isAiTurn ? 'O' : 'X';
        const score = minimax(board, !isAiTurn);
        board[i] = '';

        if (isAiTurn) {
            bestScore = Math.max(bestScore, score);
        } else {
            bestScore = Math.min(bestScore, score);
        }
    }
    return bestScore;
}

First, minimax() checks if the game is over. If it is, the function returns the score: 1 if the AI won with O, -1 if you won with X, and 0 for a draw. These finished games are at the bottom of the game tree, and they stop the recursion. Without these checks, the function would keep playing after someone has won, and return the wrong scores.

If the game isn't over, minimax() tries every empty square. It puts the current player's mark in the square, and calls itself with !isAiTurn, so the other player is next. That call returns the score of the new board. Then board[i] = '' empties the square again.

Good to know - You might expect each call to get its own copy of the board, but there's only one array, and every call to minimax() changes that same array. If a call left its mark behind, then when it tried the next square, the board would have two new marks instead of one. Every score after that would be wrong. Emptying the square puts the board back the way it was, so the call one level up in the tree can carry on with the right board.

Finally, the function keeps the best score. On the AI's turn, that's the highest score, which Math.max() finds. On your turn, it's the lowest score, which Math.min() finds. bestScore starts at -Infinity or Infinity, so the first score always replaces it.

How many boards does minimax() look at? To work out the AI's first move on an empty board, minimax() runs 549,945 times. That's far more than the 5,478 different positions in tic-tac-toe. Different move orders often lead to the same board, and minimax looks at that board again every time it gets there. Still, your browser does all of that in a fraction of a second.

Let the AI pick its best move

minimax() gives you the score of a board, but the AI needs a move. So on its turn, the AI tries every empty square, asks minimax() for the score of the board after that move, and remembers the square with the highest score:

function findBestMove(board) {
    let bestScore = -Infinity;
    let bestMove = -1;
    for (let i = 0; i < 9; i++) {
        if (board[i] != '') {
            continue;
        }
        board[i] = 'O';
        const score = minimax(board, false);
        board[i] = '';
        if (score > bestScore) {
            bestScore = score;
            bestMove = i;
        }
    }
    return bestMove;
}

After the AI's move, it's your turn, so findBestMove() calls minimax() with isAiTurn set to false. findBestMove() returns the number of a square, so the AI makes its move with board[findBestMove(board)] = 'O'.

That's all it takes: this AI never loses. In the demo below, turn on AI's scores to see what minimax thinks of every empty square. Each square shows how the game ends if the next mark goes there and both players play perfectly after that. On your turn, a square with AI wins is a mistake, and the AI will punish it. On the AI's turn, it waits a moment before it moves, so you can see its scores too:

AI's scores

On your turn, the scores never show AI loses. In tic-tac-toe, both players can always get at least a draw, so against an AI that plays perfectly, you can't win. Start in a corner, with the scores on, and you'll see that the AI has only one move that doesn't lose: the center.

Make the AI win as fast as it can

Make a mistake against the AI from the previous section, and you may see something odd. Sometimes the AI could win right away, but it plays a different square, and only wins a few moves later. It still wins, so what's the problem? To the person playing, it looks like the AI is toying with them.

And there's a worse case. The difficulty levels further down this page make the AI play badly on purpose. That can leave it in a position where it can only lose. In that case, it doesn't even try to block you.

Both problems come from the scores. A win scores +1, whether it happens now or five moves from now, so to minimax, every winning move is just as good. findBestMove() keeps the first square with the highest score, and that's not always the fastest win. When every move loses, they all score -1, and the AI takes the first empty square, even if blocking you would keep the game going.

To fix this, let the score depend on how deep in the game tree the game ends. The depth is the number of moves from the current board to that point in the tree. Pass it along as an extra argument, and use it in the score of a win or a loss:

function minimax(board, depth, isAiTurn) {
    const winner = getWinner(board);
    if (winner == 'O') {
        return 10 - depth;
    }
    if (winner == 'X') {
        return depth - 10;
    }
    // ...
    for (let i = 0; i < 9; i++) {
        // ...
        const score = minimax(board, depth + 1, !isAiTurn);
        // ...
    }
    return bestScore;
}

In findBestMove(), the board after the AI's move is one move deep, so the call becomes minimax(board, 1, false). Now, if the AI wins with the move it's about to make, that scores 9. If it wins two moves after that, that scores 7. If you win on your next move, that scores -8, and if you win two moves later, that scores -6. So a fast win scores higher than a slow one, and a slow loss scores higher than a fast one.

The 10 only has to be bigger than 9, the number of moves in the longest possible game. Then a win always stays above 0, and a loss below it.

In the demo below, you can switch between the two kinds of scoring. It shows the score of every empty square, and the square the AI picks. The small numbers in the corners are the numbers of the squares:

Position
Scoring

In the AI can win position, the AI can complete the diagonal with square 6 right away. But with Any win, all four empty squares score +1, because the AI can win after each of them. So it picks the first one, square 3. With Fastest win, square 6 scores 9 and the others 7, and the AI wins at once.

In the AI will lose position, you're about to complete the left column with square 6. Even if the AI blocks you, you can win with a fork. With Any win, every square scores -1, so the AI takes square 4, and you win on your next move. With Fastest win, blocking you on square 6 scores -6, because then you need two more moves to win. The other squares score -8. Against a person who makes mistakes, that block gives the AI a chance.

Skip moves that don't matter with alpha-beta pruning

Minimax looks at every move, even when it's clear early on that a move can't be the best one. Take another look at the game tree from the first section. The AI first tries square 5, at the right end of the middle row. That blocks your row, and the AI gets at least a draw: a score of 0. Then it tries square 6, the bottom-left corner, and finds that you can reply by taking square 5 and winning. You pick the lowest score, so square 6 can't score more than -1. The AI already has a move that scores 0, so it will never play square 6, and your other reply to square 6 doesn't matter anymore. Minimax can skip that reply.

Skipping branches like this is called alpha-beta pruning. Pruning means cutting off branches, and alpha and beta are the two numbers it keeps track of:

  • alpha - The highest score the AI can already count on. It starts at -Infinity and only goes up.
  • beta - The lowest score you can already count on. It starts at Infinity and only goes down.

Once beta is less than or equal to alpha, minimax can stop trying moves on the current board. One of the players already has a better move earlier in the tree, and won't let the game get to this board. So the code uses break to skip the rest of the moves:

function minimax(board, depth, isAiTurn, alpha, beta) {
    // Check if the game is over, like before
    // ...

    let bestScore = isAiTurn ? -Infinity : Infinity;
    for (let i = 0; i < 9; i++) {
        if (board[i] != '') {
            continue;
        }
        board[i] = isAiTurn ? 'O' : 'X';
        const score = minimax(board, depth + 1, !isAiTurn, alpha, beta);
        board[i] = '';

        if (isAiTurn) {
            bestScore = Math.max(bestScore, score);
            alpha = Math.max(alpha, score);
        } else {
            bestScore = Math.min(bestScore, score);
            beta = Math.min(beta, score);
        }
        if (beta <= alpha) {
            // The other player won't let the game get here
            break;
        }
    }
    return bestScore;
}

In findBestMove(), the best score so far is the score the AI can already count on. So it passes bestScore as alpha, and Infinity as beta: minimax(board, 1, false, bestScore, Infinity).

You can see alpha in action in the game tree from the first section. By the time the AI tries square 6, alpha is already 0, because square 5 gave the AI a draw. But after square 6, you can win by playing square 5 yourself. Your win scores below 0, so beta drops below alpha, and minimax skips your other reply. The same happens when the AI tries square 8.

Alpha-beta pruning never changes the move the AI picks, only how much work it takes to find it. For the AI's first move on an empty board, plain minimax() runs 549,945 times. With alpha-beta pruning, it runs only 20,865 times.

Press Play in the demo below to watch alpha-beta pruning at work on the game tree from the first section. The skipped branches turn gray, and the counter shows how many positions minimax looks at. Switch to Minimax to compare:

Search

With Alpha-beta, minimax looks at 10 positions instead of 14. The order in which minimax tries the moves matters too. Alpha-beta pruning skips the most branches when the best move comes first, because then alpha is high right away. In tic-tac-toe, the order hardly makes a difference, but in a bigger game it does, as you'll see later with four in a row.

Give the AI a difficulty level

An AI that never loses is impressive, but not much fun to play against. Most games let you pick a difficulty, and the easiest way to make the AI weaker is to let it make mistakes on purpose. Here, the AI sometimes plays a random empty square, and plays its best move the rest of the time. mistakeChance says how often, for each difficulty. The tutorial about random numbers in JavaScript explains how to pick a random item from an array:

// How often the AI plays a random square instead of its best move
const mistakeChance = {
    easy: 0.6,
    medium: 0.25,
    hard: 0
};

function findAiMove(board, difficulty) {
    if (Math.random() < mistakeChance[difficulty]) {
        const emptySquares = [];
        for (let i = 0; i < 9; i++) {
            if (board[i] == '') {
                emptySquares.push(i);
            }
        }
        const index = Math.floor(Math.random() * emptySquares.length);
        return emptySquares[index];
    }
    return findBestMove(board);
}

On Easy, the AI plays a random square 60% of the time, and on Hard, it never does, so you're back to the AI that never loses. A random square isn't always a bad move, so even on Easy, the AI wins now and then. Try the three levels below:

Difficulty

Another way to make the AI weaker is to let it look only a few moves ahead. That's what the AI for four in a row does in the next sections. In that game, looking ahead all the way to the end isn't possible anyway.

Take on a bigger game: four in a row

Four in a row is played on an upright board with 7 columns and 6 rows. The players take turns dropping a disc into a column, and it falls to the lowest free spot. The first player to get four discs in a row wins. The line can be horizontal, vertical or diagonal.

Could minimax look ahead to the end of every game of four in a row, like it does in tic-tac-toe? Not even close. Tic-tac-toe has only 5,478 different positions. Four in a row has 4,531,985,219,092, more than 4.5 trillion. Even at a million positions per second, looking at all of them would take more than 50 days.

So the AI only looks a fixed number of moves ahead. That number is called the maximum depth. When it reaches that depth, it estimates how good the board is, using the evaluation function from the next section. But first, the board itself.

The board is an array of 6 rows, with the top row first, and each row is an array of 7 squares. createBoard() makes an empty board like that. Your discs are 'X' and the AI's discs are 'O', just like in tic-tac-toe. dropDisc() finds the lowest empty square in a column, puts the disc there and returns its row, or -1 if the column is full:

const rows = 6;
const columns = 7;

function createBoard() {
    const board = [];
    for (let row = 0; row < rows; row++) {
        board.push(new Array(columns).fill(''));
    }
    return board;
}

function dropDisc(board, column, mark) {
    for (let row = rows - 1; row >= 0; row--) {
        if (board[row][column] == '') {
            board[row][column] = mark;
            return row;
        }
    }
    return -1;
}

function isFull(board) {
    return !board[0].includes('');
}

isFull() only checks the top row: once that's full, the whole board is. Minimax needs the row that dropDisc() returns, so it can take the disc out again with board[row][column] = ''.

Checking for a winner works the same way as in tic-tac-toe, but there are a lot more lines. A line of four is any four squares next to each other horizontally, vertically or diagonally, and a board with 7 columns and 6 rows has 69 of them.

The code below collects them all in linesOfFour, once at the start. From every square, it goes three squares further in each of the four directions in the directions array. If the last of those squares is still on the board, the four squares form a line. Each line it finds starts at its top end, or at its left end if the line is horizontal. That's why four directions are enough. None of them goes up, so endRow never drops below 0, and there's no need to check for that. countMarks() counts the discs of one player in a line:

// To the right, down, down to the right and down to the left
const directions = [[0, 1], [1, 0], [1, 1], [1, -1]];
const linesOfFour = [];
for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
        for (const [rowStep, columnStep] of directions) {
            const endRow = row + rowStep * 3;
            const endColumn = column + columnStep * 3;
            if (endRow >= rows || endColumn < 0 || endColumn >= columns) {
                continue;
            }
            const line = [];
            for (let i = 0; i < 4; i++) {
                line.push({
                    row: row + rowStep * i,
                    column: column + columnStep * i
                });
            }
            linesOfFour.push(line);
        }
    }
}

function countMarks(board, line, mark) {
    let count = 0;
    for (const square of line) {
        if (board[square.row][square.column] == mark) {
            count++;
        }
    }
    return count;
}

function getWinner(board) {
    for (const line of linesOfFour) {
        if (countMarks(board, line, 'O') == 4) {
            return 'O';
        }
        if (countMarks(board, line, 'X') == 4) {
            return 'X';
        }
    }
    return null;
}

Score a board with an evaluation function

When minimax reaches the maximum depth and nobody has won yet, it still needs a score. An evaluation function makes an estimate: it looks at the board and guesses how good it is for the AI. The guess doesn't have to be perfect. It only has to tell a strong board from a weak one, because minimax compares the scores, and picks the best.

A simple evaluation function for four in a row looks at every line of four. A line with discs of both players can never become four in a row, so it doesn't count. A line with only the AI's discs is good for the AI, and the more discs, the better. A line with only your discs is just as bad for the AI. On top of that, every disc in the middle column, column 3, gets a bonus, because the middle column is part of more lines of four than any other column:

// What a line of four is worth, for 0, 1, 2 or 3 discs of one player
const lineScores = [0, 1, 4, 16];

function evaluate(board) {
    let score = 0;
    for (const line of linesOfFour) {
        const ai = countMarks(board, line, 'O');
        const you = countMarks(board, line, 'X');
        if (you == 0) {
            score += lineScores[ai];
        } else if (ai == 0) {
            score -= lineScores[you];
        }
    }

    // A bonus for discs in the middle column
    for (let row = 0; row < rows; row++) {
        if (board[row][3] == 'O') {
            score += 3;
        } else if (board[row][3] == 'X') {
            score -= 3;
        }
    }
    return score;
}

A line with three discs and one empty square is one move away from a win, so it's worth 16, four times as much as a line with two discs. evaluate() doesn't need a score for four discs, because minimax checks for a winner first.

Drop a few discs in the demo below. You place both colors, alternating between red for you and blue for the AI. The demo marks every line of four that has two or three discs of one color and none of the other. A line with three discs gets a thicker mark. Next to the board, you see the score that evaluate() returns: above 0 is good for blue, and below 0 is good for red:

The numbers in lineScores and the bonus of 3 are choices, not rules. You can tweak them to give the AI a different style, for example one that blocks more and attacks less.

Play a game of four in a row against the AI

Now put it all together. The minimax() for four in a row is the tic-tac-toe version with alpha-beta pruning, plus three changes:

  • Maximum depth - At maxDepth, it stops and returns the score from evaluate().
  • Bigger scores for a win - A win scores 10,000 minus the depth, so it always beats any estimate from evaluate().
  • Middle columns first - It tries the columns in the order given by columnOrder, starting with column 3 in the middle. Moves in the middle columns are usually the best, and alpha-beta pruning skips the most branches when the best move comes first.

Here's the code:

// How many moves the AI looks ahead
const maxDepth = 4;
const columnOrder = [3, 2, 4, 1, 5, 0, 6];

function minimax(board, depth, isAiTurn, alpha, beta) {
    const winner = getWinner(board);
    if (winner == 'O') {
        return 10000 - depth;
    }
    if (winner == 'X') {
        return depth - 10000;
    }
    if (isFull(board)) {
        return 0;
    }
    if (depth == maxDepth) {
        return evaluate(board);
    }

    let bestScore = isAiTurn ? -Infinity : Infinity;
    for (const column of columnOrder) {
        const row = dropDisc(board, column, isAiTurn ? 'O' : 'X');
        if (row == -1) {
            continue;
        }
        const score = minimax(board, depth + 1, !isAiTurn, alpha, beta);
        board[row][column] = '';

        if (isAiTurn) {
            bestScore = Math.max(bestScore, score);
            alpha = Math.max(alpha, score);
        } else {
            bestScore = Math.min(bestScore, score);
            beta = Math.min(beta, score);
        }
        if (beta <= alpha) {
            break;
        }
    }
    return bestScore;
}

function findBestMove(board) {
    let bestScore = -Infinity;
    let bestColumn = -1;
    for (const column of columnOrder) {
        const row = dropDisc(board, column, 'O');
        if (row == -1) {
            continue;
        }
        const score = minimax(board, 1, false, bestScore, Infinity);
        board[row][column] = '';
        if (score > bestScore) {
            bestScore = score;
            bestColumn = column;
        }
    }
    return bestColumn;
}

findBestMove() passes bestScore as alpha, just like in tic-tac-toe. A column only matters if it can beat the best column so far, so minimax can stop searching a column as soon as it's clear that it can't.

Together, these tricks make a big difference. Say you start in the middle column, and the AI looks 6 moves ahead. Plain minimax looks at 137,255 positions to find its reply. Add alpha-beta pruning, try the middle columns first and pass bestScore as alpha, and it's only 2,086.

The AI in the demo below uses exactly this code. You play red and go first. Pick a depth and try to beat the AI. With a depth of 2, the AI only looks at its own move and your reply to it. With 6, it sees most of your traps coming. Under the board, you can see how many positions the AI looked at for its last move, and how long that took on your device:

Depth

Every extra move the AI looks ahead multiplies the work by up to 7, because there are 7 columns to try. The depth also works well as a difficulty level for four in a row. At a low depth, the AI plays fast and makes mistakes. At a high depth, it's strong but slow.

Common questions about the minimax algorithm

Is minimax artificial intelligence?

Yes, in the classic sense. Minimax is one of the oldest techniques in game AI, and you'll find it in every textbook on artificial intelligence. It isn't machine learning, though: it doesn't learn from earlier games, but works out the best move from the rules, from scratch, every turn. Games use other kinds of AI too. The tutorial about pathfinding shows how to find a way around walls, and the one about steering behaviors shows how to make characters move on their own.

Can you beat a minimax tic-tac-toe AI?

No. Tic-tac-toe is a solved game: if both players play perfectly, it always ends in a draw. A minimax AI that looks ahead to the end of the game plays perfectly, so the best you can get is a draw. That's why tic-tac-toe games against an AI often have a difficulty level.

Why does my minimax AI make strange moves?

Usually, it's one of three things. If the score doesn't include the depth, the AI won't always take a quick win. If you don't empty the square after each move, all the scores come out wrong. And if the players are mixed up, for example when the AI picks the lowest score instead of the highest, it plays badly.

What's the difference between minimax and negamax?

Negamax is a shorter way to write the same algorithm. It always scores a board from the point of view of the player whose turn it is. A score that's good for one player is just as bad for the other. So negamax flips the sign of the score it gets back from the other player's turn: score = -negamax(board, depth + 1). Then it can always take the highest score, without a separate branch for each player. It picks exactly the same moves as minimax.

How do chess engines use minimax?

Chess engines use minimax with alpha-beta pruning too, but chess has far more positions than four in a row, so they add a lot on top of it. They search one move deeper each round, for as long as the clock allows, which is called iterative deepening. They store the scores of positions they've already seen in a transposition table, they try the most promising moves first, and their evaluation functions know a lot about chess. The Chess Programming Wiki explains all of it. For Go, minimax doesn't work well, because there are too many moves per turn, so Go programs use Monte Carlo tree search instead.

Can minimax play games with dice or hidden cards?

Games with dice, yes, using a version called expectiminimax. It adds a turn for the dice between the players' turns, and on that turn, it takes the average score of all possible rolls. Games with hidden cards, like poker, are a different story. The AI doesn't know the cards of the other players, so it can't build a game tree from what it sees.

Why does my page freeze while the AI is thinking?

JavaScript runs your code on the same thread that updates the page, so while minimax is busy, nothing else happens. For a few hundred milliseconds, that's fine. If the AI needs longer, move the search to a Web Worker, a script that runs in the background. Send it the board with postMessage(), and it sends the move back when it's done.

Can you always win at four in a row if you go first?

Yes, if you play perfectly. In 1988, James D. Allen and Victor Allis each showed that the first player can always win by starting in the middle column. A perfect AI for four in a row needs a much deeper search than the one on this page, though. With a depth of 6, the AI is strong, but it isn't perfect.

Example code: tic-tac-toe with minimax

Here's an example page that puts the basics from this tutorial together in a single HTML file. It's a game of tic-tac-toe against the AI, which uses minimax() with depth-based scoring and alpha-beta pruning. You play X and go first, and the AI answers with O. When a game is over, click the board to play again. Paste the code below into an HTML file and open it in your browser:

Conclusion

The minimax algorithm lets a computer play a two-player game by looking ahead. It tries every move, assumes that the opponent always plays their best reply, and picks the move with the best result. In tic-tac-toe, it can look ahead all the way to the end of the game, so it never loses. Including the depth in the score makes it win fast, alpha-beta pruning skips the moves that don't matter, and a difficulty level makes it beatable again.

For a bigger game like four in a row, the AI looks ahead a few moves, and lets an evaluation function estimate the rest. That works for lots of board games: write the code for the moves, the check for a winner and an evaluation function for your game, and minimax() stays almost the same.

That's all for now. If you have any questions, feel free to ask them in the comment section. You can