this was a question in an exam I just did
my answer was 9! but I was told it was wrong
really?
How many games are possible in Tictactoe?
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.
This is kind of vague to me.
Is:
supposed to be a different outcome than:
Is:
XXX
OO.
...
supposed to be a different outcome than:
XXX
O.O
...
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.
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.
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.
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
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.
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?
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?
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';
}
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement