Whist-style tournament, 30 players, 8 rounds

[raydog]

I play in an annual euchre tournament with a group of college friends which is as much about socializing as it is about cards. Attendance varies from year to year, from the low 20's to the high 30's, and I am in charge of creating the schedules for the seeding and tournament rounds.
My question here concerns the seeding round, where we try to have each player sit with as many other players as possible (either as partner or opponent) before sitting with the same player twice. Clearly a "whist" type tournament schedule. We always play 8 seeding rounds. So in the case of 30 players, we play 8 rounds of 7 games each, with 2 players getting byes each round. With 6 "meetings" per game (2 partner combos and 4 opponent combos), we get 336 total meetings, and 435 possible meetings (for 30 players). So ideally it should be possible to create a schedule where no two players sit down twice at the same table.
This forum has been an incredible resource for me in creating my tournament schedules, but there are plenty of non-standard situation, like this one. My strategy was to start with a perfect 28-player schedule [where it's possible to play up to 9 rounds without repeat meetings] and replace a different 2 players each round with the 29th and 30th players, the replaced players being the ones getting byes (and one round requires no replacement: the 29th and 30th players get byes). To my chagrin, I have not been able to find the perfect schedule; my best is one where one pair of players meet each other twice.
Is there a perfect schedule? And more importantly, is there an ideal strategy for hunting down the perfect (or near perfect) schedule in similar cases? I am writing java programs to check hundreds of millions of permutations, but the possibilities soon explode into untenable realms.
Any advice greatly appreciated. And thanks for all the superb data and analysis already contained in this forum!
Ray

[Ian Wakeling]

Ray,

I think the schedule below will meet your requirements.  There are 9 rounds with no repeated pairs of players, where the groups of two in the last column are the byes.

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

I have found this with a computer, however I have not tried to modify the 28 player schedule, instead I searched for a cyclic solution which reduces the problem to finding just 3 rounds (the 1st, the 4th and the 7th), since all other rounds are found by rotation within groups of 3 players (1 2 3), (4 5 6), etc.  For example player 1 in the 1st round becomes 2 and 3 in the next two rounds, while player 2 in the first round becomes 3 in the 2nd round, and then back to 1 in the 3rd round.  There is no single strategy for finding schedules unfortunately, so it's difficult to offer advice.  The most general algorithm would be to assign players randomly to tables and byes in each round, count pairs, and then look for player swaps within a round to improve the pairwise balance.  But this might not give as nice a schedule as the one above, and it is unlikely to ever find the perfect schedule for 28 players - for that you must use the mathematical construction. 

Ian

[raydog]

Thank you for this, Ian. I imagine using the cyclic solution, rotating groups of 3 players, only works when the number of players is divisible by 3? The solution for 28 players already exists in this forum, up to 9 rounds can be played without repeat meetings. For 27 and 33 players I also have found a perfect solution with no repeat meetings (generally not so difficult when there are a large number of players).
As a corollary problem I am looking at 20 players, 8 rounds of play. A perfect schedule exists for 5 rounds (no repeat meetings), I am now testing permutations of players while repeating 3 of those 5 rounds, the aim being to make sure EVERY possible pair of players meets at least once while no pair meets more than twice. The best I have found is a solution where just one pair of players never meets. A secondary consideration (in the case there is more than one solution) would be a preference for players meeting once as partners and once as opponents if they are to meet twice (rather than twice as opponents).
I think I will look at player swaps (as you suggested) within my near-perfect solution and see if I can achieve my goal.

[Ian Wakeling]

Ray,

Thanks for your reply.  For schedules without any repeated pairs, then the cyclic method is an option for multiples of 3, and multiples of other odd numbers.  I am faimilar with the 28 player solution, this is known as a 'resolvable balanced incomplete block design' and if you search for this term you should find the mathematical literature on the subject.

I agree that if you are limited to about 8 rounds, then the problem is going to get easier as the number of players becomes large.

For the 20 player problem, I think I would take a different apporach.  Rather than trying to augment the 5 rounds with another 3, I would make the 8 rounds in one go.   I can show you such a schedule if you like, with all pairs once or twice.  Then in a second step I would try to make an optimal assignment of each table of four to two pairs, such that the partners-once-and-opponents-once criterion was met.

Ian

[raydog]

Hi Ian,
I had trouble implementing your idea in a manner which required less computational time than the way I was approaching (probably due to my limited programming skills / the inefficiency of my algorithm), but I am happy to say that I just stumbled across a solution I was looking for after a couple of months of systematically checking permutations using my method. I am posting it below in case anyone else has a need for it, either as is or as a starting point for further investigations.

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

To reiterate, this is a schedule for 20 players, 8 rounds, where every possible pair of 2 players meets at least once, doesn't meet more than twice, and doesn't play as partners twice.

Cheers,

Ray