Note: To allow manually exploring the concepts outlined here, the algorithm described is implemented in the Microsoft Excel spreadsheet accompanying the library release.

Playing Board

In TicTacToe, there are 9 positions and 8 wins. Each position we label as a to i like this:

a  b  c
d  e  f
g  h  i

Winning Moves

We can assign a matrix of win contributions to each position as a row of 8 elements.

[D1, H1, H2, H3, V1, V2, V3, D2]

where D1 is the main diagonal (left to right), H1, H2, H3 are horizontal wins, V1, V2, V3 are vertical wins, and D2 is the other diagonal.

For each win element, if a board position occurs in a win, give it a 1, like so:

[a] = [1, 1, 0, 0, 1, 0, 0, 0]
[b] = [0, 1, 0, 0, 0, 1, 0, 0]
[c] = [0, 1, 0, 0, 0, 0, 1, 1]
[d] = [0, 0, 1, 0, 1, 0, 0, 0]
[e] = [1, 0, 1, 0, 0, 1, 0, 1]
[f] = [0, 0, 1, 0, 0, 0, 1, 0]
[g] = [0, 0, 0, 1, 1, 0, 0, 1]
[h] = [0, 0, 0, 1, 0, 1, 0, 0]
[i] = [1, 0, 0, 1, 0, 0, 1, 0]

Now, reform this into a giant 9x8 matrix. This matrix remains constant for all games.

	D1	H1	H2	H3	V1	V2	V3	D2
a	1	1			1
b		1				1
c		1					1	1
d			1		1
e	1		1			1		1
f			1				1
g				1	1			1
h				1		1
i	1			1			1

The Algorithm

The game win matrix [M] starts clean. Here we assume

[M] = [0, 0, 0, 0, 0, 0, 0, 0]

Player 1 makes the first move, say position [a]. The line for positions [a] is added to the game matrix [M] to give an game position:

[M] = [1, 1, 0, 0, 1, 0, 0, 0]

Player 2’s move will subtract from the game matrix. If they take position [e], the resulting game matrix will be

[M] = [1, 1, 0, 0, 1, 0, 0, 0] - [1, 0, 1, 0, 0, 1, 0, 1] = [0, 1,-1, 0, 1,-1, 0,-1]

And so-on for subsequent moves, alternately adding and subtracting from [M].

We therefore have a way of tracking how the game is progressing and, more importantly, to test a move against the current board to determine which is the best move at any time.

The best move, in order of importance, will be one that

Makes a 3 or -3 (depending on the player), because this means we have made 3 in a row, column or diagonal.
Makes as many 2’s as possible provided there are no 2 or 1 of opposite sign, as it means other player would win the match. Leaving 2 2’s will mean that we are guaranteed to win on the next turn. Leaving a 2 of the opposite sign means that the other player will win next turn.
Make as many 2’s into 1’s as a last resort. A 2 now will turn into a 3 the next move, and 3 means someone wins!
Make the highest number of 1 provided there are no 2 of opposite sign, as it means other player would win the match.

If there is more than one ‘best’ move than it is possible to select randomly between choices that fit the highest criterion. This makes the algorithm slightly unpredictable and can result in moves that allow the other player to win the game, thus relieving the boredom of always losing against the computer!

The game is over when there are any 3’s or -3’s and the column in which this number appears will also tell exactly where to strike through for wins.