You are here:

Probability & Statistics/tic tac toe possibilities

Advertisement


Question
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.

---------- 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

Answer
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:
https://en.wikipedia.org/wiki/Tic-tac-toe#Combinatorics

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.

Probability & Statistics

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

I can answer all questions up to, and including, graduate level mathematics. I do not have expertise in statistics (I can answer questions about the mathematical foundations of statistics). I am very much proficient in probability. I am not inclined to answer questions that appear to be homework, nor questions that are not meaningful or advanced in any way.

Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.

©2016 About.com. All rights reserved.