Sign in to follow this  
EvilNando

How many games are possible in Tictactoe?

Recommended Posts

dantheman1337    103
[quote name='EvilNando' timestamp='1310754533' post='4835751']
this was a question in an exam I just did

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

really?
[/quote]


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

Remember, there are 2 players.

Share this post


Link to post
Share on other sites
blewisjr    752
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 this post


Link to post
Share on other sites
BeerNutts    4400
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 this post


Link to post
Share on other sites
SimonForsman    7642
[quote name='EvilNando' timestamp='1310754533' post='4835751']
this was a question in an exam I just did

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

really?
[/quote]

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


Link to post
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 this post


Link to post
Share on other sites
pinacolada    834
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 this post


Link to post
Share on other sites
alvaro    21247
I count 255,168 games, without considering any symmetries.

[code]#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[i];
result += count(p, !to_play, unused^(1u<<i));
p[to_play] -= magic[i];
}
}
return result;
}

int main() {
unsigned p[2] = {011111111, 011111111};
std::cout << count(p, 0, 0777) << '\n';
}

[/code]

Share this post


Link to post
Share on other sites
KanonBaum    277
[quote name='alvaro' timestamp='1310783673' post='4835877']
I count 255,168 games, without considering any symmetries.

[code]#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[i];
result += count(p, !to_play, unused^(1u<<i));
p[to_play] -= magic[i];
}
}
return result;
}

int main() {
unsigned p[2] = {011111111, 011111111};
std::cout << count(p, 0, 0777) << '\n';
}

[/code]
[/quote]

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

Share this post


Link to post
Share on other sites
Adam_42    3629
With symmetries it's [url="http://www.btinternet.com/~se16/hgb/tictactoe.htm"]26,830 or 31,896 depending on how you measure it[/url].

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


Link to post
Share on other sites
alvaro    21247
[quote name='KanonBaum' timestamp='1310858637' post='4836182']
How does this dark evil work?? I must know.
[/quote]

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?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this