Skip to content
Tutorials Center
My learning

Topics

Lesson 114 of 135 ยท Projects

Project: Tic-Tac-Toe

Build tic-tac-toe in C in four stages - a 2D array board, validated moves from the Input box, win and draw detection, and a minimax computer player with alpha-beta pruning.

Tic-tac-toe is the perfect size for a first game in C. The whole state fits in a 3 by 3 array of characters, the rules take a dozen lines, and yet the project touches everything a real program needs: a data representation, input that can't be trusted, a game loop, and an end condition that's easy to get subtly wrong. Then comes the best part. The game is small enough that the computer can examine every possible continuation of a position and pick a move that never loses. The algorithm that does this, minimax, is the foundation of game-playing programs from checkers to chess.

You'll build the game in four stages: the board and win detection, a two-player game, a computer opponent using minimax, and a final version with game modes and alpha-beta pruning, which gets the same answers while searching a small fraction of the positions. Each stage is a complete program, because every run starts fresh. The moves come from the Input box, one cell number per line, so you can replay any game by editing the input.

The project uses multidimensional arrays, functions with out-parameters, safe input with fgets and strtol, recursion and structures.

Stage 1: the board and win detection

Representing the board. A board is three rows of three cells, and C has exactly the right type for it: char board[3][3]. Each cell holds 'X', 'O' or ' ' (a space) for an empty cell. Using printable characters as the cell values has a nice side effect: the program can print a cell directly with %c, with no lookup table.

Players don't think in rows and columns, though; they think "top right". The program numbers the cells 1 to 9, row by row, like this:

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

Converting between the two is a matter of integer division and remainder. For a cell number n from 1 to 9, the row is (n - 1) / 3 and the column is (n - 1) % 3; going back, the number is row * 3 + col + 1. This is the same row-major arithmetic C itself uses to store a 2D array in memory (see Multidimensional Arrays).

When print_board shows an empty cell, it prints that cell's number instead of a blank. That's a small design decision with a big payoff: the board doubles as a menu of legal moves, and nobody needs to memorize the numbering.

Passing the board to functions. A parameter declared as const char board[3][3] is really a pointer to the first row, of type const char (*)[3]. The function can index it as usual, and the const promises that it won't change the board. Two consequences are worth knowing:

  • Inside the function, sizeof board is the size of a pointer (8 bytes on our server), not 9. GCC even warns about it. Inside main, where board is a real array, sizeof board is 9.
  • The first dimension in the parameter is ignored by the compiler, but the second one ([3]) is essential: without the row length, the compiler couldn't compute where board[2][1] is.

Detecting a win. There are eight winning lines: three rows, three columns and two diagonals. One loop checks row i and column i at the same time, and the two diagonals share the center cell, so they're checked together. A line counts only if its first cell isn't empty, otherwise three empty cells would "win" for nobody.

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 scanf or fgets), it gets the next line from this box.

The three test boards cover the three possible states: a game in progress, a win (O down the middle column) and a full board with no line. Writing a few hand-made positions like these before writing the game loop is a cheap way to make sure the rules are right. Once moves come from input, a bug in winner would be much harder to spot.

Passing a non-const array such as o_column to a const char board[3][3] parameter is fully allowed in C23. Older standards technically didn't allow this conversion for 2D arrays without a cast, and some compilers warn about it in C17 mode. If you need code that compiles warning-free everywhere, wrap the array in a struct (typedef struct { char cells[3][3]; } board;) and pass const board *.

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. The interesting part is read_move, because input is untrusted. A move is valid only if it's a whole number, between 1 and 9, and names an empty cell. Anything else gets a helpful message, and the function reads the next line.

Reading a line safely. read_move reads whole lines with fgets, never with a bare scanf("%d"). With scanf, typing seven leaves those letters in the input forever, and the loop would spin without making progress (see Reading Input). fgets always consumes the line. Two details complete the job:

  • strcspn(line, "\n") finds the newline so it can be removed. If there's no newline, the line was longer than the buffer, and the rest of it is discarded with a getchar loop. Otherwise the leftover characters would be read as the next "move".
  • strtol(line, &end, 10) converts the text and sets end to the first character it didn't use. If end == line, there was no number at all; if anything but whitespace follows the number (as in 5x), the input is rejected. This is the safe parsing pattern from Converting Strings and Numbers. A huge number like 99999999999999999999 makes strtol return LONG_MAX, which the range check rejects too.

Returning two results. A move has a row and a column, and the function also has to say whether it got a move at all. It returns bool (false when the input runs out) and stores the row and column through two pointer parameters. That's the standard C way to return several values, covered in Pointers and Functions.

Echoing the input. The Input box doesn't echo what it feeds to the program the way a terminal does, so read_move prints the line it read right after the prompt. The transcript then reads like a real session.

The order of the end checks. After each move, the loop checks for a win before checking for a full board. The move that fills the ninth 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 scanf or fgets), it gets the next line from this box.

Look at the second X move in the transcript. seven isn't a number, 12 is off the board and 1 is taken, so each gets its own message, and only 3 is accepted. Later, O plays 9 instead of blocking at 6, and X completes the middle row. Try deleting the last few lines of the Input box: the program reports "(no more input)" and stops politely instead of looping forever.

clear_board uses two loops instead of memset(board, ' ', sizeof board). Inside the function, sizeof board is the size of a pointer, so that memset would fill 8 bytes on a 64-bit machine and leave the last cell untouched. memset(board, ' ', 3 * 3) works, but the loops make the intent obvious and can't silently go wrong if the board size changes.

Stage 3: a computer player with minimax

A human player can now face the computer. The computer plays O, and on each turn it asks one question about every empty cell: "If I play here, and both sides play perfectly from then on, how does the game end?" Then it picks the cell with the best answer.

Minimax answers that question with recursion. To score a position:

  1. If the game is over, the score is known: a computer win is good (positive), a loss is bad (negative), a draw is 0.
  2. Otherwise, try every legal move for the player whose turn it is, and score each resulting position recursively.
  3. On the computer's turn, the position is worth the maximum of those scores, because the computer will pick its best move. On the opponent's turn, it's worth the minimum, because a perfect opponent picks the move that's worst for the computer.

That alternation of max and min gives the algorithm its name. It ends because every move fills a cell, so each recursive call is one level closer to a full board: the base case is always reached within nine levels.

Preferring fast wins. If every win scored the same, the computer might wander toward a win in five moves while it could win right now, and a human watching would think it's broken. So a win scores 10 - depth and a loss depth - 10, where depth counts moves since the search started. A quick win scores higher than a slow one, and a loss that can't be avoided is postponed as long as possible.

Make, recurse, unmake. The search doesn't copy the board for each move. It writes the move into the board, recurses, and then writes the space back. Thousands of positions are explored using a single 9-byte array, and when the search returns, the board is exactly as it was. The one rule: every path out of the loop body must undo its move, which is why the undo comes immediately after the recursive call.

The search also counts the positions it examines, through a long * parameter, so you can see how much work each move takes.

C Stage 3: playing 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 scanf or fgets), it gets the next line from this box.

You play X and open in the corner. The computer answers in the center, the only reply to a corner opening that doesn't lose, after examining 59,704 positions. Each later move needs far fewer, because fewer cells are empty: 1,052 for its second move. The game ends in a draw, which is the best either side can force.

Now change the third line of the Input box from 8 to 3. Instead of blocking, X builds its own line, and the computer plays 8 and wins at once, because a win now (10 - 1 = 9) beats every other score. Try to beat it from any opening: you can't. Tic-tac-toe is a solved game, and with perfect play from both sides, every game is a draw.

The most common minimax bug is forgetting to undo a move on one path, for example by adding an early return between the "make" and "unmake" lines. The board then slowly fills with phantom moves during the search, and the computer starts making illegal or absurd moves. If your version behaves strangely, print the board after best_move returns: it must be unchanged.

Stage 4: game modes and alpha-beta pruning

The final stage adds two features.

Game modes. The first line of the Input box chooses the mode: x (you play X and move first), o (the computer opens, and you play O) or watch (the computer plays both sides). An array bool computer_plays[2] records which side the computer controls, indexed by turn == 'O': 0 for X and 1 for O. A comparison in C yields the int 0 or 1, which makes it a valid index (see Booleans). An unknown mode prints a message and falls back to x, instead of guessing.

Alpha-beta pruning. Minimax examined 549,945 positions to choose the first move on an empty board. Most of that work is wasted. Suppose the computer has already found a move that guarantees a draw. While it examines the next move, it discovers that the opponent has a reply that wins. At that moment, it can stop: the opponent will never let it do better than "loss" with this move, and a draw is already in hand, so the move's exact score doesn't matter.

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

  • alpha is the best score the computer is already guaranteed somewhere along the current path.
  • beta is the best score the opponent is already guaranteed (the lowest score for the computer).

When alpha >= beta, the current position can't affect the final decision, because one of the players will steer away from it. The loop returns immediately and skips the remaining moves, along with their entire subtrees. The result is the same move as plain minimax, found with much less work.

To prove that claim, best_move runs both searches for every computer move, prints both position counts, and reports a bug on stderr if they ever choose different cells. A program that checks itself like this is far more trustworthy than one that merely seems to play well. Both searches use a shared final_score helper, so they can't disagree about the rules, and the search_stats struct keeps the two counters together.

C Stage 4: modes, alpha-beta and a self-check

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 scanf or fgets), it gets the next line from this box.

In watch mode, the computer plays both sides perfectly, and the game is a draw, as it must be. If watch mode ever produced a win, that would prove a bug in the scoring or the search, which makes it a great automated test. The numbers tell the story of pruning: for the opening move, plain minimax examines 549,945 positions and alpha-beta 20,865, about 26 times fewer. Over the whole game, it's 618,175 against 24,689. The "bug" line never appears, because both searches always choose the same cell.

Notice that X opens in cell 1 and then plays cell 2, which looks naive. Every move in those positions leads to a draw with perfect play, so they all score 0, and best_move keeps the first best move it finds (the > comparison, not >=). The computer is never worse than a draw; it just doesn't try to set traps. Making it prefer the center, or moves that give a weaker opponent more chances to go wrong, is a nice extension.

To play yourself, replace watch in the Input box with x followed by your moves, one per line, or with o to let the computer open.

Two more details:

  • Pruning at the root. best_move passes best_pruned as the starting alpha to each top-level search. Once one move is known to draw, the search for the next move can stop as soon as it proves "no better than a draw". A pruned search may return a value that is only an upper bound, but such a value is never greater than alpha, so it can't replace the move already chosen. That's why the two searches agree.
  • INFINITY_SCORE is just 100. Any value larger than every real score works. The real scores here stay between -10 and 10, so 100 is safe, and it avoids the classic mistake of negating INT_MIN, which overflows.

Ideas to extend it

  • Score display. Print the score of every legal move before the computer chooses, so you can see why it prefers one cell.
  • Smarter tie-breaking. Among equally scored moves, prefer the center, then corners, then edges.
  • A weaker opponent. Add a difficulty level where the computer sometimes picks a random legal move (see Random Numbers).
  • Bigger boards. Generalize to 4 by 4 with a SIZE constant. You'll find that full minimax becomes far too slow, which is exactly why real game engines limit search depth and use evaluation functions.
  • A struct board. Wrap the array in typedef struct { char cells[3][3]; } board; and pass const board *. Structs can be copied with =, which makes an "undo last move" feature easy.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. The cells are numbered 1 to 9 row by row. Which row and column does cell 6 map to with row = (n - 1) / 3 and col = (n - 1) % 3?

    (6 - 1) / 3 is 1 with integer division, and (6 - 1) % 3 is 2. Rows and columns are counted from 0, so that's the last cell of the middle row.
  2. 2. Inside static void clear_board(char board[3][3]), what does sizeof board give on our 64-bit server?

    An array parameter is adjusted to a pointer, here char (*)[3]. sizeof measures that pointer, not the caller's array, which is why memset(board, ' ', sizeof board) would be a bug.
  3. 3. Why does read_move use fgets and strtol instead of scanf with %d?

    When %d fails on text like seven, scanf leaves the characters in the stream. fgets reads the line no matter what is in it, and strtol with an end pointer reports exactly what was valid.
  4. 4. Why does a win score 10 - depth instead of a constant like 10?

    A win found after fewer moves gets a higher score, so the search picks the quickest win. Symmetrically, depth - 10 makes a later loss less bad than an earlier one.
  5. 5. Compared with plain minimax, what does alpha-beta pruning change in this program?

    Alpha-beta stops exploring a position as soon as one side is sure to steer away from it. The decision is unchanged, as the self-check in best_move confirms, but the opening move needs 20,865 positions instead of 549,945.

Summary

  • A 3 by 3 game board fits naturally in char board[3][3]; cell number n maps to row (n - 1) / 3 and column (n - 1) % 3.
  • A 2D array parameter is really a pointer to rows: the row length must be known, and sizeof inside the function measures the pointer.
  • Test the rules with hand-made boards before writing the game loop; check for a win before checking for a full board.
  • Read moves with fgets, parse with strtol and an end pointer, check the range and the cell, and handle the end of input. Return several results with a bool plus out-parameters.
  • Minimax maximizes on the computer's turn and minimizes on the opponent's; depth-adjusted scores make it prefer quick wins. Make and unmake moves on one board instead of copying it.
  • Alpha-beta pruning returns the same move with far less work (20,865 positions instead of 549,945 for the opening move). Running both searches and comparing them is a simple, powerful self-test.

Next: Project: Inventory with a Linked List, where you'll manage a list of items with add, remove, search and report commands, and save it to a binary file.