Ok, I was wondering if anyone knows what you do to solve a game such as tic tac toe using mathematical as opposed to experimental methods. Thanks

-- Student Phil M-F (lepernthern@hotmail.com), October 22, 2000

Answers

Hi Phil,

I've been working on this problem from an amusement point of view, but I do have a degree in mathematics (which helps).

I started by wanting to know how many games of tic tac toe were possible.

Once a longtime ago I wrote a pascal program which would play the game and never lose. i put strategies in the program to 1) Go for a win next move 2) Prevent a opponet win in the next move 3) Make next move to allow a win on the next move (assuming it isn't blocked by the opponent) 4) go for the centre 5) make any move possible.

This program worked well and never lost.

I have been thinking about analysing tic tac tao more mathematically.

You first have to realise that there are three move games, four move games and five move games. Then start to analyse then in that sequence. Computing the three move games is easy. Once you work out a sequence you can use rotation etc to fill in the other identical sequences as the board is baically symetrical. The other games are a little harder.

I think I've got the strategy for how to do it I'll let you know if you are still interested.

-- David Brisbane (davidbrisbane@yahoo.com), August 25, 2001.

Well, as you can see I haven't been working on the Tic Tac Toe problem for a while. I guess you are no longer interested in it, but maybe the next calss will be.

I am near the end of my analysis (for fun) of how many games are possible.

Firstly it turns out that there are only 16 games that result when good players play and these are the draws!

Also there are 21 double win games (i.e. X on the fifth move win on two different lines or diagonals at the same time).

So far I've discovered that there are 120 "X" wins on the 3rd move games and 148 "O" wins on the third move games. There are 444 "X" wins on the 4th move games and "168" O wins on the 4th move games.

I'm still auditing the results and working on X wins on the 5th move games (not many of these, around 40 games I think).

David Brisbane

-- david brisbane (davidbrisbane@yahoo.com), April 24, 2002.

I finished my analysis on "X" wins on the 5th move, or there is a draw on "X's" 5th move. It turns out that "X" wins on 5th move has 40 "single" wins and 22 "double" wins. There are 16 draws possible on the 5th move.

A "double" win is when by placing the "X" in a box on the last move (i.e. 9th move in the game, and "X's" 5th move), "X" wins in two different ways (e.g. vertically on the left side plus diagonally from the top left the the bottom right). A "single" win game is like all the other win games (i.e. win by getting only three "Xs" or three "Os" in a row, column or diagonal).

If you do the maths using the new numbers above plus the numbers I supplied in my last email, you arrive at a total of 958 possible different games, of which only 16 are ever likely to be played (i.e. the draws).

There are three easy to imagine ways I can think of to get this answer. The first is to write a computer program which systematically placed all possible games, discarding duplicates and counting only the unique games. Well, if you are a school kid, this might be too difficult for you.

The second way is to calculate the number of game wins for "X" or "O" on their 3rd and 4th moves respectively then the "X" wins or draws on the last move using factorial combinations.

E.g "X" wins on the 3rd move can be calculated as follows. There are eight possible ways for "X" to win on its 3rd move, i.e. three in a row on the two diagonals, on the three rows and on the three columns.

Noting that if "X" really did win on the third move this leaves 6 boxes into which 2 "Os" had to be placed. So the question becomes how many ways can I place 2 "Os" into 6 boxes? Well there are 6 possible boxes for the first "O" and for each of these placements there are 5 remaining boxes into which the second "O" can be placed. Hence for each "X" three in a row win there are 6 * 5 possible ways, but you will notice if you try to fit the "Os" in by hand you will notice that when you genrate all the possible ways half the way are duplicates of the other half, hence rather than there being 30 ways to fit two "Os" into 6 boxes there is really only half as many, namely 15 ways.

So 8 different ways for "X" to win on its third move and 15 different ways to place 2 "Os" in the remaining 6 squares results in 8 * (6 * 5)/2 games = 120 games for "X" wins on its 3rd move.

Obviously you have to compute the winning number of games for "X" wins on its 4th and 5th move, plus "O" wins on its 3rd and 4th move, plus the number of draws and then add 120(i.e. "X" wins in three moves)to this total to get the final answer of 958 games. Note that you will need to be watching for dupliccate games and impossible games (e.g "O" didn't win on its 3rd move as "X" won on its 3rd move etc) all the time as well during the generation and counting process.

Well, if you are a bright student you might manage to do this for all win and draw situations. Even if you aren't that bright, you'll still manage to do it for say "O" wins in three moves.

Another ways is to actually systematically generate the games by hand, which is what I did, plus use the calculation method described above to check the answer.

Systematic generation is the method I first used to get the answer. It has the advantage of allowing you to "See" all the games and their duplicates, so you can convince yourself that the answer is correct.

Systematically generating the games is a fun way of arriving at the answer but a little hard to describe in this note. First you need to know something about the symmetry of the games (i.e. five reflective and three rotational symmetries) so that you can eliminate the duplicate games via as a result of finding duplicate "Root game types" before you generate and count all the duplicate games. This cuts down the manual work quite considerable.

An example of a "Root game type" is all possible games is a win for "X" with XXX on the top row, which we discovered accounts for 15 of the 120 wins on "X's" 3rd move.

This particular "Root game type" generates 9 possible unique games (without considering symmetry) of "X" wins on the three move with XXX on the top row - try to discover the unique games for yourself - hence there could be 9 * 8 (when symmetry is considered) possible unique games.

Now using symmetry (e.g all eight and remove duplicate - there are four duplicates) leaves the XXX on the top row, XXX on the left colum, XXX on the bottom row and XXX on the right column as the unique games, hence allows us to directly generate an 60 games, bring the total number of unique games for XXX on the top row, bottom row, left side column and right side column to 60 unique games, not 72 as there 12 duplicate games discarded from the 72 possible games.

As you can see, this would be difficult for someone at high school to do, but you might want to try it for the "X" wins in three moves "Root game type" described above.

To help you I'll tell you that there are 3 "Root game types" for "X" wins on its third move as follows (1) XXX on the top row; (2) XXX on the top left to bottom right diagonal and; (3) XXX on the middle row.

These "Root games types" are independent of each other as no amount of relection or rotation of games of one type (e.g. XXX on the top row" will generate the game of another type (e.g. XXX on the top left to bottom right diagonal).

I hope this helps someone have fun with mathematics and Tic Tac Toe. I know I had fun :-)

David Brisbane 27/4/2002

-- David Brisbane (davidbrisbane@yahoo.com), April 27, 2002.