Talking about Tic Tac Toe game, Game development and Php.
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?
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.