Let's suppose we have some sort of game (for instance tic-tac-toe) with a limited amount of moves. I want to simulate that game, and with that I will use a random number generator (RNG) to calculate the moves.

In the case of tic-tac-toe, there are at most $9!$ moves (if we forget about the games that end before the last move). If I were to run that number of simulations, there is no guarantee that I've ran all possible scenarios due to the inherent randomness of the process. The only way I would have ran all scenarios is if the RNG would magically pop out a straight sequence of moves.

Assuming my reasoning to be correct, I ask if there is some way to determine a threshold or a probability of cases run that would allow me to set a representative number of simulations?

Storing the moves and looking at what was made is not, for this purpose, an option.

  • 2
    $\begingroup$ "Representative" for what purpose? If you want to see every possible game, then this is essentially the coupon collector's problem. If you want to estimate the fraction of games that are wins vs. losses vs. ties, for instance, the number of samples needed is much smaller. $\endgroup$
    – mjqxxxx
    Commented Jan 3, 2014 at 5:33
  • $\begingroup$ $9!=362\, 880$ which is small enough to run through each possibility individually. In fact there are $255\, 168$ possible games, or perhaps $26\, 830$ if you allow for symmetries $\endgroup$
    – Henry
    Commented Jan 3, 2014 at 6:15
  • $\begingroup$ @mjqxxxx I only posted the tic-tac-toe example because most people are aware of it, the real problem that lead to this question is slightly more complex. Nonetheless, that's exactly what I was looking for. Feel free to post it as an answer and I'll accept it. $\endgroup$ Commented Jan 3, 2014 at 21:46

1 Answer 1


It's not so simple as mjqxxxx said, because the way you would presumably use the random numbers is to decide the move at each step, and not to choose an entire game out of the whole set of possibilities. In that case it's not trivial at all. Consider a game whose tree looks like a completely biased binary tree. If each move is randomly selected from among the two possibilities with equal probability, then you will get the same one-move game half the time, and the same two-move game $\frac{1}{4}$ the time, and so on.. It's much harder to cover all the possible games in this case, as compared to a game with a balanced tree.


You must log in to answer this question.

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