An unbeatable tic-tac-toe in 30 lines

Tic-tac-toe has 255,168 possible games. That is small enough to search completely, which makes it the classic introduction to minimax: assume your opponent plays perfectly, and pick the move whose worst case is best.

The board

Nine cells, each 'X', 'O' or empty.

type Cell = 'X' | 'O' | null
const LINES = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
 
function winner(board: Cell[]): Cell {
	for (const [a, b, c] of LINES)
		if (board[a] && board[a] === board[b] && board[a] === board[c]) return board[a]
	return null
}

Minimax

Score a finished game from the point of view of the AI: win is positive, loss is negative, draw is zero. Subtracting the depth makes it prefer a fast win and a slow loss.

function minimax(board: Cell[], player: 'X' | 'O', ai: 'X' | 'O', depth = 0): number {
	const won = winner(board)
	if (won) return won === ai ? 10 - depth : depth - 10
	if (board.every(Boolean)) return 0
 
	const scores = board.flatMap((cell, i) => {
		if (cell) return []
		const next = board.with(i, player)
		return [minimax(next, player === 'X' ? 'O' : 'X', ai, depth + 1)]
	})
	return player === ai ? Math.max(...scores) : Math.min(...scores)
}

Proving it never loses

A claim like "unbeatable" deserves a test. Play every possible human game against the AI and assert that the human never wins.

function humanCanWin(board: Cell[]): boolean {
	return board.some((cell, i) => {
		if (cell) return false
		const afterHuman = board.with(i, 'X')
		if (winner(afterHuman) === 'X') return true
		if (afterHuman.every(Boolean)) return false
		return humanCanWin(afterHuman.with(bestMove(afterHuman, 'O'), 'O'))
	})
}
 
expect(humanCanWin(Array(9).fill(null))).toBe(false)

You can play against this implementation in the games section.