Court balanced rond robin with limited number of courts

[masipila]

Hi all,

First of all, big Thank You! I've read through the thread linked below and implemented a schedule optimizer to the result service of my website to help curling tournament organizers generate round robin schedules: https://www.devenezia.com/round-robin/forum/index.php?topic=281.0

The algorithm described there assumes that there are as many courts available that is needed. For example with 8 teams, there will be 4 courts and the games will be distributed to these 4 courts ideally. So far so god.

Now to my question. One of the most typical scenarios we have here in Finland for the sport of curling is that we have groups / pools of 6 teams and the games need to be distributed to 2 courts (we have curling halls which have 2 courts).

I can easily generate an optimal schedule for 3 courts and then I can try to manually tweak the result and try to move the games from court 3 to courts 1 and 2 in Excel but I haven't figured out a systematic way how to do it ideally. In other words, I haven't been able to figure out an algorithm how to achieve the optimal result.

Any thoughts on this?

[Ian Wakeling]

If I am understanding correctly then you can do what you want by slicing up the full tournament.  So take the standard cyclic schedule for 6 players  : 

Round 1	1 6	2 5	3 4
Round 2	1 5	4 6	2 3
Round 3	1 4	3 5	2 6
Round 4	1 3	2 4	5 6
Round 5	1 2	3 6	4 5

(I made this by going here and choosing 'cyclic' and '6 items').  Now remove the last column so you have 5 rounds for 2 courts, and  then rearrange the removed games as follows:

Round 6 (3 4) (2 6)
Round 7 (2 3) (5 6)
Round 8 (4 5) (- -)

If there are 8 teams then you just cut each round into 2 halves.  For 10 teams cut the first four columns into halves and rearrange the last column.

Ian

[masipila]

I'm looking for an ideally balanced result with two objectives:
- Each team plays on each court the same amount of games (or as close as it is mathematically possible)
- Each team has the same amount of home/away games (or as close as it is mathematically possible)

The rationale for these objectives in the sport of curling is that:
- Each court (sheet of ice) has their own characteristics
- The away team has an advantage of having a second pre-game practice. The home team has the first pre-game practice.

With the algorithm mentioned on my opening post, I'm able produce this:

Round 1 (3 6) (1 2) (4 5)
Round 2 (6 2) (5 3) (1 4)
Round 3 (4 3) (2 5) (6 1)
Round 4 (2 4) (3 1) (5 6)
Round 5 (1 5) (6 4) (2 3)


This is ideal, if our curling halls would have 3 sheets of ice (courts). But they only have 2, so I need to move the games that are scheduled for court #3 to courts 1-2.

The issue that I have here is how to do that so that the result would still be as balanced as possible.

If I just move the games from court #3 to the two courts as rounds 6-8, the result would be for example this:

Round 1 (3 6) (1 2)
Round 2 (6 2) (5 3)
Round 3 (4 3) (2 5)
Round 4 (2 4) (3 1)
Round 5 (1 5) (6 4)
Round 6 (4 5) (6 1)
Round 7 (1 4) (5 6)
Round 8 (2 3)


Considerations for "what is ideal"
- All teams have 5 games.
- Ideally they would all play twice on both courts, once as home and once as away team
- It's unavoidable that each team will play their fifth game with a court + home/away combination that has already occurred

Analysis of the above schedule:
- Team 1: plays twice on court #1, but both times as home team. Not ideal.
- Team 2: ideal
- Team 3: ideal
- Team 4: plays 4 games on court #1 and only once on court #2. Not ideal.
- Team 5: plays twice on court #1, but both times as away team. Not ideal.
- Team 6: ideal

So my question here is that is it mathematically possible to get a better result to begin with and if yes, what would be an algorithm that would produce that...

Cheers,
Markus

edit: I elaborated why the curling-specific rationale to the beginning of this comment.

[Ian Wakeling]

Thanks for your reply.  I don't know of any simple mathematical construction here.  If I were doing this I think I would take a two part approach - firstly I would make the basic schedule, balancing sheets but without considering home and away, and then in phase 2 I would swap around the left and right teams from each pair to optimize the home and away.  I do have an algorithm that will do the first part, it's an iterative approach placing all the games randomly in the schedule to begin with, and then moves games around to balance out the sheets and keep all the teams in a round unique.  For example this gives me:

(5 6) (1 3)
(2 4) (1 6)
------------
(1 5) (2 6)
(2 3) (4 5)
------------
(1 2) (3 4)
(4 6) (3 5)
------------
(3 6) (2 5)
(1 4) (---)

Where teams play either two or three times on each sheet.  The teams also play at least once, and at most twice, in each of the groups of two rounds in between the dashed lines.  The algorithm finds this easily so I suspect it is always possible to do this.  Perhaps you could use this as the starting point to balance home/away.

Regards,  Ian

[masipila]

Thanks for your thoughts!

From your example, it is possible to get a mathematically ideal solution with the "2nd pass" approach you suggested, i.e. keep the pairs but try to swap the home / away teams in each game so that the court is kept but the only thing that changes is the home / away team.

For example like this_
- here each team plays 2-3 games on each court
- and each team plays 1-2 times as home / away on each court
- ... which fulfills the criteria of "ideal" which I defined in the beginning



Now, the big question here is that what would be an algorithmic approach to do this, now I was doing the home/away balancing by staring at the data and with a couple of rounds of trial and error I was able to do this. But the whole point what I'm trying to achieve here is to save the tournament organizers' time so that an algorithm would be able to produce them as ideal schedule proposal as possible...

[Ian Wakeling]

To automate the assignment of home and away I would create an algorithm based on the matrix below which records the frequency of H/A games on the two sheets.

	HS1	AS1	HS2	AS2
T1	2	1	1	1
T2	1	2	1	1
T3	1	1	2	1
T4	2	1	1	1
T5	1	1	1	2
T6	1	2	1	1

So column HS1 for example counts home games on sheet 1, and team 1 has two such games.  The matrix above is calculated for your ideal solution, and as such the sum of squares of all the matrix elements is 42, the lowest that it can be.  Any other sub-optimal solution will have a higher sum of squares.  This provides the basis for an algorithm starting from a sub-optimal schedule, consider swapping H/A for each game in turn and pick one of the swaps that provides the biggest decrease in the sum of squares of the matrix.  Iterate this process until you reach an ideal schedule.  If the algorithm gets stuck, then you may need to stop it returning to a state that it has just visited.

[edited to correct a few typos]

[masipila]

Thanks for the suggestion!

I was thinking more about this in the morning and tried an approach (manually in Excel) which applied perfectly to 6 teams on 2 sheets. I haven't tried yet how generally applicable this would be for other team and sheet counts.

Here's how I approached this:

1. Generate an ideal schedule without considering the court limitations
I used this: https://www.devenezia.com/round-robin/forum/index.php?topic=281.0

The result is as follows, observe that the home / away is ideally balanced already.


2. Re-allocate the sheets, iterating the games from team 1 onwards. Allocate the games using a snake.

Iteration after considering team 1:


Then move on to the remaining games of team 2. The first new game will be allocated to sheet 2 and the next one also on sheet 2 so that the snake will also apply to team 2.


Then move on to team 3. Team 3 previously has two games on sheet 1 and 0 on sheet 2 so we will start from sheet 2. Also the second new game will be allocated to sheet 2 because of the snake rule. 


Then move on to team 4. Team 4 previously has two games on sheet 1 and one on sheet 2, so we will allocate the first new game to sheet 2.



Then move on to team 5. Team 5 previously has one game on sheet 1 and 2 games on sheet 2 so we will allocate the new game on sheet 1.


Then move on to team 6. Team 6 previously has one game on sheet 1 and three games on sheet 2, so the new game will be allocated on sheet 1.



This result fulfills the requirements of an "ideal" schedule and as mentioned, seems to apply to at least 6 team round robin on two sheets.

Cheers,
Markus

[Ian Wakeling]

Thanks for posting all your workings here.  Like you, I am also not sure if this will generalize to more than 6.  Let me know if you get stuck on 8+ teams and I might implement my suggestion above.

[masipila]

I'll document my experiments here directly so that I don't have to do it twice

Experiment: 7 teams round robin, need to squeeze this from three sheets to two.

Starting point: Ideal schedule is generated, but it requires three sheets:


Iteration for team 1, looks good.


Iteration for team 2. I'm adding the new games to the bottom and not yet to the first possible slot to make it easier to follow the snake. Previously allocated games are yellow, new ones that are allocated on this iteration are green.


Iteration for team 3. Things start to boil down because team 3 now has 4 games on sheet 1 and 2 games on sheet 2


If the algorithm would have a rule that this is not allowed and it would force the last game (3 4) to sheet 2 if it's available, it would look like this:


Itearation for team 4.


Iteration for team 5. Also here that special rule invented above needs to be applied for the last game.


Iteration after team 6.


Let's now fill the gaps to see the final result:

The result is ideal.

Note to self: the logic for this scenario would be something like this:

• First calculate what is the max number of allowed games for each sheet. For 7 teams, there will be 6 games for each team. For two sheets, there should be 3 games on each sheet. Let this be GAMES_PER_SHEET.
• Use the snake pattern on each iteration. Take the previously allocated games into account.
• If the snake pattern would lead into a situation where there will be more than GAMES_PER_SHEET on one sheet, force the game to the other sheet.

[masipila]

Experiment: 8 teams round robin, squeeze from 4 sheets to 2.

Ideal schedule with 4 sheets:


This could be squeezed simply by moving all games from sheet 3 to sheet 1 and from sheet 4 to sheet 2. But let's test how the algorithm used above would work here.

Team 1:


Team 2:


observation: team 2 is always playing "away" on sheet 1: not good.

Team 3:


Team 4:


Team 5:

Observation: Team 5 plays 3 times "away" on sheet 2 and always "home" on sheet 1. Not good.

I did not continue from here onwards because it's clear that this approach does not generalize well.

[Ian Wakeling]

I might have another way of making what you want for an even number of teams n>=10.  It is a rearrangement of a PBTD (see my first reply here).  I think the folowing works where the teams are 1-9 and X for team 10:


(8 X)  (5 9)
(7 9)  (6 X)
(5 4)  (2 8)
(6 3)  (1 7)
(2 1)  (4 3)
(4 6)  (9 1)
(9 8)  (7 5)
(3 5)  (X 2)
(X 7)  (8 6)
(4 2)  (3 8)
(1 3)  (7 4)
(6 1)  (3 7)
(5 2)  (4 8)
(3 9)  (1 X)
(4 X)  (2 9)
(7 8)  (6 5)
(X 5)  (7 2)
(1 4)  (X 3)
(9 6)  (8 1)
(2 3)  (9 4)
(6 7)  (5 1)
(8 5)  (2 6)

the missing game (9 X) can be placed anywhere.