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:

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:

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?

  • I’m deeply interested in AI and have published an AI theory on my blog. I hope you will enjoy.

  • daniel

    Hi Emanuele
    I did a very similar project for sudoku live checker. the problem is always the time and performance.and working on that project I found the solution for gomoku ! the gomoku is extended tic tac toe version: 15×15 board and 5 in the row. so using just strict algorithm way can kill any processor(if adobe flash), so I found the way how to calculate only possibility I need not all of them. It is much more to calculate the risk first and then pick up one of the possibilities(small number). I wouldn’t give you ready to use code but I can give you the clue: all calculations are string based(collecting data as a string and perform search functions). in that scenario you need miliseconds to get result :) if you need more info mail me.

  • wow this is interesting..
    the next AI article will be for php or as3? =)

  • xPy

    The combinations are a lot less if you can skip the mirrored or rotated combinations…

    • xPy, you’re right. According to this wiki, there are actually 26,830 different games that can be played:

      http://en.wikipedia.org/wiki/Game_tree

      I guess the AI would need to check for this mirroring and rotation.

  • fudo

    I have very fast and good algorithm for computer opponent in ‘5 in a row’. I can send you source code for it. But I wrote it long time ago so it’s in AS2.

  • As it turns out there are actually quite a few fewer solutions than this. Like xPy pointed out, mirrored and rotated boards are essentially the same combination not unique ones. There are really only 3 moves you can start with due to symmetry (corner, edge, center) not 9.

    Also, you can arrive at the same combination through a different sequence of moves. 1->2->3 == 3->2->1 (boxes marked 1-9).

    As it turns out, a scalable solution does not necessarily need to enumerate all possible combinations to be optimal. I suggest looking in to the minimax algorithm.

    http://en.wikipedia.org/wiki/Minimax_algorithm

  • impressive algo

  • Donny

    hope you will translate it to as3 version,, :D
    im a newbie in as3

  • Pingback: Daikin VRV-S Ductless split Air conditioning in NYC - - Mini Split Air()

  • Check out my tic tac toe made with pure JavaScript which never loses. NEVER! http://beancoder.com/tictactoe/