I have simulated a tournament between an infallible Tic Tac Toe player and one that chooses its moves randomly.

Even after 5 million games, the infallible player wins every single game. I know that if both players play infallible, a Tic Tac Toe game always ends in a draw. I could not find a bug in my program and I am missing the foundations in probability theory to calculate whether it is probable that even after 5 million games no draw occurs.

Is there a way to calculate and prove it?

  • 4
    $\begingroup$ I am pretty convinced that the program must contain some error. The number of choices, the random player has, is bounded from above by $8\cdot 6\cdot 4\cdot 2$ or $9\cdot 7\cdot 5\cdot3$ depending who moves first. So, the probability cannot be that low. $\endgroup$ – Peter May 22 '16 at 12:24
  • $\begingroup$ Just a question : If the position is theoretically draw, does the infallible player make a random non-losing move ? $\endgroup$ – Peter May 22 '16 at 12:26
  • $\begingroup$ The infallible player always makes the move with highest gain and it always makes the first move $\endgroup$ – Alan Russel May 22 '16 at 12:31
  • $\begingroup$ This means : It makes a move, such that the opponent has as few drawing moves as possible ? Or something else ? If we want to determine the draw-probability we have to exactly know what player $1$ does. $\endgroup$ – Peter May 22 '16 at 12:32
  • $\begingroup$ I guess : The infallible player always starts with the middle. Then, the probability that the random player makes the right choice at the beginning is $\frac{1}{2}$. $\endgroup$ – Peter May 22 '16 at 12:37

The second player has 8 choices for his first move, 6, for the second, etc., so in any game he has a total of $8 \times 6 \times 4 \times 2 = 384$ possible sequences of moves. If only one choice is correct at each point, which is an underestimation, then in 5 million games he would be expected to draw at least $\lambda = 5 \times 10^6 / 384 \approx 1.3 \times 10^4$ games. Using a Poisson approximation, the probability that he will actually draw zero games is then $e^{- \lambda} \approx 1.3 \times 10^{-5655}$. This isn't likely.

We could make a more refined estimate-- for example, it may be that the inferior player actually has two drawing choices at his second move instead of one-- but this would only serve to increase his expected number of draws and decrease the final probability of zero draws.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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