Round Robin Tournament Scheduling

Schedules - You must register to Post and Download => Requests => Topic started by: FrankClydeEnglish on July 13, 2011, 04:11:20 PM

Title: 10 person whist 'good enough' solution
Post by: FrankClydeEnglish on July 13, 2011, 04:11:20 PM

I need a OK solution for a casual 10 person spades tournament, without ghosts.  Each person should play with and against everyone at least once, and play the same number of games.  Also the duplication should be fairly evenly spread...  I have been unable to design anything that makes sense, and was just hoping that someone with more time or experience has already looked at this.  Thanks for any help that can be provided.

Title: Re: 10 person whist 'good enough' solution
Post by: Ian Wakeling on July 14, 2011, 03:49:41 AM

In order to play the same number of games you must have a multiple of 5 rounds (as you have 2 byes per round and it should be possible to arrange that each player gets exactly one bye in every block of 5 rounds). Unfortunately this means that you can not balance out either the number of times players meet as partners or opponents. The first multiple of 5 that meets your 'with and against everyone at least once' criterion is 15 and so the schedule below may be useful. Pairs of player partner either once or twice, and oppose either two or three times - and it's also symmetric in the sense that pairs play together either as partners or opponents exactly four times each.

Hope that helps.

( 2  5  v 4 10) ( 3  8 v  6  7)  ( 9  1)
( 3  1  v 5  6) ( 4  9 v  7  8)  (10  2)
( 4  2  v 1  7) ( 5 10 v  8  9)  ( 6  3)
( 5  3  v 2  8) ( 1  6 v  9 10)  ( 7  4)
( 1  4  v 3  9) ( 2  7 v 10  6)  ( 8  5)
( 7 10  v 5  9) ( 8  2 v  3  1)  ( 6  4)
( 8  6  v 1 10) ( 9  3 v  4  2)  ( 7  5)
( 9  7  v 2  6) (10  4 v  5  3)  ( 8  1)
(10  8  v 3  7) ( 6  5 v  1  4)  ( 9  2)
( 6  9  v 4  8) ( 7  1 v  2  5)  (10  3)
( 6  8  v 4  5) ( 1  9 v  3 10)  ( 2  7)
( 7  9  v 5  1) ( 2 10 v  4  6)  ( 3  8)
( 8 10  v 1  2) ( 3  6 v  5  7)  ( 4  9)
( 9  6  v 2  3) ( 4  7 v  1  8)  ( 5 10)
(10  7  v 3  4) ( 5  8 v  2  9)  ( 1  6)

Title: Re: 10 person whist 'good enough' solution
Post by: FrankClydeEnglish on August 05, 2011, 09:32:50 AM

That looks great Ian, thank you.  I had a computer chugging away in the corner checking possible combinations using brute force, with little hope that it would find an answer out of the 7x10^89 combinations.  Just out of curiosity, because I could not come up with anything aproaching an algorithm, how did you derive this?

Title: Re: 10 person whist 'good enough' solution
Post by: Ian Wakeling on August 06, 2011, 02:09:48 AM

Frank,

The brute force approach always suffers from the 'combinatorial explosion' with this type of problem. Even checking a million a second for a year is not going to scratch the surface when there are 10^89 possibilities.

I have used an algorithm and it works like this.  Examine the schedule above to see that it is uniquely determined by the 1st, 6th and 11th rounds, the rounds below these are determined by the looping over the two cycles (1 2 3 4 5) & (6 7 8 9 10).  So start with 1 to 10 randomly assigned within the three starter rounds, then apply an iterative improvement approach making swaps within rounds. Always make swaps that improve the partner/opponent balance the most.