# Tic Tac Toe Artificial Intelligence

During these days I played a bit with Artificial Intelligence for a project I am working on (big news on the horizon) and I’m coming with a brief introduction to the simplest game you can use to test artificial intelligence. Tic Tac Toe.

It’s a pencil-and-paper game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. (source: Wikipedia).

But most of all, it’s a good playground to apply artificial intelligence for four reasons:

It’s a perfect information game: all players know all moves that have taken place.

It’s a sequential game: when a player moves, the other player waits. And have the waiting player see the moves of the playing one.

It’s a zero sum game: if one player wins, the ohter loses. No cooperation.

It’s a non-random game: there isn’t any randomizing element such as dices, dealing of cards, and so on. Non-random games are pure strategy.

How many board configurations?

Now, we need to know how many boards configurations can exist in a Tic Tac Toe game. We’ll do it using php. We’ll code an empty board like a string with nine points (`.........`). Every point represents an empty cell. Then, with a recursive function, we’ll generate all possible board combinations, assuming the first player puts an `X` and the second player uses the `O`.

Here it is the script:

``` \$values){
echo "Combinations with ".trim(9-\$empty_spots)." symbol(s): \$values";
}

echo "Elapsed time: ".trim(\$end-\$start)."";

?>```

And the result is:

Combinations with 1 symbol(s): 9 – easy to see, in an empty board you can place an `X` in any of the nine spots

Combinations with 2 symbol(s): 72 – for each of the 9 different combinations with one symbol, you can place a `O` in any of the remaining eight spots. 9*8 =72.

Combinations with 3 symbol(s): 504 – for each of the 72 previous combinations, you can place an X in any of the remaining seven spots. 72*7 = 504.

Combinations with 4 symbol(s): 3024 – 504*6

Combinations with 5 symbol(s): 15120 – 3024*5

Combinations with 6 symbol(s): 60480 – 15120*4

Combinations with 7 symbol(s): 181440 – 60480*3

Combinations with 8 symbol(s): 362880 – 181440*2

Combinations with 9 symbol(s): 362880 – 362880*1. Same number as the combinations with 8 symbols, because when there are 8 symbols in game, you can only place an `O` in just one spot.

Elapsed time: 6.0569689273834 – six seconds to calculate 986409 different combinations. So the total possible board configurations are 986410, including the empty board.

According to these results, we can say the number of possible combinations in a board with n symbols is 9!/(9-n)!.

How many REAL board configurations?

Obviously there’s something wrong with this script because it does not consider when a player wins. If a player wins, the game is over and there are no more moves. So a lot of board configurations are impossible to reach.

So let’s modify a bit the script to check for victories and the number of necessary moves to win:

``` \$values){
echo "Combinations with ".trim(9-\$empty_spots)." symbol(s): \$values";
}

for(\$x=5;\$x<=9;\$x++){
echo "Wins in ".\$x." moves: \$wins[\$x]";
}

echo "Elapsed time: ".trim(\$end-\$start)."";

?>```

And the result is:

Combinations with 1 symbol(s): 9

Combinations with 2 symbol(s): 72

Combinations with 3 symbol(s): 504

Combinations with 4 symbol(s): 3024

Combinations with 5 symbol(s): 15120

Combinations with 6 symbol(s): 54720

Combinations with 7 symbol(s): 148176

Combinations with 8 symbol(s): 200448

Combinations with 9 symbol(s): 127872

Wins in 5 moves: 1440

Wins in 6 moves: 5328

Wins in 7 moves: 47952

Wins in 8 moves: 72576

Wins in 9 moves: 81792

Elapsed time: 4.7160170078278 – Less than five seconds to generate all possible Tic Tac Toe combinations.

This means `X` will win 1440+47952+81792 = 131184 times while `O` will win 5328+72576 = 77904 times. The first player has more chances to win.

How can we determine the drawn games? They are represented by the number of possible boards with nine symbols (127872) minus the number of wins at the 9th move (81792) = 46080 draws.

According to these results, next time we’ll introduce an algorithm to make the computer play Tic Tac Toe.

Meanwhile enjoy these results.

PS: anyone willing to translate this into AS3 or other languages?

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers