Tic Tac Toe: What is the probability that a random player draws against an infallible player?

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?

• 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. – Peter May 22 '16 at 12:24
• Just a question : If the position is theoretically draw, does the infallible player make a random non-losing move ? – Peter May 22 '16 at 12:26
• The infallible player always makes the move with highest gain and it always makes the first move – Alan Russel May 22 '16 at 12:31
• 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. – Peter May 22 '16 at 12:32
• 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}$. – 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.