Computer generated initial alliances

[katkimball]

What are the criteria the 2014 FRC algorithm uses to generate the initial team alliances? Is it different District vs Regional events? Does it factor in a District win by aligning a team with a district win with lower ranked teams for the second play? I can only find data on the web for the 2008 algorithm and that must have changed as we were against the same team three times in only 12 rounds so “Minimum possible number of times a team plays opposite any team” doesn’t seem to apply? Thank you for any assistance in finding this information.

[Steven Donow]

Per section 5.3.2 of the manual:

The Field Management System (FMS) assigns each Team two (2) ALLIANCE partners for each Qualification MATCH using a predefined algorithm. The algorithm employs the following criteria, listed in order of priority:

Maximize time between each MATCH played for all Teams
Minimize the number of times a Team plays opposite any Team
Minimize the number of times a Team is allied with any Team
Minimize the use of SURROGATES
Provide even distribution of MATCHES played on Blue and Red ALLIANCE

All Teams are assigned the same number of Qualification MATCHES, unless the number of Teams multiplied by number of MATCHES is not divisible by six. In this case, the FMS randomly selects some Teams to play an extra MATCH. For the purpose of seeding calculations, those Teams are designated as SURROGATES for the extra MATCH. If a Team plays a MATCH as a SURROGATE, it is indicated on the MATCH schedule, it is always their third Qualification MATCH, and the outcome of the MATCH has no affect on the Team’s ranking criteria.

A team's perceived skill/history has no impact on the schedule.

[Chris_Ely]

Game Manual, Section 5

Originally Posted by 5.3.2 MATCH Assignment

The Field Management System (FMS) assigns each Team two (2) ALLIANCE partners for each Qualification MATCH using a predefined algorithm. The algorithm employs the following criteria, listed in order of priority:

Maximize time between each MATCH played for all Teams
Minimize the number of times a Team plays opposite any Team
Minimize the number of times a Team is allied with any Team
Minimize the use of SURROGATES
Provide even distribution of MATCHES played on Blue and Red ALLIANCE

All Teams are assigned the same number of Qualification MATCHES, unless the number of Teams multiplied by number of MATCHES is not divisible by six. In this case, the FMS randomly selects some Teams to play an extra MATCH. For the purpose of seeding calculations, those Teams are designated as SURROGATES for the extra MATCH. If a Team plays a MATCH as a SURROGATE, it is indicated on the MATCH schedule, it is always their third Qualification MATCH, and the outcome of the MATCH has no affect on the Team’s ranking criteria.

[Schnabel]

Check this out.

[katkimball]

Thank you Shnabel FRC #0314 for the link that answers so many questions!

I was sure there was a different algorithm for district events as we had 36 teams and 12 matches so no surrogates and yet played against the same team 3 times and never played with at least 4 teams.

I now see there are other factors that figure in to the equation.

[Caleb Sykes]

Originally Posted by katkimball

Thank you Shnabel FRC #0314 for the link that answers so many questions!

I was sure there was a different algorithm for district events as we had 36 teams and 12 matches so no surrogates and yet played against the same team 3 times and never played with at least 4 teams.

I now see there are other factors that figure in to the equation.

emphasis mine

does "played with" as used here mean "played on the same alliance as" or "played in the same match as"?

[katkimball]

Yes I mean played on the same alliance as

[Caleb Sykes]

Originally Posted by katkimball

Yes I mean played on the same alliance as

In that case, I am not surprised in the slightest. Since you are only partnered with 2 robots/match, and you play 12 matches, you only play on the same alliance with a maximum of 24 robots at a 12-match event. Since there were 35 teams at your event that weren't you, this means that you will not play with at least 11 of them in quals, no matter what the algorithm is.

[Chris is me]

I also noticed that 2791 played with / against the same teams a ton of times at Finger Lakes. Events that large normally have less repeats. Other teams had a lot of repeats as well.

We played with / against 341 three times (1/2). We played twice against 1126. We also played 1 with and 1 against teams 20, 1592, 174, 1450, 1551, and 3173. Not that upset about it or anything, just thought there was a bit less emphasis on playing unique teams this year than prior years.

[Electronica1]

Originally Posted by Chris is me

I also noticed that 2791 played with / against the same teams a ton of times at Finger Lakes. Events that large normally have less repeats. Other teams had a lot of repeats as well.

My team also noticed more with/against repeats than usual at our events this year. Even at the VA region which is a 64 team event. It was kind of odd.

[MikeE]

The scheduling algorithm focuses on minimising repeated alliance partners while also trying to limit the number of repeated opponents and the number of times you see the same teams in either role.
While the algorithm is great for standard regional events (50+ teams and around 10 matches) and gives a reasonable schedule for all events, it struggles a little when the number of teams is between 2 & 3 times the number of matches per team.

[Libby K]

Originally Posted by Chris is me

I also noticed that 2791 played with / against the same teams a ton of times at Finger Lakes. Events that large normally have less repeats. Other teams had a lot of repeats as well.

We played with / against 341 three times (1/2). We played twice against 1126. We also played 1 with and 1 against teams 20, 1592, 174, 1450, 1551, and 3173. Not that upset about it or anything, just thought there was a bit less emphasis on playing unique teams this year than prior years.

1923 had this happen at Lenape, but not Mt. Olive. It was definitely odd.

We saw 2590, 341, and someone else (i'm burned out and my brain isn't working) at least three times, whether they were on our side of the glass or across the field. It was unexpected for sure.

[Lil' Lavery]

Originally Posted by Alan Anderson

I don't think FIRST was behind the Alliance Algorithm of Doom. The software developer was told to change it after the first week's matchups were universally recognized as being very bad. It got a teeny bit better, but the underlying method of splitting the teams into three groups based on team number wouldn't go away.

From everything I recall, you're correct. FIRST was not aware that the algorithm functioned that way until it was unveiled. The "pooling" issue persisted throughout the entire season, including championship. It was decidedly worse in week one, and improved as the season progressed. VCU (week 1 in 2007) was easily the worst schedule I've ever seen in FRC history. The teams in the "low number pool" played against the same opponent in the low number pool every single match (ie 116 faced 122 every match). Same for the high number pool teams (1541 faced 1598 every match). The low team's opponent from the middle pool would become their partner in their next match, but the pairing didn't remain constant. It has set the bar for absolutely awful match pairing algorithms.

[itsjustmrb]

From the link provided...

MatchMaker Scheduling Algorithm
By Tom and Cathy Saxton
© 2007-2008, Idle Loop Software Design, LLC
Latest Revision: January 11, 2008 MatchMaker Version: 1.0.2b1

“The algorithm used by FIRST to generate the qualification match schedule at the FIRST Robotics Competitions (FRC) is critical to the success of the regional and championship competitions. This paper discusses the desired properties of the match schedule, and an algorithm that finds near-optimal solutions in a practical time frame.
The algorithm begins by seeding the match schedule with the simplest possible schedule: the teams are dumped in the schedule sequentially in the exact same order for every round. Thereafter, teams are only rearranged within rounds. This guarantees the round uniformity requirement: no schedule that breaks the round uniformity requirement is ever even generated.”


I am not going to get into the debate about whether an older team (lower number) is better or not, but I have noticed the match schedule seems to lump lower number teams together a little more often.(As well as bunch the higher numbers) For example, in the Curie Division last year, there were 50 teams numbered above 2130 and 49 below.
We played 8 matches against 24 teams, 11 of which were numbered over 2130 and 13 were below. Of the 16 alliance partners, 13 were numbered above and only 3 were below.
Maybe the schedule generator should randomize the numbers before the teams are dumped in the schedule instead of sequentially.

[alectronic]

Originally Posted by katkimball

I was sure there was a different algorithm for district events as we had 36 teams and 12 matches so no surrogates and yet played against the same team 3 times and never played with at least 4 teams.

The algorithm is the same for all events, but when there are so few teams and so many matches at districts, the likelihood is simply that you end up playing with/against the same teams more often than a traditional regional. The FTAs at each event review the schedules after generating them, and review the number of times each teams is paired with/against teams and maximize the number of opponents and partners, per the rules quoted previously.