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?
Best Answer
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.