7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ See here and here. Might be helpful for discussion. \$\endgroup\$ – Alex A. May 30 '15 at 22:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Alex A. May 30 '15 at 22:16
  • \$\begingroup\$ Maybe based on time - Make the overall test procedure take a few minutes. \$\endgroup\$ – isaacg May 31 '15 at 6:26
  • \$\begingroup\$ 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. \$\endgroup\$ – Nathan Merrill May 31 '15 at 13:06
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

Adaptive Sampling

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).

Start with a reasonably large N

Note that starting with N (the initial number of games) too small will give a high probability of early termination with inaccurate results. For example, starting with N=1, there may be a significant probability of the 2 runs of 1 game having the same outcome, even if that outcome is not the same as the long term average. Starting with a larger N makes it much less likely that both runs will match and be inaccurate.

\$\endgroup\$
  • \$\begingroup\$ For the latest Prisoner's Dilemma this answer probably wouldn't work. The results haven't been recalculated since I added the Perfect Gentleman (PG), but I can tell you that having run the game about 400000 times, they're all slightly different, as the PG dominates so completely (95% of all runs end with PG as the only survivor) that determining 4th place and beyond accurately is virtually impossible. The remaining 5% of games are the ones where all initial copies of PG are matched against one of the (low general fitness) defector types. \$\endgroup\$ – Draco18s Jun 22 '17 at 15:24
  • \$\begingroup\$ I'd love to see a better approach (perhaps from someone who has an in depth knowledge of probability and statistics), but for now I'm resigned to not being able to determine an exact ordering for the leaderboard. For upcoming KotHs I'm likely to settle for something that makes 1st place unambiguous, and just accept that lower places will be only estimates. \$\endgroup\$ – trichoplax Jun 22 '17 at 22:07
  • \$\begingroup\$ I'm unsure that there is a "best" approach, I think it entirely depends on what's being randomized. But in the case of that KoTH, sure. 2nd and beyond are likely only going to be approximate. \$\endgroup\$ – Draco18s Jun 22 '17 at 23:21
1
\$\begingroup\$

If the space of randomness is relatively small, just run for all possibilities and average the score

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.

\$\endgroup\$

You must log in to answer this question.

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