The Game#

Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Irish English) is a paper-and-pencil game for two players who take turns marking spaces in a three-by-three grid with X or O. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins. It is a solved game, meaning the outcome is always a forced draw if both players play optimally.

Wikipedia

How Does the AI Work?#

As you might guess, the AI anticipates all your possible moves. There are 9! (read as “nine factorial”) possible ways to fill a tic-tac-toe board, totaling 362,880. However, since players take turns placing X or O, many of these options are redundant (like filling the entire board with X). In reality, the board can be filled in 3^9 possible states, which equals 19,683. But how does the AI decide where to place its mark to ensure victory? The answer lies in its decision-making algorithm. So, what is this algorithm, and how does it work?

The Minimax Algorithm#

For almost any two-player game where one player’s win means the other’s loss (or a draw is possible), certain AI algorithms can compute the best move to secure a win. These algorithms evaluate all possible opponent responses and score each game state to determine the optimal move. While options like Monte Carlo Tree Search (MCTS) or Alpha-Beta pruning exist, I chose the minimax algorithm for tic-tac-toe because it performs exceptionally well here. Let’s explore how it works.

Imagine you’re X, and the AI is O. Suppose the game reaches this state:

First, we define rules to help the AI score each state. After every move, the AI checks if someone has won. If the AI wins, the state scores +10. If the opponent wins, the state scores -10. A draw results in a score of 0. If the game is still ongoing, the score is calculated based on subsequent possible moves. When the AI makes a decision, it’s called “maximizing”; otherwise, it’s “minimizing.”

Now, the AI must decide its next move. It identifies four possible options:

In this scenario, the AI (O) is maximizing. Option 4 results in an immediate win for the AI, scoring +10. For the other states, the game continues, and the AI switches to minimizing mode, evaluating the player’s potential moves. Here’s a diagram illustrating the process:

{ const img = document.getElementById("ai-flow-img"); if (img.requestFullscreen) { img.requestFullscreen(); } else if (img.webkitRequestFullscreen) { img.webkitRequestFullscreen(); } else if (img.msRequestFullscreen) { img.msRequestFullscreen(); } }} >

Zoom in to view better (click to fullscreen)

As you can see, beating the AI in tic-tac-toe is impossible because it evaluates all possible moves faster than any human. The best you can achieve is a draw. If you want a challenge, try playing a variant like 3D tic-tac-toe (though I can’t guarantee an AI won’t be waiting for you there either).

Now, to answer the title’s question: There’s no speed at which you can compute moves that would allow you to beat the AI. Even with the processing power of a quantum computer, defeating the AI is impossible. You can only force endless draws. The only way to “win” is by imposing speed constraints—for example, if each players has to move in 0.001 seconds, and you can compute moves in 0.0000000001 seconds while the AI takes 0.1 seconds. In this case, you’d win not by outplaying the AI but by forcing it to time out.

Implementation#

To implement tic-tac-toe with the minimax AI, use a 3x3 array to track the game state. After each player move, call the AI to determine its move. Here’s the AI class I wrote:

1
class TTT_AI {
2
    constructor(debug) {
3
        this.debug = debug;
4
    }
5

6
    setDebug(debug) {
7
        this.debug = debug;
8
    }
9

10
    randomEmptyPlace(gameBoard) {
11
        var emptyPlaces = [];
12
        for (var i = 0; i < gameBoard.length; i++) {
13
            for (var j = 0; j < gameBoard[i].length; j++) {
14
                if (gameBoard[i][j] == '') {
15
                    emptyPlaces.push([i, j]);
16
                }
17
            }
18
        }
19
        if (emptyPlaces.length == 0) {
20
            return false;
21
        } else {
22
            var randomIndex = Math.floor(Math.random() * emptyPlaces.length);
23
            return emptyPlaces[randomIndex];
24
        }
25
    }
26

27
    scores = {
28
        'O': 10,
29
        'X': -10,
30
        'tie': 0
31
    }
32

33
    minimax(gameBoard, depth, isMaximizing) {
34
        let aiGameBoard = gameBoard;
35
        let result = checkWinner(aiGameBoard);
36
        if (result !== false) {
37
            return this.scores[result];
38
        }
39

40
        if (isMaximizing) {
41
            let bestScore = -Infinity;
42
            for (let i = 0; i < aiGameBoard.length; i++) {
43
                for (let j = 0; j < aiGameBoard[i].length; j++) {
44
                    if (aiGameBoard[i][j] == '') {
45
                        aiGameBoard[i][j] = 'O';
46
                        let score = this.minimax(aiGameBoard, depth + 1, false);
47
                        aiGameBoard[i][j] = '';
48
                        bestScore = Math.max(score, bestScore);
49
                    }
50
                }
51
            }
52
            return bestScore;
53
        } else {
54
            let bestScore = Infinity;
55
            for (let i = 0; i < aiGameBoard.length; i++) {
56
                for (let j = 0; j < aiGameBoard[i].length; j++) {
57
                    if (aiGameBoard[i][j] == '') {
58
                        aiGameBoard[i][j] = 'X';
59
                        let score = this.minimax(aiGameBoard, depth + 1, true);
60
                        aiGameBoard[i][j] = '';
61
                        bestScore = Math.min(score, bestScore);
62
                    }
63
                }
64
            }
65
            return bestScore;
66
        }
67
    }
68

69
    pickBestMove(gameBoard) {
70
        let ai = 'O';
71
        let bestScore = -Infinity;
72
        let aiGameBoard = gameBoard;
73
        var bestMove;
74
        for (let i = 0; i < aiGameBoard.length; i++) {
75
            for (let j = 0; j < aiGameBoard[i].length; j++) {
76
                if (aiGameBoard[i][j] == '') {
77
                    aiGameBoard[i][j] = ai;
78
                    let score = this.minimax(aiGameBoard, 0, false);
79
                    aiGameBoard[i][j] = '';
80
                    if (score > bestScore) {
81
                        bestScore = score;
82
                        bestMove = [i, j];
83
                    }
84
                }
85
            }
86
        }
87
        return bestMove;
88
    }
89

90
    action(gameBoard) {
91
        if (this.debug) {
92
            console.log('AI is thinking...');
93
        }
94
        let bestMove = this.pickBestMove(gameBoard);
95
        console.log(bestMove);
96
        return bestMove;
97
    }
98
}

To use this AI, create an instance and call the action method, passing the gameBoard array as an argument:

1
function oAction() {
2
    var minimaxMovement = _AI.action(gameBoard);
3
    gameBoard[minimaxMovement[0]][minimaxMovement[1]] = 'O';
4
}

Here’s Github repo containing source code:

Conclusion#

In this article, I explained how the minimax algorithm works and why it guarantees the AI’s victory in tic-tac-toe. The same algorithm can be applied to other win-lose games like chess. Though, because of the vast amount of possible moves in chess, you may need to use other algorithms, such as alpha-beta pruning, as well.