2
\$\begingroup\$

I'm building a game in which there are tournaments. During the tournaments we want players to play against each other in an efficient way.

What I'm looking for is a generic algorithm that will match players together in an optimal way in order to:

  • Have the lowest amount of games possible
  • Be reasonably sure that after all games are played, the highest-ranked player is the best

Tricky part:

  • Games can have 2, 3 or 4 players in a death match depending on the tournament.
  • Tournaments have two or more players, no other constraints.

Does such an algorithm exist?

Note: For the ranking, I will probably be using an ELO-based algorithm (unless you have a better suggestion).

\$\endgroup\$
  • \$\begingroup\$ Your question title seems to imply you already have the round robin algorithm in mind. The question body says otherwise. \$\endgroup\$ – Sean Middleditch Aug 31 '13 at 3:25
  • \$\begingroup\$ Well I'm thinking I want a sort of round robin, just not the complete set of games \$\endgroup\$ – gmalette Aug 31 '13 at 3:54
2
\$\begingroup\$

The Swiss Movement is a well-known tournament algorithm used in Chess, Bridge and Go tournaments (at least). It works similar to an elimination, except no-one gets eliminated; in each round, players/teams with an equal win-loss record are matched up subject to the constraint of not having played each other previously in this tournament. Clearly for a good result one wishes to have:
number of rounds > log2 (number-of-entrants);
however, having one greater number of rounds than required by this formula can at times give even better differentiation. For some types of games it is possible to enhance the scheduling even more by having a mild victory-point scale rather than pure win-loss for each match.

The mechanics of matching entrants at each round involve first sorting by win-loss record (or VP's if applicable), and then working from both ends to the middle. In case of a severe conflict near the end of the event (ie teams having to replay each other), Bridge tournaments have a policy of forcing this replay as far down the standings as possible, without creating another such conflict.

Also, to maintain interest at the low end, it is common in larger Bridge tournaments to take the bottom half of the entrants at the half-way point and start a second (new) event. (Better players have been know to term this The Swamp.)

In world-championship Bridge tournaments, a complex combination of qualifying Swiss, followed by double-elimination knock-out with repechage is used. I admit to never having explored the intricacies of this, but a search of relevant regulations for Bridge Olympiads (in particular) should provide details for this mechanism.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.