Can whist algorithm or similar be used here?

[nlkolbe]

Hi

I am currently programming a small web application to use in my spare time for planning matches for a foosball / table soccer tournament, but is currently pretty stuck in deciding/programming the main algorithm to use after having used 10-15 hours trying different approaches.

I'm therefore very glad to have found this page/community and hope that you might be able to help me with some sparring about the challenges described below (I have used a couple of hours reading in the forums and on https://www.devenezia.com/downloads/round-robin/index.html and related pages, but haven't found exactly what I'm looking for so far).

The requirements for the tournament are as follows:
- The tournament is played on either 1 or 2 foosball tables (Meaning that each round will consist of either 1 or 2 simultaneously played matches)

- N players will participate in the tournament (if 1 table is used at least 4 players will participate, while at least 8 players will participate if 2 tables are used. However, the numbers 4/8 are just the minimum numbers, but in real-life e.g. 4-11 players could be part of the "1 table" variant, while e.g. 8-19 players could be relevant for the "2 table" variant). This means that I can't enforce that a multipla of 4 or 8 players participates, but my algorithm should handle all numbers of players from 4 and up to about 20 on both 1 and 2 tables)

- During the tournament each player will a number of matches, which will be between 1 to "N - 1", each with a different partner as a team against two other players in another team. The same two players can only be on the same team once during the tournament, but it is NOT important how many times a player meet a specific other player as an opponent on the other team, but it will of course be great to have these "evened out" as much as possible).

- All players will play the same number of matches (The number of matches that each players gets to play depends on how much time there is available for the tournament).

- If the number of players and number of played matches per player means that the last matches e.g. "lacks" opponents, these matches should just be equipped with dummy players (A simple, but unrealistic example: If we have a tournament with 5 players on 1 table, where each player should play just 1 match, the rounds/matches could be as following: Round 1/Match 1: A+B vs. C+D. Round 2/Match 2: E + dummy vs. dummy + dummy). In reality the "dummy players" would be selected randomly from all other players, but the winning/losing in this match would only count for the real player, in this scenario player E)

- A player can not participate in a given match in more than one position (meaning that there is always four different players in a match) and can not participate in two matches in the same round (only relevant if we have two tables in the tournament)

- The players that to not participate in the 1 or 2 matches pr. round will just be spectators/preparing for the next round/match where they will participate.

- Wish: As far as possible the matches for a given player should be spread well about between all rounds. So if e.g. the tournament consist of 9 players playing on 1 table as "all-against-all" (8 matches for each), player 1 should not play all of his/hers matches in round 1-8, while e.g. player 9 played the majority of his/hers matches in round 9-18. It would be much desired that player 1 participated in e.g. round/match 1, 3, 6, 7, 10, 11, 14 and 16, meaning that he/she had a maximum of 1/2 mathces/rounds between the matches/rounds he/she participates in.

And now to my questions:
1) Is it possible to make a tournament like the above with all rounds except possible the last with "full tables" in all matches/rounds?

2) Can you point at a algorithm or similar that I might be able to use? (I think my scenario looks much like the whist algorithm in some ways, but it seems to mostly be aimed at situations where the number of players can be divided by 4?)

But in general; al input or ideas related to the challenges above will be very well received :-)

Thanks in advance

Nikolaj

[Ian Wakeling]

Whist schedules exist for 4n players and also for 4n+1 players, for examples of the latter typesee the Wiseman web site where they are called 'individual pairs' tournaments.  Split each round of these schedules in to mini-rounds over one or two tables and this will naturally distribute the games for one player relatively evenly over the whole tournament.  There is no 'whist algorithm' as such, so I suggest that you will better to start with a library of the Whist schedules.

For other numbers of players I think there will be problems.  I would not advise using lots of dummy players as I think this just adds another dimension to be balanced.  That is to say, the tournament will no be fair unless every player acts as a dummy the same number of times.  Perhaps you can give an example with 6 or 7 players of a schedule that you consider fair?

[nlkolbe]

Hi Ian

Thanks for your reply.

Since I asked my original question I have been looking into a lot of algoritm ideas, and implemented some of them in Javascript but has still not arrived at a solution that fulfills all of my requirements. So I'm still looking/investigating/trying to answer both of the questions :-)

In relation to your concerns about dummy players I understand the possible weaknesses that you describe. But in the last 3 tournaments I have played it hasn't been an issue, since the participants consider the possibility to play a lot of matches in the allocated time as more important than achieving a "100% fair" number of matches. So in our experience also the last matches with some dummy players function well, and in some cases we just allocate the "dummy" players depending on what we find most fair for the player/players who has something to play for in the final match in the tournament (Often the winner will already be found at this time, and in some case this tournament is "only" used to find the four/eight participants that should enter a final round to find the two best players).

Examples of 6 and 7 player scedules that we would normally consider fair are given below (they are quickly "hand made", so there may be errors, but the ideas is to show how one match with "dummy players" could fit in for us)

Example of a 7 player schedule on 1 table with 6 matches for each player (players named 1-7):
Round 1: 1-5 vs 2-6
Round 2: 3-7 vs 2-5
Round 3: 3-6 vs 4-7
Round 4: 1-7 vs 3-5
Round 5: 4-6 vs 2-7
Round 6: 1-6 vs 4-5
Round 7: 1-3 vs 2-4
Round 8: 5-7 vs 1-4
Round 9: 2-3 vs 6-7
Round 10: 1-2 vs 3-4
Round 11: 5-6 vs. (two random players)

Example of a 6 player schedule on 1 table with 5 matches for each player (players named 1-6):
Round 1: 1-4 vs 2-5
Round 2: 3-6 vs 2-4
Round 3: 1-6 vs 3-5
Round 4: 1-5 vs 2-6
Round 5: 3-4 vs 5-6
Round 6: 5-4 vs 2-3
Round 7: 6-4 vs 1-2
Round 8: 1-3 vs (two random players)

If (when?) I found an answer for question 1 or/and 2 I will get back :-)

Nikolaj

[Ian Wakeling]

Hi Nikolaj,

The example makes things much clearer, thanks.

I know that you have stated that you are not too worried about opponent balance, but I would place much more importance on this, as it is a key property of the Whist schedules.   For example in the 7 player schedule above, player 1 plays against 4 and 5, three times, and against 6 and 7 only once.  If 4 and 5 just happened to be the best two players, then player 1 would naturally think the schedule unfair.

I think it might work with 7 players if the odd pair does not partner and also does not oppose, so only 10 rounds of play. Of course this means that these two players will have one less game than the others.  For example I can find the schedule below:

[(C F):(D E)]
[(A C):(F G)]
[(A B):(E F)]
[(A E):(C G)]
[(D G):(B F)]
[(D F):(E G)]
[(B E):(A G)]
[(C E):(B D)]
[(A F):(B C)]
[(C D):(B G)]

where (A D) is the odd pair. To the other 5 players it appears like a whist schedule since they play once with everyone else and twice against everyone else.  My guess is that a schedule like this will exist for 7 or more players where the number of players is of the form 4n+2 or 4n+3.

Ian.

[nlkolbe]

Hi Ian

Thanks for the answer, your reflections and the suggestion for a fair schedule for a 7 player tournament.

I see your point about opponent balance, and will consider whether I should put more focus on ensuring that this is fair.

The suggested schedule seems fair, and I'm glad to hear that you think I could be applied to 4n+2 and 4n+3 in general (meaning that we can cover all situations, if I'm right in remembering, that the Whist schedules already applies to 4n and 4n + 1).

However, I'm unsure whether the suggested schedule can also be applied if the members of 7 player tournament won't play "all-against-all" (6 matches) but e.g. only 3 matches pr. player (due to lack of time). That would mean that only 5 "complete" matches/rounds are played, and in the schedule above, I can't just take the top 5 matches from the list, since this would mean that e.g. player B had at that point only played two matches (match 3 and 5) whereas player F would have played four matches (match 1, 2, 3 and 5). But I'll look into whether some simple replacement of matches may help on that challenge :-)

Thanks for your inputs

Nikolaj