C#: solving tic-tac-toe with minimax

Before you start

C# recursion and arrays.

Search the complete game tree and show that perfect play by both sides ends in a draw.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Minimax searches a game tree to its end. The player who wants to maximize the score (X, scored +1 for a win) picks the child with the largest value. The other player (O, scored −1 for a win) picks the smallest. A draw scores 0. The value of the starting position is the result when both sides play perfectly.

Tic-tac-toe is small enough to search completely: the tree from the empty board contains 549,946 positions. The program makes a move, searches the resulting position recursively, undoes the move, and keeps the best value. The root value is 0, so with perfect play the game is a draw.

Code example

using System;

class Program {
  static int nodes = 0;
  static readonly int[][] Lines = {
    new[] { 0, 1, 2 }, new[] { 3, 4, 5 }, new[] { 6, 7, 8 },
    new[] { 0, 3, 6 }, new[] { 1, 4, 7 }, new[] { 2, 5, 8 },
    new[] { 0, 4, 8 }, new[] { 2, 4, 6 },
  };

  static char Winner(char[] b) {
    foreach (int[] line in Lines) {
      if (b[line[0]] != ' ' && b[line[0]] == b[line[1]] && b[line[1]] == b[line[2]]) {
        return b[line[0]];
      }
    }
    return ' ';
  }

  static int Minimax(char[] b, char turn) {
    nodes++;
    char winner = Winner(b);
    if (winner == 'X') return 1;
    if (winner == 'O') return -1;

    bool moved = false;
    int best = turn == 'X' ? -2 : 2;
    for (int i = 0; i < 9; i++) {
      if (b[i] != ' ') continue;
      moved = true;
      b[i] = turn;
      int value = Minimax(b, turn == 'X' ? 'O' : 'X');
      b[i] = ' ';
      best = turn == 'X' ? Math.Max(best, value) : Math.Min(best, value);
    }
    return moved ? best : 0;
  }

  static void Main() {
    char[] board = new string(' ', 9).ToCharArray();
    Console.WriteLine("value of the empty board: " + Minimax(board, 'X'));
    Console.WriteLine("positions searched: " + nodes);
  }
}

Output

value of the empty board: 0
positions searched: 549946

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

3class Program {

4 static int nodes = 0;

5 static readonly int[][] Lines = {

6 new[] { 0, 1, 2 }, new[] { 3, 4, 5 }, new[] { 6, 7, 8 },

7 new[] { 0, 3, 6 }, new[] { 1, 4, 7 }, new[] { 2, 5, 8 },

8 new[] { 0, 4, 8 }, new[] { 2, 4, 6 },

9 };

11 static char Winner(char[] b) {

12 foreach (int[] line in Lines) {

13 if (b[line[0]] != ' ' && b[line[0]] == b[line[1]] && b[line[1]] == b[line[2]]) {

14 return b[line[0]];

15 }

16 }

17 return ' ';

18 }

20 static int Minimax(char[] b, char turn) {

21 nodes++;

22 char winner = Winner(b);

23 if (winner == 'X') return 1;

24 if (winner == 'O') return -1;

26 bool moved = false;

27 int best = turn == 'X' ? -2 : 2;

28 for (int i = 0; i < 9; i++) {

29 if (b[i] != ' ') continue;

30 moved = true;

31 b[i] = turn;

32 int value = Minimax(b, turn == 'X' ? 'O' : 'X');

33 b[i] = ' ';

34 best = turn == 'X' ? Math.Max(best, value) : Math.Min(best, value);

35 }

36 return moved ? best : 0;

37 }

39 static void Main() {

40 char[] board = new string(' ', 9).ToCharArray();

41 Console.WriteLine("value of the empty board: " + Minimax(board, 'X'));

42 Console.WriteLine("positions searched: " + nodes);

43 }

44}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
X starts from a value worse than any result; O from one better than any result.	`—`	—
Try a move.	`board changes`	—
Undo the move so the next candidate starts from the same position.	`board changes`	—
Neither side can force a win, so the value is 0: a draw.	`value = 0`	value of the empty board: 0
Every node of the full game tree was visited.	`nodes = 549946`	value of the empty board: 0 positions searched: 549946

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

Exponential in the number of moves: up to 9! move sequences here.

Forgetting to undo the move corrupts the board for later branches.
Plain minimax revisits repeated positions. Alpha-beta pruning or caching positions cuts the search enormously.
Larger games such as chess are far too big to search completely. They need a depth limit and an evaluation function.

Try it yourself

Why is X's best-value start −2?

Reveal answer and reasoning

Any real result is −1, 0, or +1, so −2 is guaranteed to be replaced by the first value found.