Louis Nelen
Belgium Gent België

I'm trying to organize a league play for a racing game (thunder alley). I have a specific case now, but I would like to get a general solution for future plays.
There are 7 players and we want to play each game with 4 players.
restrictions
*Each player has to play the same amount of races *Every player plays at least once every two games (in order to get interim scores) *Each player should play all the other players the same amount of races
This is what I've come up with:
race1 A B C D race2 E F G A race3 B D F G race4 C E B F race5 A C D E race6 G A B E race7 G C D F race8 C D E F race9 G A B C race10 D F A B race11 E G D A race12 C E F G race13 B C D G race14 B E F A
The first and second condition are met. The third is not.
X A B C D E F A B 5 C 3 4 D 4 4 5 E 5 3 4 3 F 3 4 4 4 5 G 4 4 4 4 4 4
It's very close to each player playing all the other players 4 times.
Is there a way to find a solution or an optimal case?

Jeremy Lennert
United States California

plytho wrote: I have a specific case now, but I would like to get a general solution for future plays. It's not clear to me what parts of this would be considered variable for a "general" solution.
plytho wrote: The first and second condition are met Actually, your example assignment does not meet your second condition: for example, player A does not play in either race 3 or race 4, so he is not playing once every two games.
Looking at the constraints you listed, I notice that the requirement that everyone play at least once every 2 games, combined with the fact that 2 games have only slightly more total slots than you have players, means that you are almost simply dividing your player group in half for every pair of games. You also need one player to play in both games to fill them up.
So I'd start by saying that the players will take turns "doubling up"player A will be in both race 1 and race 2 (everyone else will be in either race 1 or race 2 but not both), player B will be in both race 3 and race 4, player C will be in both race 5 and race 6, etc. This is both necessary and sufficient to ensure that you meet conditions 1 and 2.
So now the problem is just, for each pair of games, how to split the 6 remaining players in half in order to optimize condition 3.
There are only C(6,3) = 20 possible splits for any pair of games, so at that point my inclination would be to consider each pair of games one at a time, in chronological order, and test all 20 possible splits for the one that optimizes condition 3 based on all previous games (this could be done with a simple computer program). That might not be optimal in the long run, though, because we're optimizing each round without regard for the later rounds.
If you need a true optimal solution, I'm not seeing an obvious approach that's better than brute force. Anyone else?

Louis Nelen
Belgium Gent België

Antistone wrote: plytho wrote: I have a specific case now, but I would like to get a general solution for future plays. It's not clear to me what parts of this would be considered variable for a "general" solution.
Variable parts would be the number of players (total) and the number of players per game. A third variable would be the number of games. The number of games is already somewhat restricted by the first two.
The general problem would be:
Make a shedule for N racers to race in X matches with Z players each.
Antistone wrote: plytho wrote: The first and second condition are met Actually, your example assignment does not meet your second condition: for example, player A does not play in either race 3 or race 4, so he is not playing once every two games.
I didn't express that correctly. What I meant is that after 2 games everyone played at least once, after 4 games at least twice, etc.. So after 4 games all players played 2 races and we can compare the scores and see how everybody is doing after their second game.
I've created the above list manually by matching the first and second condition and getting as close as possible to the third. I've tried moving racers to get all 4's but so far it failed. I'll probably play this schedule because it's close enough but I'd prefer playing the neater solution if it exists.

Jeremy Lennert
United States California

plytho wrote: I didn't express that correctly. What I meant is that after 2 games everyone played at least once, after 4 games at least twice, etc.. So after 4 games all players played 2 races and we can compare the scores and see how everybody is doing after their second game. It sounds like what you're aiming for is for all players to have played a similar number of games at any given point, in which case a better requirement might be "at no point should the difference between two players' number of races be greater than 1". That basically means that if player X has already played more games than player Y, then player X can't play again before player Y does.
That also has the advantage that it makes your first condition redundant, so you can simplify your requirements.


