Probability & Statistics/tic tac toe possibilities
QUESTION: Assuming random placements, how many possible variations of a tic-tac-toe game are there? My first thought was simply 9! or 362,880. But then I realized that if X wins after 5 moves, then the last 4 squares wouldn't have to be filled. Similarly, if X wins after 7 movies, or O wins after 6 or 8 moves, the rest of the squares don't have to be filled.
I know the answer would be as easy as taking the number of times that would happen and subtracting it from 9!, but I can't figure out a mathematical way to determine the number of possible ways the game could be won in 5, 6, 7 or 8 moves. I can't determine if it is a simple Combination or something more complicated.
ANSWER: This is a "simple" combination in the sense that you can answer this problem without doing a serious amount of mathematics beyond permutations and combinations. It just requires very careful book-keeping, so to speak.
Your methodology doesn't take into account the position of the moves. There are, indeed, nine moves total in a game that fills up the board, but when you talk about a game that ends without filling up the board (someone wins in fewer than nine moves), the position of the winning moves limits your choices.
It may be easier to consider where the Xs and Os are, then to consider the order in which they were placed. For example, if there is some tie game (with 5 Xs and 4 Os), then
For example, if the game is won in only five moves, then there are only eight possible ways that X could have moved (since his three X's must be in a row, column, or diagonal). The two Os could have moved in 15 possible ways among the six remaining squares. But the order matters too. The Xs could be in any order (3!) and the Os as well (2!). The total number of the ways of doing this would be:
3! 2! 8 × 15 = 1440
You should be careful, because you have to analyze the following cases:
Win after 5 moves (as above, 1440).
Win after 6 moves.
Win after 7 moves.
Win after 8 moves.
Win after 9 moves.
No win after 9 moves.
If you have a win after 9 moves, this may require a certain move to be the last move. The winning move could not happen prior to those moves. The same care should be taken in other cases as well, that the winning move must be last.
I will not work out all the cases, as I believe guidelines like this are what you are asking for.
[an error occurred while processing this directive]---------- FOLLOW-UP ----------
QUESTION: After asking the original question, I started thinking about basic strategy. Just the basics of always winning if there is winning move available and always blocking if your opponent has a winning move available.
My first thought would be that it would make the number of possible games smaller since it would limit moves fairly often. But then I realized that it would also extend the average game length considerably. In fact, using basic block strategy, it is impossible for a game to end in 5 or 6 moves.
I guess my followup question is, Can this be determined mathematically without getting too involved? And would it increase or decrease the number of possible different games?
PS...IF you are wondering, this question came about after watching the 80s movie WarGames where at the end, David, the main character, has "Joshua" the supercomputer that handles the missile launching, play tic-tac-toe over and over again to learn that it is a pointless game and always ends in a tie, so that he can apply that same learning strategy to nuclear war. I started thinking that the games were being played so quickly that the computer should have been able to have tried every single variation, let alone using basic strategy to always end up in ties, which it must have been doing since the whole plan required it to never have a winner or else it would have launched the nuclear missiles
Mathematically, questions like "how many possible games of tic-tac-toe are there?" are not very appealing, and do become tedious (as you say, "too involved"). Not to mention, mathematically we would eliminate redundancies (if the first move is in a corner, should it matter which corner?). But yes, it certainly can be done -- with some of the tedium reduced by various mathematical methods (or just hashing things out by computer). The answer, in many different phrasings of the question, is available on Wikipedia:
The "real" answer at the bottom of this is that tic-tac-toe is a game with the following properties:
1. It is strong positional game. This is a game where each player claims certain positions with the goal of being the first to claim an entire winning configuration (a row, column, or diagonal in this case).
2. It is symmetric. The winning configurations are the same for X or O.
3. It is a game of perfect information. No moves are hidden or secret.
For these reasons, the winner of the game is -- if not a draw -- player 1. If player 1 executes a sufficiently good strategy, he or she will always win.
But tic-tac-toe in particular can be shown to have no winning strategy. If both players play as well as possible, the game will always result in a draw. For tic-tac-toe, when we discuss strategy, optimal play, etc. the whole game really boils down to a big draw -- nobody can really win at tic-tac-toe.