## Thursday, 14 January 2010

### Tic Tac Toe.... Looks Like the Number 15...

Playing around with the mathematics of Tic-Tac-Toe with some kids to talk about symmetry and counting... got me thinking..... and searching....

I found the following (slightly edited) interesting history notes at the ADIT sight..

"It may be that the ancient Roman game of Terni Lapilli was an identical game although the evidence is somewhat mixed. It is certainly true that identical grids to the noughts and crosses grid have been found scratched and etched into surfaces all over the ancient Roman empire. However not a single Nought or Cross has been found to confirm the link. It seems probable that Terni Lapilli was played with simple pieces and may have been played with the same rules but in my mind it’s sheer popularity casts doubt upon the connection.

The first software program designed to play Noughts and Crosses (Which is how the English describe T-T-T,... and I recently was told that many Irish folk call the game Boxin' Oxen) was written by A.S. Douglas as part of his PhD dissertation on Human-Computer interaction. The computer was the EDSAC machine built at Cambridge University in 1949. The EDSAC machine was the first true programmable computer as we would understand it today." Here is what the output looked like on the old Edsac..

There are 255,168 possible games of T-T-T, if you label the positions on the board (from 1-9 for instance), but if you allow for symmetry, there are only 138 possible outcomes. If one (or both) of the two players play the game poorly then it may end in a win on the fifth, sixth, seventh, eighth or ninth move....91 wins by the first player (X) and 44 by the second (o)..... and if you are good at arithmetic, then you now know that out of all the games ever played that ended in a draw.... there are only three different final boards. Somehow I think that is incredible. Can you find them all? It is easiest if you just figure out how to place the four " o " so that X can't win...

You can play against an online computer here...
This is a breakdown of all the endings as presented at Wikipedia...
"Ignoring the sequence of Xs and Os, and after eliminating symmetrical outcomes (ie. rotations and/or reflections of other outcomes), there are only 138 unique outcomes. Assuming once again that X makes the first move every time:
91 unique outcomes are won by (X)

* 21 won by (X) after 5 moves

* 58 won by (X) after 7 moves

* 12 won by (X) after 9 moves

* 44 unique outcomes are won by (O)

* 21 won by (O) after 6 moves

* 23 won by (O) after 8 moves

* 3 unique outcomes are drawn"

Now for the 15 part... you can play TTT without the board... Players alternate picking numbers from the integers one to nine inclusive. The first who has picked three numbers that add up to fifteen wins...How is it Tic-Tac-Toe? Well label the TTT board like this....Ohhhh, like MAGIC...