5
$\begingroup$

Consider the average game of Tic Tac Toe or Noughts and Crosses. The game is played on a 3 by 3 two dimentional board. The game is played by two people and each person is allowed to only add one type of piece to the board - $\bigcirc$ or $\large\times$, where the person with the crosses always starts first, the players take turns, and whoever puts three pieces in a row (either horizontally,vertically or diagonally) first, wins. The fact that some games finish without filling the entire board is where this gets tricky.

So my questions are:

How many possible games of Tic Tac Toe, which finish at the ninth move, are there? (aka games that fill up the entire board.)

How many possible games of Tic Tac Toe, which finish before the ninth move, are there? (aka games that have at least 3 pieces of one type in a row 'stricked', where there are still empty spaces on the board.)

*Not that here games which are a rotations of other games count as different games.

$\endgroup$

closed as off-topic by David Handelman, Mark Sapir, Ben Barber, Stefan Waldmann, Gabriel C. Drummond-Cole Feb 21 '18 at 23:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – David Handelman, Mark Sapir, Ben Barber, Stefan Waldmann, Gabriel C. Drummond-Cole
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 10
    $\begingroup$ Mandatory xkcd: xkcd.com/832 $\endgroup$ – Per Alexandersson Feb 20 '18 at 19:34
  • 1
    $\begingroup$ As is, the question is a little bit too specific to be of research interest. More interesting questions might be about the asymptotics for the number of games of length $n^2$ on an $n\times n$ board as $n\rightarrow\infty$ or for $d$-dimensional analogues, etc. May I suggest you edit your question in this direction? $\endgroup$ – j.c. Feb 20 '18 at 21:47
  • $\begingroup$ See e.g. the variations described here weijima.com/… $\endgroup$ – j.c. Feb 20 '18 at 21:56
  • $\begingroup$ By "games" do you mean "final board configurations" or do you mean "sequences of moves"? I would think of two entirely different sequences of moves that end up with the same board configuration are not the same game. $\endgroup$ – Eric Lippert Feb 20 '18 at 22:58
  • 1
    $\begingroup$ The clue that this is an easy question is that there are at most $9! = 362880$ games, which is an insignificant number of cases to inspect on a modern computer. If it's not clear how to check all these cases then working out the details is a useful exercise in programming. $\endgroup$ – Ben Barber Feb 21 '18 at 9:42
12
$\begingroup$

There is a fairy detailed computation on this page of Henry Bottomley's. There seem to be 81792 games ending in a win +46080 games ending in a draw = 127872 games ending on the 9th move (out of 255168 games possible).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.