# How many games are possible in Tictactoe?

This topic is 2408 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

##### Share on other sites

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

Perhaps it's 18. Or 1*2*3*4*5*6*7*8*9*2?

Remember, there are 2 players.

##### Share on other sites
This is kind of vague to me.

Is:

 XXX OO. ... 

supposed to be a different outcome than:

 XXX O.O ... 

##### Share on other sites
If I remember correctly there are 8 different outcomes for each player in a winning game.

one for each row so that is 3 different possibilities. One for each column which is another 3 possibilities. Finally one for each diagonal which is 2 more possibilities.

So that gives us (3 + 3 + 2) * 2 = 16 different winning outcomes in tic tac toe. Not sure if the question asked for losing outcomes as well.

##### Share on other sites
What an open-ended question. Is a "game" defined by where a player places his pieces, in what order? You may win by getting 3 diagonal, but is it a different "game" if you play the middle place as your 1st, 2nd, or 3rd move? I would say yes. Which would get the number of games into a very high count.

##### Share on other sites

this was a question in an exam I just did

my answer was 9! but I was told it was wrong

really?

yes, 9! is the number of ways you can fill the board in completely(assuming that order matters), games can end before the board is completely filled

##### Share on other sites
Also the board is symmetric along 4 axii: horizontal, vertical, and 2 diagonals. So you can pick one, flip/mirror the board across it, and thus show half the possible sequences of moves to be duplicates of the other half.

##### Share on other sites
sounds like a challenging problem..

I think "game" is probably defined as "a sequence of moves that terminates in one player winning or a draw"

You'd have to start with 9! and then subtract all the games that are impossible. Specifically, any game where there are moves after a player has reached 3 in a row is impossible.

So.. in the whole game there are 9 moves. We don't have to worry about a winner until move number 5 (when X might win). How many different ways can we have a winner in 5 moves? There are 8 different ways to win, and order is important, there are 6 different ways to order 3 moves. Also, O is also playing- there are 6 remaining spots on the board (after you subtract the 3 that X uses to win), so there's 6*5 ways that O could play before losing. So that's 8*6*6*5, or 1440 games that end at move #5.

With that number you can figure out how much the 9! total has overcounted. After a victory in 5 moves, there's 4! ways to keep playing. So the 9! number has overcounted by 1440*4! = 34560. So the final answer would be 9! minus 34560. But let's not forget the 1440 valid games that ended after 5 moves, so add 1440 back in.

I think you would have to continue and find numbers of games that are impossible because of victories after move #6, #7 and #8. It gets complicated quickly. What class is this for?

##### Share on other sites
I count 255,168 games, without considering any symmetries.

#include <iostream> unsigned const magic[9] = { 010010010, 010001000, 010000101, 001010000, 001001011, 001000100, 000110001, 000101000, 000100110 }; int count(unsigned p[2], int to_play, unsigned unused) { if (p[!to_play] & 044444444) return 1; // Last move was a win if (p[0]+p[1] == 055555555) return 1; // Full board int result = 0; for (int i=0; i<9; ++i) { if (unused & (1u<<i)) { p[to_play] += magic; result += count(p, !to_play, unused^(1u<<i)); p[to_play] -= magic; } } return result; } int main() { unsigned p[2] = {011111111, 011111111}; std::cout << count(p, 0, 0777) << '\n'; } 

##### Share on other sites
Hidden
How does this dark magic work?

##### Link to post

I count 255,168 games, without considering any symmetries.

#include <iostream> unsigned const magic[9] = { 010010010, 010001000, 010000101, 001010000, 001001011, 001000100, 000110001, 000101000, 000100110 }; int count(unsigned p[2], int to_play, unsigned unused) { if (p[!to_play] & 044444444) return 1; // Last move was a win if (p[0]+p[1] == 055555555) return 1; // Full board int result = 0; for (int i=0; i<9; ++i) { if (unused & (1u<<i)) { p[to_play] += magic; result += count(p, !to_play, unused^(1u<<i)); p[to_play] -= magic; } } return result; } int main() { unsigned p[2] = {011111111, 011111111}; std::cout << count(p, 0, 0777) << '\n'; } 

How does this dark evil work?? I must know.

##### Share on other sites
With symmetries it's 26,830 or 31,896 depending on how you measure it.

If you assume the players aren't making moves completely at random and only consider games where players will make three in a row whenever they can, and otherwise will choose to block whenever possible then you're down to 1,145 different ways to play the game.

P.S. The main thing that confused me about how that code above worked, was that because of the leading zero those constants are in octal not decimal: 0777 == 511. Once you realize that, and that the magic numbers are set up to handle the 8 possible rows + columns + diagonals you can win along, it's not too hard to read.

##### Share on other sites

How does this dark evil work?? I must know.

The main trick is that I use numbers in octal (octal constants start with a "0" in C and C++, which is something that not everybody knows) so I have one 3-bit counter for each 3-in-a-line configuration. The magic' array tells you which configurations each square participates in. Then I simply keep the sum of the magic numbers for each side, so when a counter reaches 3 it means that that player won and the game is over. As an extra twist, I initialize all the counters to 1 instead of 0, because it's easier to test if any counter reached 4 instead of 3 (a single bitwise-and operation does the trick).

I also keep track of which squares are still available as moves as bits in unused'. I could check if the board is full by checking `unused==0', but I wrote the condition before I had decided how to encode the available squares, and I thought checking that the sum of both players's magic numbers is 055555555 is kind of cute, so I left it there.

The rest is simple depth-first search using backtracking, which is the natural algorithm for this task.

Did I leave anything out?