How many combinations are possible in the game tic-tac-toe (Noughts and crosses)?
So for example a game which looked like: (with positions 1-9)
A1 -- B1
A2 -- B2
A3 -- --
[1][3][4][6][7] would be one combination
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ se16.info/hgb/tictactoe.htm $\endgroup$– DarylJan 2, 2013 at 10:00
-
$\begingroup$ @Daryl, if you feel up to it, you should repackage that as an answer citing that website so this question can have an answer. $\endgroup$– Mark S.Nov 22, 2013 at 3:42
-
$\begingroup$ @MarkS. Sure thing. $\endgroup$– DarylNov 22, 2013 at 5:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
This information is taken from this website.
A naive estimate would be $9!=362\,880$, since there are $9$ possible first moves, $8$ for the second move, etc. This does not take into account games which finish in less than $9$ moves.
- Ending on the $5^\text{th}$ move: $1\,440$ possibilities
- Ending on the $6^\text{th}$ move: $5\,328$ possibilities
- Ending on the $7^\text{th}$ move: $47\,952$ possibilities
- Ending on the $8^\text{th}$ move: $72\,576$ possibilities
- Ending on the $9^\text{th}$ move: $127\,872$ possibilities
This gives a total of $255168$ possible games. This calculation doesn't take into account symmetry in the game.
-
$\begingroup$ Accounting for symmetry, this can quickly be reduced by a factor of 6, as there are only 12 possible two move openings, not 8*9=72. $\endgroup$ Nov 22, 2013 at 5:32
-
$\begingroup$ As that linked page makes clear at the bottom, symmetry allows a reduction by a factor of $8$ (i.e. rotations and reflections of a square) to $31896$, but arguably by a greater amount to $26830$. $\endgroup$– HenryJan 2, 2015 at 11:18
-
$\begingroup$ I am assuming I am asking a naive question here, but why isn't the answer $9! - \sum\limits_{i=5}^{8} m_i = 235584$, where, $m_i$ are the number of games ending on $i$ moves (the numbers above). (From the overestimation of the games that take all 9 moves we subtract the ones that require less) $\endgroup$ Dec 3, 2017 at 23:47
$\begingroup$
$\endgroup$
2
I will say that the board combinations are 3^9, which is 19683 possibilities, and 2032 winning positions. The answer of 9! is related to how many ways we have to fell all the positions, rather than the possible combinations.
I have answered this question already in another post, please see the next link: https://stackoverflow.com/a/54035004/5117217
Cheers!
-
$\begingroup$ yes but this number is much smaller than they mentioned, i can't figure out why $\endgroup$ Apr 11, 2021 at 12:06
-
$\begingroup$ the actual number might be smaller than this. your number 3^9 includes the board state where all the 9 positions are O's- which is not a realistic state $\endgroup$ Apr 24, 2021 at 19:18