# How should authors choose the proper sample sizes for probabilistic programming competitions?

Several programming competitions include randomness as part of the scoring. This randomness can come either from the controller/tester program (like Lab Rat Race) or from other competitors (examples include most KOTHs). As a result of this randomness, the competitor rankings can vary from tournament to tournament. When it comes to determining the winner, it is important that the leaderboard be accurate so that the correct answer is accepted.

What are some guidelines for picking the sample size of a competition? I am interested in answers that can serve as guidelines to challenge hosts and which cover the following topics:

• For challenges in which all contestants play together, how should we determine how many games should be in a tournament?
• For challenges in which each contestant is scored separately (like Lab Rat Race), how many trials should each contestant perform?
• For challenges in which a single game involves a pair (or more) of contestants, how many times should each pairup be played?
• For challenges in which each game is iterated (iterated prisoner's dilemma or RPS), how many iterations should be in each game?

My motivation for asking this question is that I've noticed a very wide range in sample sizes, and I felt that some of the smaller ones probably weren't actually enough to determine the true winner. Listed below is some of the variety.

• See here and here. Might be helpful for discussion. – Alex A. May 30 '15 at 22:14
• There probably isn't a good "right" answer to this because the number of trials necessary is pretty specific to the metric you're using to select a winner. I'd say do as many trials as computationally feasible, but fewer than an annoying amount. – Alex A. May 30 '15 at 22:16
• Maybe based on time - Make the overall test procedure take a few minutes. – isaacg May 31 '15 at 6:26
• What should be happening is that we take tests until, statistically speaking, there is little to no variance. However, the time and math it takes to do prove that small variance isn't fun. – Nathan Merrill May 31 '15 at 13:06

# Run trials until you run out of time

To some extent, it doesn't matter if there is a chance that you've picked the wrong winner, just whether or not anybody is going to be able to prove you're wrong.

If your competition is based on a large group game (everyone playing at once) then program your controller to run, say, eight-hours-worth of games, let it run overnight, and call it good enough.

## Pros

• By definition, the tournament always runs in a feasible amount of time.
• To show that the results are incorrect and that the true winner is a different candidate, someone would have to run a second tournament for an even longer, unfeasible amount of time.

## Cons

• You have to be able to let it run for many hours.

Ideally an approach would be specified in the question that can be applied regardless of the number of answers or the strategies used. This would describe what will be done and how it will be determined whether a given sample size is sufficient. This should allow the sample size to be varied based on the results, rather than trying to infer an ideal size from the number and type of answers.

If a perfect result cannot be obtained, this can be acknowledged by showing joint nth place rather than a potentially incorrect leaderboard order.

## Example approach (for all against all games)

For an all against all game, run N games and record the result. Run another N games and compare the result with the first. If they differ, run another 2N games and compare the result with the first 2N. Continue doubling until the results match.

Using this approach to obtain a strictly ordered leaderboard (no joint nth place) is likely to require a very large number of games, especially if there are a large number of players and where there are two or more similarly matched players. To keep the required number of games manageable, the strictness can be compromised in some way.

If only the winner is important, then the process can simply be repeated until 1st place is consistent, and any differences below that can be converted into joint places. Alternatively the process can be continued until any joint places only include 2 players (so there are not 3 or more players joint nth place).

As the time required will increase as new answers come in, the question poster may choose a hybrid approach, where there is a maximum number of games. This way early leaderboards will be strictly ordered, and later leaderboards will have an upper limit on the time required, but may have joint places.

### A faster equivalent

With the approach described, doubling the number of games each time the first half doesn't match the second half, the worst case is that 2M+1 games are required for an accurate ordering, in which case this approach will require 2M+1 games. If instead only 2 extra games are played each time, then the worst case will require 2M+2 games (roughly half as many) and be equivalent in the best case.

So the approach is to play 2N games, and if the first N do not match the last N, play an additional 2 games. Now if the first N+1 do not match the last N+1, repeat as required. The process can be terminated early with joint places as before.

## Example approach (for pairwise games)

If players are paired up and compete against each other one on one, then N games can be run for each possible pairing, and then compared with another N games each. Only those that do not match need to be repeated, so that the majority of samples will be of closely matched pairs and further time need not be wasted on pairs where there is a clear winner.

Again, after a time limit is reached joint places can be accepted (or joint places can be accepted below 1st place, with more time being allowed if 1st place is still ambiguous).

This won't apply for every KOTH, as some use very large amounts of randomness. For some, though, it's clearly the fairest method for scoring. For example, this KOTH ran in parallel with another one offsite (I was participating in the other one at the time). I remember thinking that the one on PPCG was fairly primitive because it didn't simply run all 42 possibilities (21 lengths, then again swapping the - and + in one program), like other hills for that challenge do.