Round Robin Tournament Scheduling

Am I asking for the impossible?

GoldenOldie · 27 · 6135

raydog

  • Newbie
  • *
    • Posts: 0
Reply #15 on: October 12, 2022, 07:11:49 PM
Ian, you're a genius!

Thank you for the improvement to my 24 player schedule. I had attacked it from a different angle and thought 8 no-meets was pretty good.

As for the 40 player schedule, I did search the forum for a solution ready-made, but gave up after 15 minutes. I figured it was there somewhere, thank you for pointing me in the right direction (this also solved my 39-player schedule).

I am attaching a spreadsheet with my solutions (not always optimized) for the other numbers of players, 15-40. Excel format. In case it is of use for others. There is a tab for each scenario, and a summary on the last tab. Some references to "Bob" (a stalwart colleague who did an incredible job devising schedules by hand many years ago), I was trying to improve upon his results. And sometimes a bit of explanation as to my tactics. Maybe this will prove useful to someone.

As for byes, I neglected to mention that a minimum number of byes is essential: everyone should play as many games as possible (no more than 1 bye). Thank you for pointing that out.

A story: a computer programmer gets a call from his wife at work. She says, "On your way home, can you pick up a loaf of bread? And if they have eggs, get a dozen." He comes home with 12 loaves or bread.

Cheers!

Ray


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #16 on: October 13, 2022, 04:12:34 AM
Ray,

Thanks for posting the spreadsheet and your kind words - I will let you know if I find any improvements.

Kind regards,

Ian


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #17 on: October 13, 2022, 12:18:55 PM
Ray,

I found the following for 15 players:

  (13  6  1 11) ( 9  5  7 12) ( 8  2 10  4)  (14  3 15)
  (15  2 13  5) ( 7 14  4  6) ( 1  8  3 12)  ( 9 11 10)
  (10 15  1  7) ( 2  4  3 11) ( 9 13 14  8)  (12  6  5)
  ( 5  8  1  6) ( 7 15 11 14) ( 3  4 13 12)  (10  9  2)
  ( 1  5  4 11) ( 2  7  8 12) ( 9 10  3  6)  (15 14 13)
  (11 15  3  8) ( 9  7  2  1) (12  5 14 10)  ( 4 13  6)
  (15  4  6  9) (12 10 13 11) ( 3  1 14  2)  ( 5  8  7)
  (10 11  9 14) (13  3  5  7) ( 2 12  6 15)  ( 8  1  4)

above read (A B C D) as (A B vs C D).  Appart from the pair 2 & 3 who oppose twice, I think it's as good as it can be, so it should come very close to your ideal parameters.

Ian


raydog

  • Newbie
  • *
    • Posts: 0
Reply #18 on: October 13, 2022, 06:12:50 PM
I don't know how you do it, Ian, but this obviously an ideal schedule. Thanks!

Ray


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #19 on: October 15, 2022, 12:24:47 PM
Ray,

Can you explain to me how you calculate the ideal values for "partner once", "oppose once", "oppose twice" & "partner once + oppose once" that I can see in the spreadsheet that you posted?   Perhaps you could take n=18 as an example.

When player pairs are going to meet twice, do you see "partner once + oppose once" as more desirable than "oppose twice"?

Thanks,

Ian


raydog

  • Newbie
  • *
    • Posts: 0
Reply #20 on: October 17, 2022, 10:42:12 AM
Ah, you caught me out! Those are more or less made up. I think I just applied some ratios I thought seemed reasonable. But there is in fact no reason to think those numbers are achievable (sorry if that was misleading - part of my hesitancy in posting this spreadsheet was the fact that there are numbers like that included!)

The cardinal rules are:
1) a pair of player never meets 3 times (which is now the case in all scenarios, thanks to your help with the 15-player scenario);
2) no player gets 2 byes until all other players have had 1 bye.

So the important numbers in that "ideal" scenario are the "never meet" number (which I strive to make 0 if there are more "possible meetings" than "possible pairings"), and the "meet 3 times" number (which I strive to make 0: solved). It's that first stipulation which may not actually be possible.

When I coded my program, I needed to specify what made a given solution better than any previous solution. So if "never meet" was the same for two scenarios [and "meet 3 times" was 0], I applied a 2nd order comparison, and prioritized "partner once + oppose once" over "oppose twice".  This just seemed reasonable, on a human level. So yes, you have interpreted correctly, but the 1st order priority is minimizing "never meet".


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #21 on: October 18, 2022, 01:39:42 PM
Consider the 18 player tournament, and count the pairs in the schedule in different ways.  With 8 rounds and 4 tables, there are 32 games.  Each game has 2 partner pairs and 4 opposition pairs, so over the tournament 64 partner pairs and 128 opposition pairs, or a total of 192 pairs.  With 18 players there are a possible 153 distinct player pairs, so the ideal arrangement, with no player pairs who never meet, or player pairs who meet 3 or more times, has:

114 pairs who meet once(x)
39 pairs who meet twice(y)

this follows because these numbers are the only solutions to:

x + y = 153
x*1 + y*2 = 192

As we have agreed, the best schedule will have all 39 pairs who meet twice of the type where 2 players partner once and oppose once. Therefore, by subtraction we can discover how the players pairs who meet once are distributed:

64 - 39 = 25 pairs who partner once
128 - 39 = 89 pairs who oppose once.

So putting this together the ideal parameters are as follows:
Never meet = 0
Partner once = 25
Oppose once = 89
Oppose twice = 0
Partner once + Oppose once = 39
Meet 3+ times = 0

This is not that far away from your Excel sheet.  So I went looking, and I can find such a schedule by computer search:

(13  6  5  1) (14  3  7 16) ( 2 10 15 11) (17 12 18  9)  ( 4  8)
( 6 11 12 15) ( 2  4 13 16) (17  8 10  3) ( 7 18  1  9)  (14  5)
(14  8  1 12) (11 17  7 13) (15  6 16  9) ( 5  2  4 18)  (10  3)
(13  1 10 16) ( 5 11  9 14) ( 3  4 18 12) ( 7  6  2  8)  (15 17)
(15 17  1  4) (11 13  8  3) (18  2 14 10) (16  5 12  7)  ( 9  6)
(18 14 15 13) ( 6  4 10  7) ( 5 17 16  8) ( 1  2  9  3)  (12 11)
( 3  5 10 15) (11 18 16  6) ( 8  9 14  4) ( 2 12  1 17)  ( 7 13)
( 3 17  6 14) ( 9 12 10 13) (15 18  7  8) ( 4  5 11  1)  ( 2 16)


raydog

  • Newbie
  • *
    • Posts: 0
Reply #22 on: October 18, 2022, 08:58:02 PM
Certainly can't argue with your logic, Ian, and get another ideal solution! I'm updating my spreadsheet with each update, will repost once you get tired of optimizing my results.

Thanks again!

Ray


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #23 on: October 23, 2022, 04:47:02 AM
Ray,

I have been having another look at 26 players and using some statistical experimental design software, I can get an improvement.  Your excel file has a schedule with parameters (52,10,5) for (never meet, partner twice, partner/oppose once). The schedule below has parameters (46,0,9) where players 11 to 26 are the ones who get a bye.

(12  3 18  1) ( 7 23 25 14) (20 22 17 15) ( 8 21  2  4) (11  5 10 13) ( 6 19  9 24)  (16 26)
(23 12  4 10) ( 2 18 14 20) ( 1  9 25  5) ( 3 13  6 17) (19 26 15  8) (21 16  7 24)  (11 22)
( 2 22 10 16) (23 26  6  5) ( 4 17 19  1) (12 11 24 15) ( 9 14 21 13) (20  7  8  3)  (18 25)
( 6 10  8 20) (26 21 11  1) (24  3  2  5) (15 13 18 23) (25 19 12 16) (22  4  7  9)  (14 17)
(18 11  6  2) ( 3 16 15  9) ( 8 23 22  1) (26 13  4  7) (14  5 19 20) (21 17 25 10)  (12 24)
(25 11 22  3) ( 1 16 13 20) (24 17 14  8) ( 7 18 19 10) ( 6  4 15  5) (12  2 26  9)  (21 23)
( 4 14 16 11) (13 25  8  2) (10  1  9  6) ( 3 23 19 21) (12  5 17  7) (24 18 22 26)  (15 20)
( 2  1  7 15) (23 17  9 11) ( 3 14 26 10) (16  8 18  5) (21 12 22  6) ( 4 24 20 25)  (13 19)

as with the other schedules the match (A B C D) should be read as (A B) vs (C D).
« Last Edit: October 23, 2022, 04:49:52 AM by Ian Wakeling »


raydog

  • Newbie
  • *
    • Posts: 0
Reply #24 on: October 29, 2022, 08:43:58 AM
Another fine improvement to my schedule, thanks!

Ray


AEuchreDude

  • Newbie
  • *
    • Posts: 0
Reply #25 on: October 15, 2023, 12:03:52 PM
A big thank you to raydog for posting your schedules. This is exactly what I have been looking for. I am creating scorecards for a Euchre tournament for 2-48 players. I was able to take raydog's info and create "perfect" scorecards from 41-48 players successfully.

raydog, do you have any updated/improved schedules?

Ian, would you be able to help improve some of my schedules? A small problem was raydog's schedules were for 8 rounds and I only want 7 rounds.
I attached a spreadsheet that has 12,13,23,25,26 schedules that it seems could be improved upon. The 25 and 26 schedules are raydog's, not sure if these can be made "perfect" but raydog's 24 player is.

I have the exact same criteria as raydog except I have 7 rounds instead of 8.
Thank you for any help
« Last Edit: October 15, 2023, 12:12:05 PM by AEuchreDude »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1141
Reply #26 on: October 30, 2023, 01:28:27 PM
AEuchreDude,

I have been thinking about the three larger schedules that you give above.  These are of the sort where it might be possible to have no pair of players meet twice. I am getting quite close.

23 players:

 ( 3 18  4 13)  ( 5  7 20 15)  ( 1  9 16 12)  (14  8 11 10)  (17  2 19  6)
 (23 22  9 13)  (12  3 17 11)  (16  5  4  8)  ( 7  6 14 21)  (10 15  1  2)
 (11 21 23 13)  ( 8  2  3  9)  ( 5  6 10 12)  ( 1  7  4 22)  (19 14 18 20)
 ( 6  1 18 11)  (23 20  4  2)  ( 5 21  9 17)  ( 8 15 19 22)  (10 16  7  3)
 ( 7 23  8 12)  ( 5 19 13  1)  (14  4 17 15)  ( 6 22  3 20)  (18  2 21 16)
 (22  2 11  5)  (18 15 12  9)  (23  3 14  1)  (17 20 13 16)  (10 21  4 19)
 (17 10 22 18)  ( 9 11 19  7)  ( 2 14 13 12)  (21 20  8  1)  (15 23  6 16)

Above the pairs (9 12) & (13 23) are the only ones who meet twice.

25 players:

 (18 22  1 19)  ( 9 20  7  8)  (24 12 15  6)  (16  2 17 13)  (10 23 14  5)  ( 3 11 21  4)
 ( 7 19 12  3)  (10 21 20  1)  ( 6 22 16 14)  (17 15 18 25)  (13 23  8  4)  ( 9  2  5 11)
 ( 5 22  4 15)  (20 18 16 11)  ( 3 24  8 10)  (17  1  9 12)  ( 7 13 19 14)  (21  2 25  6)
 ( 7 10 15 16)  ( 2 23 24 19)  (18 14  3  9)  (12 20 25  4)  (13  1  6 11)  (17  8 21  5)
 (22  3 17 23)  (20  6 19  5)  (18 12 10 13)  (15 11  8 14)  (16 24  9 25)  ( 4  1  7  2)
 ( 6  7 18 23)  (22  8 12  2)  (13 21  9 15)  (16  3  5  1)  (10 25 19 11)  ( 4 14 17 24)
 (17 22 11  7)  ( 3 20  2 15)  (24  5 13 18)  (12 23 21 16)  ( 4  6 10  9)  ( 8  1 14 25)


Above the pairs (7 19), (8 14), (13 18) & (17 22) are the only ones who meet twice.


26 players:

 (15  4 23 10)  ( 6 22  2  5)  (14 24 11 18)  (20 17 12  9)  (16  3  7 19)  (21  1 13  8)
 (12 13  4 18)  (11 20 10  3)  ( 9  2  1 25)  (22 14 15 19)  ( 5 26 16 21)  ( 6 17  8  7)
 (26 15 11  9)  (23  3 12  8)  (18  7  2 10)  ( 5  4 19 24)  (20 14  1  6)  (17 16 13 25)
 (14 10 25 21)  (12 24  1 26)  ( 5 18 15  8)  ( 7 22 13 11)  (23  6  9 16)  ( 2 17  4  3)
 (14 26  8  2)  (24 23 22 25)  ( 9  5 13  3)  ( 1 16 11  4)  (20 15 21  7)  (19  6 12 10)
 (26  6 25  4)  (17 11 23 21)  ( 2 20 13 19)  ( 8 10  9 24)  ( 1 22  3 18)  (14  7  5 12)
 (12 16 15  2)  (11  8 19 25)  ( 4  7  9 22)  ( 3 21  6 24)  ( 5 10  1 17)  (26 20 23 18)


Above the pair (7 22) is the only one to meet twice.

If games such as (A B C D) in the schedules above are played as (A B vs C D) then those who meet twice will do so once as partners and once as opponents.

Those sitting out are logically arranged with the highest player numbers sitting out in the first round.

Hope that helps.
« Last Edit: October 30, 2023, 01:32:26 PM by Ian Wakeling »