Foosball.com Forums

32 team double elim chart problem

0 Members and 1 Guest are viewing this topic.

ech

32 team double elim chart problem
« on: August 19, 2005, 09:02:35 AM »
I have just tried to use the contact us email form, with no luck :(

First thanks for the great double elimination charts - I hold regular table football nights, and had to break out the 32 team chart last week!

However, we ended up with some teams playing the same team twice (not in the final) ???.  I've done some research in the past on double elimination, and I think a few things need swapping on the 32 team chart.  The main one - losers bracket where it says "From C1" and "From C2" - these need to be swapped!  Otherwise you can end up with someone losing in the winners bracket, and after their next game losing again to the same team  ::).

Significantly less important is the A1-A8 losers bracket labels, these should (in theory) be A5-A8,A1-A4 rather than just reversed.  It makes very little difference, just fits with the algorithm as it should so highest seeds play lowest seeds at the round where the B level losers come in.

Any chance of getting the C2 and C1 labels swapped round at least? :)

Thanks again for the charts, they're a great help!

If anyone disagrees, here's my implementation of a 'correct' double elimination generator: http://www.mrq3.com/mrcup/dbl_elim.cgi
I'd be interested to know if anyone says that's wrong.

Cheers,
Chris

Offline SumnerH

  • *
  • 174
  • No spinning, have fun!
Re: 32 team double elim chart problem
« Reply #1 on: August 19, 2005, 11:32:15 AM »
If anyone disagrees, here's my implementation of a 'correct' double elimination generator: http://www.mrq3.com/mrcup/dbl_elim.cgi
I'd be interested to know if anyone says that's wrong.

What algorithm are you using for it?

Here's what I came up with, I'd be interested in comparing--it's all Python code but should be pretty easy to understand.  I posted an earlier version with some notes at http://groups.google.com/group/rec.sport.table-soccer/browse_frm/thread/08251a752ad0ca69/484911fcf63e85a5#484911fcf63e85a5

Here's the current one:

#
#
#
# This function recursively splits and reverses the bracket, recursing
# until the splitFactor is 1.
#
# someList is the list that you want to split.
#
# splitFactor is a recursive number set up by printBracket; it just
# doubles for every round you go out in the bracket.  Intuitively,
# it is the number of "mini-lists" that you are splitting the main list
# into.  So if [0,1,2,3,4,5,6,7] is going to become
# [2,3,0,1,6,7,4 5]), you have essentially split the original into
# 4 little segments of consecutive numbers--so splitFactor was 4 to
# generate this list.
#
# reverseFactor is whether or not to reverse the order of the matches
# inside each little split list.
def splitAndReverse(someList, splitFactor, reverseFactor):
                                                                               
    if splitFactor == 1:
        return someList
    # left and right are the left and right halves of
    # someList.  So if someList is [0,1,2,3,4,5,6,7], then
    # left is [0,1,2,3] and right is [4,5,6,7]
    left = someList[:len(someList)/2]
    right = someList[len(someList)/2:]
                                                                               
    if reverseFactor:
        return splitAndReverse(right, splitFactor/2, not reverseFactor) + \
            splitAndReverse(left, splitFactor/2, not reverseFactor)
    else:
        return splitAndReverse(left, splitFactor/2, not reverseFactor) + \
            splitAndReverse(right, splitFactor/2, not reverseFactor)
#
# This function prints the permutations for a bracket of the given size.
# The size is actually the number of matches in the first round of the
# losers bracket, so calling printBracket(8) will print out the permutations
# for a 32-team bracket (which had 16 matches in the first round of the
# winner's bracket and has 8 matches in the first round of the loser's
# bracket)
#
# The lists printed out are the ordering of the matches
# from the winner's side.  These are often labelled as A1....An for the
# second round of the winner's bracket, B1...Bn/2 for the third round,
# etc (the first round of the winner's bracket is often not given a letter)
# I don't print the letters here, just the whole ordering for the loser's
# bracket tree.  So (example here is a 16-team bracket) if it prints:
#
# [1, 2, 3, 4, 5, 6, 7, 8]
# [3, 4, 1, 2]
# [1, 2]
# That means that the first round in the loser's bracket is just the losers
# of the opening 8 rounds (this is just the first "move losers to the left
# of the center" step)
# The next round is [3,4,1,2]; the fill-ins for the loser's bracket round
# that takes 4 new teams should be from top to bottom
# the losers of A3, A4, A1, A2 in the winner's side.
# The next round is [1,2]; the fill-ins for the round should be the losers
# of A1 and A2.
def printBracket(x):
    rv = []
    splitFactor = 1
    reverseFactor = 0
    while x > 1:
        if splitFactor > x:
            splitFactor = x
        rv.append(splitAndReverse(range(1,x+1), splitFactor, reverseFactor))
        reverseFactor = not reverseFactor
        splitFactor *= 2
        x /= 2
    return rv

for p in printBracket(32):
    print p

# that's the end of the code




This code is copyright 2005, Gerry Sumner Hayes. All rights reserved.

This code is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.

ech

Re: 32 team double elim chart problem
« Reply #2 on: September 04, 2005, 01:27:58 PM »
First sorry for the long time taken to reply.
Second sorry for the utter crap in my first post  :-\

I've been drawing the charts out now, and I think my implementation is not necessarily correct.  In fact, it looks to be less correct than the 32 team chart, so please don't change it! :-[

I think there are two extremes of picking the way the players take part.  You can either make sure the top seed always plays the bottom seed at every opportunity, or you can make sure no two teams ever play twice unless they're in the final of either bracket.

1) Make sure that at every stage, the highest seed plays the lowest seed, the second highest plays the second lowest, etc.
This is how the teams are initially ordered, to ensure this is easier.
For example assuming all teams with a better seeding win every time, with a 32 team double elimination, 1v32, 17v16, etc in the first round of the winners bracket.
then the winning bracket contenders will be seeds 1-16 for matches A1-A8.  In match A1:1v16, A2:9v8, etc.  In match B1:1v8,B2:5v4 etc.

So if you keep to this rule in the losers bracket, you need to make sure the higest seed coming from the winners bracket plays the lowest seed remaining in the losers bracket.  This means your losers bracket has seeds 17,24,21,20,19,22,23,18 and your losers of games A1-A8 are 16,9,12,13,14,11,10,15
The best pairings are to keep highest playing lowest would be if every pairing totalled 33: and are 17v16, 24v9, etc - giving A1 - A8 down the losers bracket round 1.
Despite being correct and good for high seeds, this is pretty sucky - you could quite easily lose your first game to someone who comes back and beats you again one game later.  This method leads to B1,B2,B3,B4 and then C1,C2.  So the ideal way to arrange the tournament so that you get the most accurate results possible lead to you playing the same people again and again.

You can go some way to avoiding having people play each other by first attempting fair parings, then looking for a better solution if they might have played each other before.  This is what the chart does.
Because you don't want A1-A8 in order, with pairings totally 33, you can go for a compromise with pairings totalling 32 and 34 alternately.  This ends up with the reversed A1-A8 so you get 17v15, 24v10, 21v11, 20v14 etc.  Then in the next round, you end up with B2,B1,B4,B3. In the next round however, you're screwed.  There's no way you can pick teams so that you're sure you've never played anyone before.  So you go back to the best seed thing.  This is where I fell foul of it - we had teams playing each other in the winners bracket B games, and then playing again in losers bracket when the C losers came in.
So you get what the chart says as an attempt at fairness:
Losers bracket round 2: A8,A7,A6,A5,A4,A3,A2,A1
Losers bracket round 4: B2,B1,B4,B3
Losers bracket round 6: C1,C2

2) The other extreme is to make totally sure you never play anyone again (and I'm going to make a hash of explaining this too  :-[).  If we start at the stage where losers A1-A8 come into the losers bracket again, we've got players involved in the losing side of A1-A8 already there. Because the winner of A1 is about to play the winner of A2, we want to send the loser of A1 off to play the loser of the games that preceeded A2. This avoids wasting the use of any teams we've not played. For example in the previous layout the loser of A8 goes to play the loser of A1. At that point the loser of A2 hadn't played anyone from the A1 feeding teams either, but that's the last point at which we're going to be able to separate people from A1 and A2..... did that make any sense? ;D

The side effect of this is that you have completely the opposite style pairings - the best seed in the losers bracket plays the best seed coming from the winners bracket.  So you get fairer games, and you never play anyone twice.  This is what i'm going to use at my next table football evening because we play it for fun rather than to prove who's the best.  If you're interested, you end up with this:
Losers bracket round 2: A2,A1,A4,A3,A6,A5,A8,A7
Losers bracket round 4: B2,B1,B4,B3
Losers bracket round 6: C2,C1
Get the pattern? :)

Offline SumnerH

  • *
  • 174
  • No spinning, have fun!
Re: 32 team double elim chart problem
« Reply #3 on: September 08, 2005, 01:55:31 PM »
1) Make sure that at every stage, the highest seed plays the lowest seed, the second highest plays the second lowest, etc.

This means that if there are any upsets, you'll likely play the same team again very quickly.  That's bad for accurately ranking teams, since if you have one matchup where someone plays very well against another player (e.g. Mike Archer always beating Frederico Collignon) then if you replay that matchup again it'll look like the person on the wrong side is generally bad when in reality they're just badly matched against that player.

Quote
2) The other extreme is to make totally sure you never play anyone again (and I'm going to make a hash of explaining this too  :-[).

Well, you can't make sure you don't play again.  I think given 2^n teams in the bracket then you are guaranteed to meet again in n rounds.

But yeah, the brackets are supposed to be designed so that you don't meet again for as long as possible.

Quote
If you're interested, you end up with this:
Losers bracket round 2: A2,A1,A4,A3,A6,A5,A8,A7
Losers bracket round 4: B2,B1,B4,B3
Losers bracket round 6: C2,C1
Get the pattern? :)

If I'm understanding the terminology, this is not quite right.  You're missing the first split/reverse.  Notice that the teams from the top half of the bracket in the A-rounds should play the teams from the bottom half of the bracket in the B-rounds.

I'll try to post tomorrow explaining the logic exactly, but if you read the code I posted it explains exactly how to come up with the seedings.