C#: solving tic-tac-toe with minimax
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.
C#
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);
}
}