The game of tic-tac-toe

[Kent]

Today was terribe, because i had to attend a 8 hour traffic school presentation. The presentation was boring, but i had try to made the most of it by play tic-tac- toe by myself. At some point, i realize that the game of tic- tac - toe could be represented using a Possibility tree. There should be 2^9 ways to play the game. Can any provide a link to such possibility tree? or perhaps somthing similar? Are there ways to optimize your chance of winning?

[Aki]

Shouldn't there be 9! = 362,880 ways to play it?

[Kent]

Shouldn't there be 9! = 362,880 ways to play it?

 

1) Perhaps there are 9! ways to play the game between two player.

 

2) There number of arrengment of O and X in the diagram is 2^9

 

3) The number of possible win of the game perhaps is C( 9, 3) =9!/(3!6!) <---i think this is wrong, but can anyone find the solution ?

 

 

3 much not be it. If one label the space of a tic tac toe game by a, b, c, d, e, f, g,h,i

 

To win a game, you need need 3 letters chosen from the set of {a, b, c, d, e, f, g,h,i}

 

ex: abc, bcd, ahi, cef ...etc

 

 

The thing is that not all 3 letter combinations are possible. the letter on the rim have( not corners) have 2 ways. The corners have 3 ways. the letter at the center have 4 ways. If they are all disjoint, then perhaps i could add those suckers together, but since those letter combine to form a win then it is really not that helpful. :eek:

[Bo]

1) Perhaps there are 9! ways to play the game between two player.

 

2) There number of arrengment of O and X in the diagram is 2^9

 

the problem is more complex then you both propose here :eek:

there are 9! ways if each player in turn puts down a piece, and the game wouldn't stop if a player has three in a row (and the complete board isn't filled yet). on the other hand there are 2^9 ways to fill a complete board with X's and O's, but -apart from the point above; such a situation doesn't always occur when you actually play-, in this way the number of X's and O's doesn't have to be equal.

 

Bo

[pgrmdave]

but you don't take into account that there are only three different places you can put the origional piece. A corner, a middle of a side, and the center - the board is rotatable.

[pgrmdave]

x|_|_

_|_|_

_|_|_

 

is the same as

 

_|_|_

_|_|_

_|_|x

[Thomas]

x|_|_

_|_|_

_|_|_

 

is the same as

 

_|_|_

_|_|_

_|_|x

This is a very interesting point, Considering this, the 3 spaces on top cancel out the bottom 3, one side cancels on side, and the middle space counts as on possibility, which leaves five spaces, so, my logic is:

the number of way to play is 5x4x3x2x1 = 120

[Kent]

delete

[Kent]

x|_|_

_|_|_

_|_|_

 

is the same as

 

_|_|_

_|_|_

_|_|x

 

 

I don t know what you are trying to say. Perhaps you can eloberate a bit?

 

Let us suppost such label:

 

[a][c]

[d][e][f]

[g][h]

 

abc, ghi constitude a win .

 

adg, cfi constitide a win

 

etc.....

 

I think there are 8 ways to win a game abc , def, ghi, adg, beh, cfi, aei, cei

 

What do you propose?

[pgrmdave]

I propose that abc and ghi are the same thing, in effect. that a=c=i=g and b=f=h=d The orientation of the board is unimportant.

[TeleMad]

I propose that abc and ghi are the same thing, ... The orientation of the board is unimportant.

 

I agree ... the orientation of the board is unimportant.

 

Another thing that might throw a monkey wrench into theoretical calculations of the number of possible games is something known in chess as transposition. Consider the following partial games (I can't remember which moves first! I'll assume o does):

 

Partial game #1

 

o | _ | _ |

_ | _ | _ |

_ | _ | _ |

 

o | _ | _ |

_ | x | _ |

_ | _ | _ |

 

o | _ | _ |

o | x | _ |

_ | _ | _ |

 

 

Partial game #2

 

_ | _ | _ |

o | _ | _ |

_ | _ | _ |

 

_ | _ | _ |

o | x | _ |

_ | _ | _ |

 

o | _ | _ |

o | x | _ |

_ | _ | _ |

 

 

By the third position, the game positions are identical...but they were arrived at via two different opening lines of play. Thus, after the first 2 moves, these two openings reduce to just one line of play. How many other opening sequences simply reduce to other base positions?

[zadojla]

Tic-tac-toe is solvable. Perfect play always results in a draw. I've spent some time looking for a web page with the solution to reference without success. However, I discovered the link below, which is to a rather old Scientific American article, which discusses building a computer to play tic-tac-toe out of Tinker Toys.

http://www.rci.rutgers.edu/~cfs/472_html/Intro/TinkertoyComputer/TinkerToy.html

[C1ay]

Tic-tac-toe is solvable. Perfect play always results in a draw. I've spent some time looking for a web page with the solution to reference without success.

 

Perhaps this one and this one cover what you were looking for.

[Aki]

I found this site about the different games that can be played:

http://yallara.cs.rmit.edu.au/~micfoste/Portfolio/TicTacToe.shtml

[Bo]

true the board has rotation symmetry, and also mirror symmetry....

o | x | _ |

_ | _ | _ |

_ | _ | _ |

=

o | _ | _ |

x | _ | _ |

_ | _ | _ |

 

but these symmetries also have an overlap:

 

o | _ | _ |

_ | x | _ |

_ | _ | _ |

=

_ | _ | _ |

_ | x | _ |

_ | _ | o |

Both by 2 rotations and mirror symmetry...

 

even more complications....

 

Bo