Skip to content
Tutorials Center
My learning

Topics

Lesson 157 of 171 ยท Projects

Project: Tic-Tac-Toe

Build tic-tac-toe in C++ in four stages - a std::array board, enum class marks, validated moves from input, win detection and an unbeatable minimax computer player.

Tic-tac-toe is small enough to fit in your head and rich enough to teach real program design. A board has to be represented, moves have to be validated, wins and draws have to be detected, and then comes the fun part: a computer player that never loses. Because the game has fewer than 6,000 reachable positions, the computer can simply look at every possible continuation and pick the best one. The algorithm that does that, minimax, is the same idea behind chess engines, just without the shortcuts chess needs.

You'll build the game in four stages: the board and win detection, a two-player game driven by the Input box, a minimax opponent, and finally a polished version with game modes and alpha-beta pruning, which makes the search more than ten times faster. Every stage is a complete program (each run starts fresh), and the moves come from the Input box, one cell number per line, so you can replay any game by editing the input.

You'll use std::array, enum class, constexpr, structured bindings, algorithms like none_of, std::optional, references and recursion.

Stage 1: the board

What's in a cell? A cell is empty, an X or an O. That's a closed set of three values, which is exactly what a scoped enumeration is for:

C++
enum class Mark : char { None = ' ', X = 'X', O = 'O' };

Compared with using char directly, enum class gives you type safety: a Mark can't be mixed up with an arbitrary character or integer, and the compiler rejects board[0] = 'Q'. Giving the enumerators char values is a small convenience. std::to_underlying(Mark::X) (C++23) returns 'X', so printing a mark needs no lookup table.

What's a board? Nine cells, always nine. A std::array<Mark, 9> is the natural fit: fixed size, stored inline with no heap allocation, copyable with =, and it knows its own size. The cells are numbered 0โ€“8 internally and 1โ€“9 for players, laid out row by row:

TEXT
 1 | 2 | 3
---+---+---
 4 | 5 | 6
---+---+---
 7 | 8 | 9

Why not std::array<std::array<Mark, 3>, 3>? A 2D array matches the picture, but almost everything the program does (looping over cells, trying every move, checking lines) is easier with one index. The rows and columns only matter when printing, where row * 3 + col converts between the two (see Multidimensional Arrays and Matrices).

How do you detect a win? There are exactly eight winning lines: three rows, three columns, two diagonals. Instead of writing eight if statements, the program lists them as data in a constexpr table and loops over it. Data is easier to check than logic: you can verify the table at a glance, and the same table will be reused for every win check, including the thousands the computer player makes.

C++ Stage 1: the board and win detection

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 std::cin or std::getline), it gets the next line from this box.

Empty cells are printed as their number, so the board doubles as a menu of legal moves. That's a small UX decision with a big effect: players never have to remember the numbering.

Three C++ details are worth noticing:

  • Board empty; empty.fill(None); instead of Board empty{};. Value-initialization ({}) sets every element to zero, and zero is not Mark::None here, because None is ' ' (32). Mark{0} is a valid value of the enum's underlying type, but it isn't any named mark, so winner and print_board would misbehave silently. Either fill explicitly, or make the "empty" enumerator the one with value 0. When an enum has a meaningful "nothing" value, it's a good habit to make it 0.
  • for (const auto& [a, b, c] : winning_lines) uses a structured binding to unpack each std::array<int, 3> into three names (see std::pair and std::tuple).
  • using enum Mark; (C++20) brings the enumerators into the current scope, which makes the hand-written boards readable. Keep it inside small scopes like this one; elsewhere, Mark::X is clearer.

Stage 2: two players and the Input box

Stage 2 turns the board into a game: X and O take turns, each move is read from the Input box, and the game ends with a win or a draw.

Untrusted input. A move is valid only if it's a whole number from 1 to 9 and that cell is empty. read_move reads a line, checks both, prints a helpful message if either check fails, and reads the next line, until it gets a valid move. Parsing uses std::from_chars, which rejects seven, 5x and the empty string cleanly, because it reports exactly how much of the text it consumed (see Converting Between Strings and Numbers).

Running out of input. In a terminal, a player could keep typing forever. In the Input box, the moves eventually end, and std::getline fails. That's not a bug in the game, but the program must handle it. read_move therefore returns std::optional<int>: a cell index, or "no move at all". The game loop checks it and stops politely. Returning an optional is clearer than a magic value like -1, because the type itself says "this might not have a value" (see std::optional, std::variant, std::any and std::expected).

The game loop follows the order every turn-based game uses: get a move, apply it, show the result, check for the end, switch players. Checking for a win before checking for a full board matters: a move that fills the last cell can also complete a line, and that's a win, not a draw.

C++ Stage 2: a two-player game from the Input box

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 std::cin or std::getline), it gets the next line from this box.

In the sample game, O tries to play seven, then 12, then the already-taken 5. Each mistake gets its own message, and O still gets to move. X then completes the diagonal 1-5-9. Delete the last line of input and run it again to see the "no more moves" ending.

Stage 3: a computer player with minimax

Now for the interesting part. How does a program choose a good move?

The idea

Imagine the game as a tree. The current position is the root. Each legal move leads to a child position, each reply to a grandchild, and so on until every branch ends in a win, a loss or a draw. If you could see the whole tree, choosing a move would be easy, assuming the opponent also plays perfectly:

  • At the bottom, score each finished game from the computer's point of view: positive for a win, negative for a loss, zero for a draw.
  • On the computer's turn, a position is worth the maximum of its children's scores, because the computer will pick its best move.
  • On the opponent's turn, a position is worth the minimum of its children, because the opponent will pick the move that's worst for the computer.

That's minimax: alternate between maximizing and minimizing, all the way down. The recursive function mirrors the definition directly. Its base cases are the finished games; its recursive case tries every empty cell (see Recursion).

Preferring faster wins

If the score were just +1 for a win, the computer would see no difference between winning now and winning in five moves, and it might "toy" with a beaten opponent, or worse, wander until a mistake appears. Including the depth fixes that: a win is worth 10 - depth and a loss depth - 10. A win in one move (10 โˆ’ 1 = 9) beats a win in three (10 โˆ’ 3 = 7), and when losing is certain, the computer delays it as long as possible. The 10 just needs to be larger than the maximum depth of 9.

Make the move, recurse, undo it

The search explores hundreds of thousands of positions. Copying the board for each one would work (a std::array<Mark, 9> is only 9 bytes), but the classic technique is make/unmake: write the mark into the cell, recurse, then set the cell back to None. The search function takes Board& and leaves it exactly as it found it. best_move takes its board by value, so the caller's board is never touched, even temporarily, and the search works on its own copy.

The search also counts the positions it visits in nodes, passed by reference, so you can see how much work each move takes.

C++ Stage 3: human against minimax

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 std::cin or std::getline), it gets the next line from this box.

The sample game is a careful one: X takes the center, then blocks every threat, and it ends in a draw. That's the best anyone can do against minimax, because tic-tac-toe is a solved game: with perfect play from both sides, it's always a draw. Now try to lose. Change the input to 5, 9, 4 and watch the computer take its chance: after X's 4, O completes the top row.

Look at the search counts. The computer's first reply searches about 55,000 positions; later replies search far fewer, because the tree shrinks with every filled cell. From an empty board, the full minimax tree has 549,945 positions (the number of distinct move sequences; the number of distinct boards is much smaller, because different move orders reach the same board). Modern CPUs handle that in a few milliseconds, but chess has roughly 10120 sequences, so real game engines can't search everything. They need pruning.

Stage 4: alpha-beta pruning and game modes

The final stage adds two features.

Alpha-beta pruning

Minimax evaluates every branch, even ones that obviously can't matter. Suppose the computer has already found a move that guarantees a draw (score 0). Now it examines another move, and the first reply it checks lets the opponent win. The computer doesn't need to look at the opponent's other replies: the opponent already has a way to make this move bad, so it's worse than the draw the computer already has. That entire subtree can be skipped.

Alpha-beta pruning formalizes that with two numbers passed down the recursion:

  • alpha: the best score the maximizing player (the computer) is already guaranteed elsewhere,
  • beta: the best score the minimizing player (the opponent) is already guaranteed elsewhere.

As soon as alpha >= beta, the current position can't affect the final decision, and the loop breaks. The result is exactly the same move minimax would choose (the root keeps the first move with the best score, as before), found with far less work. How much less depends on move order: the earlier good moves are tried, the more gets pruned.

Game modes

The first line of the Input box now chooses who plays, and several games can follow each other in one input:

TEXT
x      you play X (you move first), the computer plays O
o      the computer plays X and moves first, you play O
two    two humans
watch  the computer plays both sides

Each player's controller (Human or Computer) is stored in a small Setup struct, selected by parse_setup, which returns std::nullopt for an unknown mode. The game itself moves into a play function that returns the winner (or Mark::None for a draw, or std::nullopt when the input runs out), and main keeps a tally across games. The computer's move now comes back as a SearchResult struct holding the move, its score and the node count, so the program can explain its verdict: a positive score means "I'm going to win", zero means "best play from here is a draw".

C++ Stage 4: modes, alpha-beta and a tally

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 std::cin or std::getline), it gets the next line from this box.

Read the computer's commentary in the first game. Its opening move from an empty board now searches 20,865 positions instead of the 549,945 plain minimax needed, about 26 times fewer, and it picks the same cell (1). In the second game the computer plays both sides, and the result is always a draw: two perfect players can't beat each other. That's the strongest possible test that the search is correct. If a "watch" game ever ended in a win, there would be a bug in the scoring.

Why the result of play is std::optional<Mark>

A game has four outcomes: X wins, O wins, draw, or "abandoned because the input ran out". Mark covers the first three (None meaning draw), and the optional adds the fourth without inventing a fake mark. Each return in play states its outcome directly, and main handles each case once.

++(*result == Mark::X ? x_wins : o_wins);

The conditional operator can yield an lvalue when both branches are lvalues of the same type, so this increments whichever counter matches. It's compact, but if your team finds it too clever, an if/else says the same thing (see Operator Precedence and the Conditional Operator).

Comparing the two searches

Stage 3's best_move and stage 4's choose_move must always pick the same move. That's a perfect opportunity for a test: put both functions in one program, generate many positions (for example, by playing random legal moves from the empty board), and assert that they agree. Writing that check is one of the ideas below.

Ideas to extend it

  • Prove the pruning is safe. Copy stage 3's minimax into stage 4, play random positions using <random>, and assert that both searches return the same move and score (see Random Numbers and Assertions and Debugging).
  • Better move ordering. Try the center first, then the corners, then the edges. Count how many fewer nodes alpha-beta visits.
  • A transposition table. Different move orders reach the same board. Cache scores in a std::unordered_map keyed by the board encoded as a number (each cell is 0, 1 or 2, so the board is a base-3 number below 39 = 19,683), and watch the node count drop again.
  • Difficulty levels. Make an "easy" computer that picks a random legal move 50% of the time, or a "medium" one that only searches two moves ahead.
  • Bigger boards. Generalize to a 4ร—4 board where you need four in a row. The winning-lines table becomes something you generate in a loop, and the full search becomes too slow, so you'll need a depth limit and a heuristic score.
  • Undo. Keep a std::vector<int> of moves so a human can type u to take back the last turn.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Mark is declared as enum class Mark : char { None = ' ', X = 'X', O = 'O' };. What do the elements of Board board{}; contain?

    Value-initialization zero-initializes the elements, and zero isn't the value of None (which is 32, a space). That's why the program fills the board with Mark::None explicitly.
  2. 2. Why does the game loop check for a winner before checking whether the board is full?

    When the ninth mark completes a line, the board is full and won at the same time. Checking the win first reports the correct result.
  3. 3. In minimax, why is a win scored as 10 - depth instead of a constant?

    A win found deeper in the tree is worth less, so the search prefers the quickest win. Likewise depth - 10 makes a later loss less bad than an earlier one.
  4. 4. What does alpha-beta pruning change compared with plain minimax?

    Alpha-beta skips subtrees once it's clear the opponent (or the computer) would never allow them. The chosen move is the same; only the amount of work changes.
  5. 5. The computer plays both sides in "watch" mode. What result should every such game have, if the search is correct?

    Tic-tac-toe is a solved game, and perfect play from both sides always draws. A win in watch mode would reveal a bug in the scoring or the search.

Summary

  • Model closed sets of values with enum class; give the "empty" value some thought, because {} initializes enums to zero, which may not be a named value.
  • A fixed-size grid fits naturally in a std::array; one index plus row * 3 + col for display is often simpler than nested arrays.
  • Express rules as data where you can: a constexpr table of the eight winning lines replaces eight if statements.
  • Treat input as untrusted. Validate with std::from_chars, re-prompt on errors, and return std::optional when there may be no move at all.
  • Minimax scores finished games, maximizes on the computer's turn and minimizes on the opponent's. Depth-adjusted scores make it prefer quick wins.
  • Make/unmake moves on a Board& inside the search, and let the top-level function take its board by value.
  • Alpha-beta pruning returns the same move as minimax while visiting a fraction of the positions. Perfect play against itself always draws, which makes a great correctness test.

Next: Project: A Small Matrix Library, where you'll write a Matrix class template with operator overloading, exceptions for size mismatches and tests with assert.