Round Robin Tournament Scheduling

Schedules - You must register to Post and Download => Requests => Topic started by: Glitchman(Guest) on July 17, 2007, 12:23:45 PM

Title: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Glitchman(Guest) on July 17, 2007, 12:23:45 PM

I apologize for such a long post, but I strongly believe that this site has the most
knowledgeable people to handle such scenarios. A working solution would benefit not only
this particular game, but numerous others that I can imagine!

I am creating the structure for a video game tournament, where 4 players at a time compete
on a given television. I am in a dilemma at the moment, since the number of players showing
up is not yet known, with only a couple weeks left to get the structure ready for any
number of players, possibly up to 21 people.

Anyway, I have successfully devised the following setup for 8 players, by making some
alterations to a 2-table euchre scenario. This worked fairly well last time (even though
only 7 showed up):


Round    TV 1    |   TV 2
  1     5 2 1 6  |  3 4 7 8
  2     2 5 8 3  |  4 7 6 1
  3     1 8 3 6  |  7 2 5 4
  4     1 3 4 2  |  8 6 5 7
  5     2 1 7 8  |  3 4 6 5
  6     6 7 2 3  |  4 1 8 5
  7     6 8 2 4  |  7 5 3 1
  8     5 6 4 7  |  8 3 1 2


Let g = the number of groups (TVs / game consoles) available (g = 2 here)
Let P = the number of People / Players altogether (P = 8 here)

I intend to do P rounds for P players (although I may exclude some rounds if P is too big.)
My mathematical instincts tell me that I can always work this out elegantly in P rounds for
P players.

The elegance behind this setup is that in the first P - 1 rounds (in this case, rounds 1
through 7), everyone plays everyone else precisely thrice. The Pth round (round 8 in
this case) is needed to accommodate a particular flaw in this game, as follows:

In this particular game, the order of seats matters significantly! The problem with this
game is that no two players can pick the same character, and everyone prefers 3 specific
characters. Whoever gets 4th pick will get the shaft, so to accommodate this flaw, I set it
up so that everyone gets 1st, 2nd, 3rd, and 4th picks equally. As you can see, the Pth round
does exactly that. I'm not nearly as concerned that some players end up on the same TV more
than some others, as that may be unavoidable.

Is there an algorithm to work this out whenever P = 4g?

Again, the priorities are:
#1. Everyone gets 1st, 2nd, 3rd, 4th pick equally
#2. Everyone plays everyone precisely thrice in all but the last round

If so, I believe I can use the same charts for P = 4g - 1, having an "imaginary" idle
player. I just cannot avoid the advantage in round P for those lucky enough to play this
imaginary player a fourth time, but I can live with that for now.

Also is there an algorithm for P = 4g + 1? I suspect there is by having each player sit out
for one round, while still getting to play each person thrice, and getting 1st, 2nd, 3rd,
and 4th picks all equally as well.

As for P = 4g +/- 2, I just hope that I don't run into that scenario.

Thanks in advance to anyone who can solve this for P = 4g and P = 4g + 1.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Ian Wakeling on July 18, 2007, 04:26:56 AM

The first 7 rows of the schedule you have found are known a resolvable balanced incomplete block design (BIBD).  It's going to be very hard to describe an algorithm to solve the general problems you pose. So I think I would break it down into two stages, first use combinatorics to get most of the way and then tweak that to get the final schedule. So with your example above you could have obtained the first 7 rounds from some combinatorial reference and then step 2, add the last round, any arrangement of the 8 players would do and arrange the whole thing so that it has balance for the order of picking characters.

For many schedules it would be useful to look at cyclic construction methods of BIBDs.  For example if you take the following base blocks for 12 players at three TVs [note the players are not labelled 1 to 12, but rather inf,0,1,2,3,4,5,6,7,8,9 & 10]

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

Now increment each block cyclically by adding one, and reducing mod(11),
then you will obtain an a second round:

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

Note 10 wraps around to 0 in the mod(11) system, and the infinite element remains unchanged.

Repeat this procedure on the second round to get the third, etc, until you obtain an 11 round solution where everyone plays everyone else three times.

Like 8, the construction for 16 players is harder, but search this web site for "social square" and you will find a solution in 5 rounds where everyone plays everyone else just once.

The base blocks for 19 rounds of 20 players mod(19) are:

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

That's probably as high as you want to go with P=4g as I don't think you would want to play more than 19 rounds

There are other cyclic solutions that will help with P=4g+1. For example 13 players:

(0) (1 5 12 8) (7 9 6 4) (10 11 3 2)

This time there is no infinite element and you will end up with 13 rounds mod(13) which will naturally have the character balance property, i.e once in each position at each TV.  The (0) at the begining is the player with the bye, who is also developed cyclically.

Finally base blocks for a 17 player schedule mod(17)

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

Hope that is of some help.

Ian.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Glitchman on July 19, 2007, 10:59:13 AM

Thank you so much for your quick reply. I have been playing with the numbers a bit, and these will definitely get me started on the right track. I especially like the simplicity of the setups for 13 and 17 players. Those two virtually create themselves without any need to re-arrange anything!

I attempted to make a setup for 9 players similar to the 13- and 17-player arrangements. I suspect it may be mathematically impossible with a squared prime, although I am a bit rusty on group theory (and on this game too, lol.) In a nutshell, I'm trying to get 9 players in the form of the following:
(0) (x x x x) (x x x x)

For now I have compromised with a 9-player setup across 3 TVs as the following:
(inf 0 4) (1 6 7) (2 3 5)
That will give me 4 rounds with everyone playing everyone just once. I can make some substitutions to get 4 more similar rounds, and hopefully create the 9th round to give everyone equal opportunities on characters (although it's not quite as much an issue in 3-player scenarios.) Or I may just repeat it all again and have 12 rounds this way. I just prefer getting 4 players per TV whenever possible in order to maximize matchups in fewer rounds.

For 10 players,  I am not yet certain on which approach is best. I might be able to approach it as follows:
(0) (1 x x) (x x x) (x x x)
As I thought about it more, I might also be able to model it off of the trivial 5-player setup with the "5th" player on each TV sitting out:
(x x x x x) (x x x x x)
By doing this, I prevent two "bye" players from being on the same television, but it won't be nearly as elegant as most other setups.

My mind is drawing a blank for 14 or 18 players, so it is perhaps best if I concentrate on completing the other scenarios for now.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Ian Wakeling on July 20, 2007, 03:32:08 AM

There is a cyclic solution for 9 players, but you need to consider the elements to be Z3 x Z3, rather than Z9.

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

The three TV approach that you were considering for 10 players is also possible, however the construction is not so easy. I have arranged it below so that players occur three times each in the three positions within a block.

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

I am not aware of any mathematical treatment of the two byes per round scenario, so unfortunately I have no off-the-shelf solutions for 14 or 18 players.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Glitchman on July 26, 2007, 02:13:22 AM

With time getting closer, I fear we may end up with 14 players. I looked at what you posted in another thread regarding euchre and decided to start with that as a base:

Quote

   Table 1         Table 2       Table 3      Byes
(10  9 v 12 2)  ( 7 11 v 5 1)  (4 3 v 6  8)  (0 13)
(11 10 v 13 3)  ( 8 12 v 6 2)  (5 4 v 0  9)  (1  7)
(12 11 v  7 4)  ( 9 13 v 0 3)  (6 5 v 1 10)  (2  8)
(13 12 v  8 5)  (10  7 v 1 4)  (0 6 v 2 11)  (3  9)
( 7 13 v  9 6)  (11  8 v 2 5)  (1 0 v 3 12)  (4 10)
( 8  7 v 10 0)  (12  9 v 3 6)  (2 1 v 4 13)  (5 11)
( 9  8 v 11 1)  (13 10 v 4 0)  (3 2 v 5  7)  (6 12)

If I apply this to my scenario, with seating exactly in the same order, I notice that players 7 through 13 get 1st and 2nd picks twice, while the others get 3rd and 4th picks twice. They also oppose everyone either once or twice. I figure I may be able to double up these rounds, but I'll need to make some substitutions to even things out. That is, players 0 - 6 must be mapped somewhere to 7 - 13, and vice-versa, so that everyone gets equal picks.

Unfortunately, every substitution I have made so far results in some players competing with others 4 times. Is there such a substitution that I can make to complete rounds 8 through 14? I am uncertain what I am doing wrong, but some sleep will probably give me a fresh perspective.

I have all the other scenarios now accounted for, with the charts nearing completion (except 18 players, but I doubt we'll have that many at this point.) The 15- and 16-player scenarios now fit nicely into just 12 rounds. Thank you so much for your help once again.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Ian Wakeling on July 27, 2007, 12:19:21 PM

If you want 14 rounds then things are simpler than the Euchre tournament, just look for starter blocks to develop mod(14).

I believe the following will work and will pair people together at the same TV either 2 or 3 times.

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

As before there is natural balance for the selection of characters.

Hope the tournament goes well.

Ian.

Title: Re: 4-player game across 5 TVs. Help w/ algorithm!
Post by: Glitchman on July 30, 2007, 08:11:45 AM

This is perfect! With your 14-player setup, I am incrementing it in steps of three instead of one so that the same player does not have two consecutive bye rounds. Thank you so much for all your help and patience.