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.

Improve this question
$\endgroup$
7
  • 10
    $\begingroup$ Mandatory xkcd: xkcd.com/832 $\endgroup$
    – Per Alexandersson
    Commented Feb 20, 2018 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.
    Commented Feb 20, 2018 at 21:47
  • $\begingroup$ See e.g. the variations described here weijima.com/… $\endgroup$
    – j.c.
    Commented Feb 20, 2018 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
    Commented Feb 20, 2018 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
    Commented Feb 21, 2018 at 9:42

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .