algorithms for tournament brackets (NCAA, etc.)

Question

I'm trying implement a bracket in my program (using C#/.NET MVC) and I am stuck trying to figure out some algorithm.

For example, I have a bracket like this with 8 entries (A,B,C,D,E,F,G,H)

I'm trying to figure out if there's an algorithmic way to

1. depending on # of entries, find # of games per round

2. depending on # of entries, for a specific game #, what is the corresponding game # in the next round?

For example, in this case, for 8 entries, the example are:

1. for round 1, there are 4 games. Round 2, 2 games. Round 3, 1 game
2. game 2 in round 1 corresponds to game 5 in round 2.

I also thought about storing this info in a table, but it seems overkill since it never changes, but here it is anyway:

Any help will be greatly appreciated!

Cheers,

Dean

Answer 1

using clingo would be a better option for solving this. Alot of people are gonna say that this is a statistics problem but really its a logic problem....

look at this below quickly written up sudo code for clingo...the syntax is horrible and its just a rough example because I dont wanna give away too much to the reader butttt....

Below is a logic puzzle written in Clingo ASP(Answer set programming)

1 % instance
2 motive(harry).
3 motive(sally).
4 guilty(harry).
5
6 % encoding
7 innocent(Suspect) :- motive(Suspect), not guilty(Suspect).

Here is the output for this program.

clingo version 5.6.0 (c0a2cf99)
Reading from stdin
Solving...
Answer: 1
motive(harry) motive(sally) guilty(harry) innocent(sally)
SATISFIABLE

Here is another example:

1 person(jane). person(john). 
2 day(mon). day(tue). day(wed). day(thu). day(fri). 
3 available(jane) :- not on(fri). 
4 available(john) :- not on(mon), not on(wed). 5 meet :- available(X) : person(X). 
6 on(X) : day(X) :- meet. 

% Define the NBA teams
team(hawks).
team(cavaliers).
team(bulls).
team(raptors).
team(wizards).
team(bucks).
team(grizzlies).
team(warriors).
team(rockets).
team(clippers).
team(spurs).
team(trail_blazers).
team(pelicans).
team(mavericks).
team(thunder).
team(jazz).

% Define the brackets
east_1(team(hawks), team(nets)).
east_2(team(cavaliers), team(celtics)).
east_3(team(bulls), team(bucks)).
east_4(team(raptors), team(wizards)).
west_1(team(warriors), team(pelicans)).
west_2(team(grizzlies), team(trail_blazers)).
west_3(team(clippers), team(spurs)).
west_4(team(rockets), team(mavericks)).
east_semis_1(team(hawks), team(wizards)).
east_semis_2(team(cavaliers), team(bulls)).
west_semis_1(team(warriors), team(grizzlies)).
west_semis_2(team(clippers), team(rockets)).
east_finals(team(cavaliers), team(hawks)).
west_finals(team(warriors), team(rockets)).
finals(team(warriors), team(cavaliers)).

% Define the winning team as a decision variable
1 { winner(T) : team(T) } 1.

% Define the constraints for the brackets
:- winner(T), east_1(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_2(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_3(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_4(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_1(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_2(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_3(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_4(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_semis_1(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_semis_2(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_semis_1(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_semis_2(T1, T2), not winner(T1), not winner(T2).
:- winner(T), east_finals(T1, T2), not winner(T1), not winner(T2).
:- winner(T), west_finals(T1, T2), not winner(T1), not winner(T2).

% Define the objective function to maximize the number of correctly guessed teams
#maximize { 1, T : team(T), west_1(T, T1), winner(T1) ; 1, T : team(T), west_2(T, T1), winner(T1) ; 1, T : team(T), west_3(T, T1), winner(T1) ; 1, T : team(T), west_4(T, T1), winner(T1) ; 1, T : team(T), east_semis_1(T, T1), winner(T1) ; 1, T : team(T), east_semis_2(T, T1), winner(T1) ; 1, T : team(T), west_semis_1(T, T1), winner(T1) ; 1, T : team(T), west_semis_2(T, T1), winner(T1) ; 1, T : team(T), east_finals(T, T1), winner(T1) ; 1, T : team(T), west_finals(T, T1), winner(T1) ; 1, T : team(T), finals(T, T1), winner(T1) }.

#show winner/ 1.

Answer 2

Quoting @Yuck who answered the first question perfectly.

C# code for the first part of your question:

// N = Initial Team Count
// R = Zero-Based Round #
// Games = (N / (2 ^ R)) / 2
public double GamesPerRound(int totalTeams, int currentRound) {
    var result = (totalTeams / Math.Pow(2, currentRound)) / 2;

    // Happens if you exceed the maximum possible rounds given number of teams
    if (result < 1.0F) throw new InvalidOperationException();

    return result;
}

Moving on to the second question:

//G = current game.
//T = total teams
//Next round game = (T / 2) + RoundedUp(G / 2)
//i. e.: G = 2, T = 8
       //Next round game = (8 / 2) + RoundedUp(2 / 2) = 5
public int NextGame(int totalTeams, int currentGame) {
    return (totalTeams / 2) + (int)Math.Ceiling((double)currentGame / 2);
}

Answer 3

Consider renumbering the games (you can always renumber them back afterwards)

if the final is 1 semis are 2,3 the problem is then has well-published solutions: ahnentafel (German for ancestor table) has been used for a long time by genealogists - http://en.wikipedia.org/wiki/Ahnentafel

one interesting part of this is the binary notation of the game # gives a lot of information as to the structure of the tournament and where in the tree the match is.

Also note that as every match knocks out 1 competitor, for n competitors there will be n-1 matches

Answer 4

I actually worked this out myself fairly recently and stumbled on (that is, I worked it out, but it has probably been discovered before) a neat recursive solution.

You start with your list of players, in a list that is sorted in seed order. This will be important later.

The overall algorithm consists of splitting the list of players into two and then creating two sub-tournaments. The winners of the two sub-tournaments will end up the grand final of the overall tournament.

Required Objects

• Player
  • Name
  • Seed
• Match
  • Home Player
  • Away Player
  • Next Match (pointer to the Match the winner goes to)

Splitting the Lists

Most tournaments put the top seeded player against the bottom seeded player in round one. In order to do this I used the following algorithm, but you could just put the first n / 2 players in one list and the rest in the other list to create a tournament where seeds 1 and 2 play off in round one (and seed 3 plays 4, 5 plays 6 etc).

I'll note here that the neat thing about having top seed play bottom seed is that with this algorithm if you don't have a power of two number of players, the top seed(s) will get a bye in the early rounds.

1. Take the first player and put them in the "left" list
2. Take the next two players (or the last player) and put them in the "right" list
3. Take the next two player and put them in the "left" list
4. Repeat from step 2 until there are no more players.

Of course, if there are only two players in the list you simply create a match between them and return.

Building the Tournament

So you start out with a list of say, 64 players. You split it into two lists of 32 players and recursively create two sub tournaments. The methods that you call recursively should return the Matches that represent the sub-tournament's grand final match (the semi-final of your overall tournament). You can then create a match to be the grand final of your overall tournament and set the nextMatch of the semi final matches to be this grand final.

Things to Consider

• You'll need to break out of recursing if there are only two players in the list that's passed in.
• If your split gives you a list of one, shouldn't recurse with it. Just create a sub-tournament with the other list (it should only have two players so will return with a match immediately), set the home team to be the single player and the nextMatch of the sub-tournament.
• If you want to be able to keep track of rounds, you'll need to pass a recursion depth integer - increment it when you create a sub-tournament.

Hope this helps, let me know if you need any clarification :)

Answer 5

C# code for the first part of your question:

// N = Initial Team Count
// R = Zero-Based Round #
// Games = (N / (2 ^ R)) / 2
public double GamesPerRound(int totalTeams, int currentRound) {
    var result = (totalTeams / Math.Pow(2, currentRound)) / 2;

    // Happens if you exceed the maximum possible rounds given number of teams
    if (result < 1.0F) throw new InvalidOperationException();

    return result;
}

The next step in solving part (2) is to know the minimum game number for a given round. An intuitive way to do that would be through a for loop, but there's probably a better method:

var totalTeams = 8;
var selectedRound = 2;
var firstGame = 1;
// If we start with round 1, this doesn't execute and firstGame remains at 1
for (var currentRound = 1; currentRound < selectedRound; currentRound++) {
    var gamesPerRound = GamesPerRound(totalTeams, currentRound);
    firstGame += gamesPerRound;
}

Answer 6

So basically its a elimination contest.

So just have List.

The algorithm will always put the first and second teams together if the number of teams is even. You then increase the counter by two and repeat.

If the number of teams is odd do pretty much the samething except you randomly select a winner of the "first around" and put it against the odd team.

After the first round you repeat the algorithm the same way.

A+1 C+1 ...

For example, I have a bracket like this with 8 entries (A,B,C,D,E,F,G,H)

You should be able to figure out how to parse this. This seems like a homework question.