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
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 (http://www.idleloop.com/matchmaker/) 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]

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"?

[alectronic]

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.

[engunneer]

Keep in mind that there are some inputs when the program is run, and (not applicable to your case) any surrogate matches don't count against the partner/opponent duplication score.

[katkimball]

Yes I mean played on the same alliance as

[Caleb Sykes]

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]

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. :confused:

[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.

[MrTechCenter]

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.

I used the algorithm to generate a match schedule for an event with just 22 teams at it. Worked fine in making sure that teams did not get the same alliance partners/opponents too many times, and that was to my surprise, I expected that teams would have to play with each other several times because of how few teams there were, but this was not really the case. However, some teams had to play back-to-back matches.

[GaryVoshol]

If the minimum match separation parameter is set too high, then there will be more repeats of teams seeing each other in matches. For example, in that 36-team event, if minimum match separation is set to 6, the exact same robots will be forced to play in matches 1, 7, 13, 19, etc. (I wouldn't be surprised if the software has limits that wouldn't allow you to enter too high a value in the parameter.) As in the example of the 22-team event, to get more mix in the matches, the minimum had to be set low and allow back-to-back matches.

[rich2202]

One adjustment that appears to have been made: If a Bot has not passed inspection, it is given as late a 1st match as possible. This gives it as much time as possible to pass inspection prior to its first mach. They also appeared to keep those bots 1st match separated (don't put all the bots in the same last 1st match).

[BrendanB]

Our team had to play against team 3479 three times at UNH and against team 1073 three times at NU.

[RufflesRidge]

One adjustment that appears to have been made: If a Bot has not passed inspection, it is given as late a 1st match as possible. This gives it as much time as possible to pass inspection prior to its first mach. They also appeared to keep those bots 1st match separated (don't put all the bots in the same last 1st match).

Neither of these are parameters that can be entered when generating the schedule. This was either a coincidence or the FTA regenerated the schedule until this occurred.

[rich2202]

Neither of these are parameters that can be entered when generating the schedule. This was either a coincidence or the FTA regenerated the schedule until this occurred.

Does it automatically feed the teams to the FMS? If not, I was thinking they just substituted team numbers before publishing the list.

[Gamer930]

Does it automatically feed the teams to the FMS? If not, I was thinking they just substituted team numbers before publishing the list.
Rich,
I'm thinking that you are talking about Wisconsin Regional 2014 schedule for qualifications. I can tell you 100% that this was just coincidence that the 3? teams that didn't pass inspection yet were in match 7? and 8?. I was the person that created the schedule for the regional using the FMS software. The FMS software is no way connected to Inspection. The final schedule with team numbers was generated ONCE.

It wasn't until 100 copies were printed and schedule posted on usfirst.org that this was noticed by the Lead Robot Inspector.

[rich2202]

Yes, it was the WI Regional. Interesting coincidence. I noticed because I was a RI assigned to one of the 3 teams to get them passed before their first match.

Maybe it could be a criteria in the future. I don't see the harm in giving the teams some extra time.

[RunawayEngineer]

Neither of these are parameters that can be entered when generating the schedule. This was either a coincidence or the FTA regenerated the schedule until this occurred.

I don't know if this is standard practice, but I know of one regional that will regenerate the schedule until the first match consists of 6 robots that have already passed inspection.

[MikeE]

Our team had to play against team 3479 three times at UNH and against team 1073 three times at NU.

With 40 teams at NEU and 36 at UNH a "perfect" district schedule would have no teams seeing repeated partners (I believe this was the case in all NE districts events), no repeated opponents at NEU and only a single repeated opponent at UNH. However the current algorithm is designed to run in a couple of minutes on the FMS server and is very unlikely to find a globally optimal solution.
For traditional Regionals this isn't much of an problem because the ratio of matches to teams is large enough that local optima are usually close to the global optimum.
There is just less flexibility when you only have 3 times as many teams as matches.

[AGPapa]

With 40 teams at NEU and 36 at UNH a "perfect" district schedule would have no teams seeing repeated partners (I believe this was the case in all NE districts events), no repeated opponents at NEU and only a single repeated opponent at UNH. However the current algorithm is designed to run in a couple of minutes on the FMS server and is very unlikely to find a globally optimal solution.


Could a global optimum be found for each event beforehand with filler teams (i.e. teams #1-40) and have the FMS randomly assign real teams to each filler one?

[MikeE]

Could a global optimum be found for each event beforehand with filler teams (i.e. teams #1-40) and have the FMS randomly assign real teams to each filler one?

You've just described my offseason project.
It's feasible for district events since the parameter space is much smaller (always 12 matches, 35-40 teams) so only a handful of solutions are needed.

[Ether]

I posted an analysis of Weeks 1 thru 6 Event schedules.

There appears to be some room for improvement in the scheduling algorithm

http://www.chiefdelphi.com/media/papers/2971

[Conor Ryan]

Is there a tool that exists that can quickly tell you the quality of the schedule generated?

In the past year FMS has separated out the Scheduling from the Match Maker process. I've spoken to at least a few people about the possibility of having a server populated with only the best match randomizations ahead of time, and then having a tool randomly select a schedule to use. I haven't seen it yet, but I'm sure off-seasons will make use of it.

[MikeE]

I posted an analysis of Weeks 1 thru 6 Event schedules.

There appears to be some room for improvement in the scheduling algorithm

http://www.chiefdelphi.com/media/papers/2971




Thanks Ether.
The other metric that's useful is the number of times a team appears in either role (with or against), i.e. the sum of your two event matrices. Incidentally all these stats are generated as part of the schedule tool and available in the FMS.

I'd also like to point out that the current schedule software is a really good solution to the general problem, and a massive improvement on what went before!
But it's the nature of us engineers to always look for improvement.
I'm not sure if that means we're natural optimist or pessimists.

[coalhot]

Is there a tool that exists that can quickly tell you the quality of the schedule generated?

http://www.idleloop.com/matchmaker/
There's a piece of software in the Matchmaker bundle called "Matchrater", it can tell the quality of a schedule.

[Ken Streeter]

Our team had to play against team 3479 three times at UNH and against team 1073 three times at NU.

I think it should definitely be possible to have the FMS use an optimized schedule at the sizes for typical district events such that a team never has to play against the same team three times.

For the record, at the Granite State District Event (39 teams, 12 matches per team = 78 matches), we were in a match (either with or against) with every team at the event. We were never allied with the same team twice in qualification matches. We saw most teams once or twice. There were three teams that we saw three times. We were against team 138 three times, and had no matches with them. (Yes, they won all three of those matches! They went undefeated...)

At the Rhode Island District Event (37 teams, 12 matches per team = 74 matches), we were in a match (either with or against) with every team at the event. We were never allied with the same team twice in qualification matches. We saw most teams once or twice. (18 teams once; 12 teams twice; 6 teams three times.) We were against team 2621 three times, and had no matches with them.

I contend that facing the same team three times in an event when over half the teams have only been seen once should not have to happen for any team at the event.

Could a global optimum be found for each event beforehand with filler teams (i.e. teams #1-40) and have the FMS randomly assign real teams to each filler one?

^^^ This. ^^^

Seems like the above would definitely the way to solve this problem. The match schedule could be pre-determined and the "randomizer" need only assign team numbers to slots in the schedule. That randomization would be practically instantaneous on the FMS computer. Since it would be a "pre-determined" schedule, it can be very close to optimum. (i.e. Avoid things like have a pair of teams face one another three times.)

[IceStorm]

It would be nice to see it take into account rookie teams as well. At our event last weekend it paired up 3 rookies against 3 veteran teams. Needless to say it wasn't a very fun match to watch.

[AGPapa]

It would be nice to see it take into account rookie teams as well. At our event last weekend it paired up 3 rookies against 3 veteran teams. Needless to say it wasn't a very fun match to watch.

It's generally bad to classify how good or bad a team is by their age. In 2007 FIRST tried to implement something like your suggestion to balance the matches. Each event was broken into the lower third of team numbers, the middle third and the upper third. Each alliance would then be composed of one team from each.

This was the result (http://www.thebluealliance.com/team/11/2007). Team 11 played team 25 in half of their qual matches in New Jersey. The worst problems came when good teams with high numbers (like 1114) attended events. Other teams with similar numbers would always be paired against them and never with them. It was a complete disaster and the algorithm had to be changed for later weeks. Team age is not a good predictor of robot quality.

EDIT: Found an old thread (http://www.chiefdelphi.com/forums/showthread.php?t=55178).

[GaryVoshol]

It would be nice to see it take into account rookie teams as well. At our event last weekend it paired up 3 rookies against 3 veteran teams. Needless to say it wasn't a very fun match to watch.

They tried that once, and it was a miserable failure. The teams were divided into 3 "pools" based on team number, and each alliance got one from A, one from B and one from C. Which meant that you as a rookie team could never be paired with one of the other good rookie teams, but you could be playing against them.

(Incidentally, Team 1114 fell into the "C" pool at the old GLR that year, because there were so many lower-numbered teams.)

The fact is, the age of a team (team number sequence) has very little to do with the effectiveness of a team. We've seen low-numbered teams perform poorly, and rookies come out near the top.

[Travis Hoffman]

I would just like to ensure there is some standard that requires an event's team list to be randomized before being "injected" into the algorithm. Or better yet, the algorithm generates some generic schedule populated by Teams 1-X and then randomly assigns teams from the team list to those Team 1-X spots after the fact.

Ideally, I'd prefer human eyeballs not see anything related to actual team identities until after the ideal schedule is generated and approved, with all desired parameters agreeable to event staff. I do NOT count knowledge of specific team positions within that schedule as a parameter that should concern event staff. That includes any allocation for non-inspected teams. The schedule is supposed to be RANDOM. If a team is dinged RANDOMLY by the fact they failed to understand the urgency of receiving an inspection, such is the way fate works sometimes.

There is also the risk of more insidious schedule adjustments to creep into the current process. "I don't like this schedule because <insert some subconscious aversion related to seeing a schedule with a certain mix of team pairings that enables rationalization of a re-click>". *Clicks mouse again* "Oh that's much better."

This schedule generating process sounds like it contains weak points where much blar can be introduced, if the non-random tendencies of human beings let such things happen.

Humanity is fallible. Whether consciously or otherwise, non-random injection of human preference into the final outcome of a match schedule has likely happened at least once at events spanning the broad expanse of FIRST history. The majority of folks out there would not even consider such a thing, but if there's a simple solution that could prevent the tiny percentage of those who would from adversely impacting the process, as well as prevent any subconscious thoughts of the otherwise pure from leaking their way into the final schedule that is printed and distributed, I think that is a change that needs to be made.

[MikeE]

I would just like to ensure there is some standard that requires an event's team list to be randomized before being "injected" into the algorithm. Or better yet, the algorithm generates some generic schedule populated by Teams 1-X and then randomly assigns teams from the team list to those Team 1-X spots after the fact.


Glad to see Travis arguing for the RNG :)

[IceStorm]

They tried that once, and it was a miserable failure. The teams were divided into 3 "pools" based on team number, and each alliance got one from A, one from B and one from C. Which meant that you as a rookie team could never be paired with one of the other good rookie teams, but you could be playing against them.



(Incidentally, Team 1114 fell into the "C" pool at the old GLR that year, because there were so many lower-numbered teams.)



The fact is, the age of a team (team number sequence) has very little to do with the effectiveness of a team. We've seen low-numbered teams perform poorly, and rookies come out near the top.




Guess I never realized they tried this before. After reading your post I see your point of why it wouldn't work.

[Alan Anderson]

It's generally bad to classify how good or bad a team is by their age. In 2007 FIRST tried to implement something like your suggestion to balance the matches. Each event was broken into the lower third of team numbers, the middle third and the upper third. Each alliance would then be composed of one team from each.

They tried that once, and it was a miserable failure. The teams were divided into 3 "pools" based on team number, and each alliance got one from A, one from B and one from C. Which meant that you as a rookie team could never be paired with one of the other good rookie teams, but you could be playing against them.

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.

[rich2202]

I like the idea of having one set of match combinations for M to N number of teams (where M is the least number of teams at a Regional, and N is the most number of teams). I'm guessing that 30 pre-determined combinations covering 40-70 teams would work.

Then, assign teams that have not passed inspection to the later 1st matches (one red and one blue per match), and randomly assign teams to the rest of the spots.

[Libby K]

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]

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.

[Joe Ross]

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.

I count 4 teams you were with below 2130 and 12 teams above. On the other hand, 4645 was with 12 teams below 2130 and 4 teams above and 193 was with 4 teams below and 12 teams above.

Even with randomization of inputs, someone would get a schedule like that, unless team number was an explicit factor in the scheduler.

[itsjustmrb]

I count 4 teams you were with below 2130 and 12 teams above. On the other hand, 4645 was with 12 teams below 2130 and 4 teams above and 193 was with 4 teams below and 12 teams above.

Even with randomization of inputs, someone would get a schedule like that, unless team number was an explicit factor in the scheduler.

You are correct, there were 4, I missed the last team. I assumed when the teams are dumped in the schedule sequentially in the exact same order for every round, that team number is an explicit factor, but I may be wrong.

[MikeE]

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.

That description describes the initial seeding, which is followed by hundreds of thousands of iterations to find a better schedule.

In fact using the test you suggest (for each match on Curie 2013 how many teams are >2130) the distribution is close to the expected distribution.
Stating it more precisely there is no significant evidence to suggest that the alliance pairings are non-random.

[itsjustmrb]

Stating it more precisely there is no significant evidence to suggest that the alliance pairings are non-random.

I am sorry if you thought I was suggesting that it wasn't random, I only suggested that the teams not be dumped in the schedule sequentially in the exact same order for every round.

[jlmcmchl]

I am sorry if you thought I was suggesting that it wasn't random, I only suggested that the teams not be dumped in the schedule sequentially in the exact same order for every round.

I hate to say it, but applying a random shuffle to something that will already be shuffled randomly (The schedule is a permutation of the list of teams based on an RNG) is equally random. You can't make the outcome better by shuffling teams, because then other teams will see the pattern than currently do. In order to fix the issue, you would need to change the actual algorithm that permutes the list and/or that which scores the permuted list.

[MikeE]

I am sorry if you thought I was suggesting that it wasn't random, I only suggested that the teams not be dumped in the schedule sequentially in the exact same order for every round.

As Jordan said above, from a process point of view putting teams in a standard order at initial seeding doesn't matter to the final outcome. The order gets permuted literally hundreds of thousands of times during schedule optimization.

My point about Curie is that testing the statistic of high vs low number teams indicates that the algorithm is doing the right thing, or at least shows there's no evidence that it's doing the wrong thing. The experience of your team is completely expected.

[Joe Ross]

It should be noted that in 2008, the schedule did not get permuted enough, and there was a correlation between team numbers that was not intentional. See http://www.chiefdelphi.com/forums/showthread.php?t=66983 and http://www.chiefdelphi.com/forums/showthread.php?t=67108