Kent Posted February 27, 2005 Report Posted February 27, 2005 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 Posted February 27, 2005 Report Posted February 27, 2005 Shouldn't there be 9! = 362,880 ways to play it?
Kent Posted February 27, 2005 Author Report Posted February 27, 2005 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 Posted February 27, 2005 Report Posted February 27, 2005 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 Posted February 27, 2005 Report Posted February 27, 2005 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 Posted February 27, 2005 Report Posted February 27, 2005 x|_|_ _|_|_ _|_|_ is the same as _|_|__|_|__|_|x
Thomas Posted February 27, 2005 Report Posted February 27, 2005 x|_|_ _|_|_ _|_|_ is the same as _|_|__|_|__|_|xThis 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 Posted February 27, 2005 Author Report Posted February 27, 2005 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 Posted February 28, 2005 Report Posted February 28, 2005 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 Posted February 28, 2005 Report Posted February 28, 2005 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 Posted February 28, 2005 Report Posted February 28, 2005 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 Posted February 28, 2005 Report Posted February 28, 2005 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 Posted February 28, 2005 Report Posted February 28, 2005 I found this site about the different games that can be played:http://yallara.cs.rmit.edu.au/~micfoste/Portfolio/TicTacToe.shtml
Bo Posted February 28, 2005 Report Posted February 28, 2005 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
Recommended Posts