EvilNando 96 Report post Posted July 15, 2011 this was a question in an exam I just did my answer was 9! but I was told it was wrong really? 0 Share this post Link to post Share on other sites
dantheman1337 103 Report post Posted July 15, 2011 [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. 0 Share this post Link to post Share on other sites
BradBobak_68669 137 Report post Posted July 15, 2011 This is kind of vague to me. Is: [code] XXX OO. ... [/code] supposed to be a different outcome than: [code] XXX O.O ... [/code] 0 Share this post Link to post Share on other sites
blewisjr 752 Report post Posted July 15, 2011 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. 0 Share this post Link to post Share on other sites
BeerNutts 4401 Report post Posted July 15, 2011 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. 0 Share this post Link to post Share on other sites
SimonForsman 7642 Report post Posted July 15, 2011 [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 0 Share this post Link to post Share on other sites
EqualityAssignment 230 Report post Posted July 15, 2011 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. 0 Share this post Link to post Share on other sites
pinacolada 834 Report post Posted July 15, 2011 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? 0 Share this post Link to post Share on other sites
alvaro 21272 Report post Posted July 16, 2011 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] 0 Share this post Link to post Share on other sites
KanonBaum 277 Report post Posted July 16, 2011 · Hidden Hidden How does this dark magic work? 0 Share this post Link to post
KanonBaum 277 Report post Posted July 16, 2011 [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. 0 Share this post Link to post Share on other sites
Adam_42 3630 Report post Posted July 17, 2011 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. 0 Share this post Link to post Share on other sites
alvaro 21272 Report post Posted July 17, 2011 [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? 0 Share this post Link to post Share on other sites