**FIRST EMAIL**/Updated Alliance Pairing Algorithm

[Mark McLeod]

Greetings Teams:

FIRST staff and Game Design Committee have been working to improve the method used to generate alliances for the 2008 FRC season. We are trying to make sure that the new method will produce alliances that we all will regard as appropriate. We have developed a list of criteria to define the factors that influence the algorithm results. These criteria are:

a. Maximum time (in number of matches) between each match played for all teams
b. Minimum possible number of times a team plays opposite any team
c. Minimum possible number of times a team is allied with any team
d. Minimize the use of surrogates.
e. Even distribution of matches played on Blue and Red Alliance (without sacrificing a, b, c and d)

Below is a link to a discussion thread on the FIRST Forum. There you will find a stand-alone algorithm that can be used to generate alliances. This particular algorithm currently meets the above criteria. We invite you to try out the program and post your feedback in this thread. Where are the holes? What issues can you find? We want to know!

http://forums.usfirst.org/forumdisplay.php?f=442

Additionally, please post comments about generating alliance pairings in general. It is FIRST's intent to produce the best solution for all teams.

Thanks to all, and good luck in 2008!

Go Teams!

[Richard Wallace]

Absence of a criterion based on presumed team strength is a major improvement vs. the 2007 "algorithm of death". I like the criteria that are included. [edit: Is anyone able to download Matt's attachment on the FIRST Forum? The box notation says pending approval, so maybe we can't see it yet?]

[eugenebrooks]

Hopefully, if the algorithm runs directly on team numbers,
the list of team numbers provided is randomly ordered to
deal with any remnant of the original ordering that might
survive the trip through simulated annealing.
In general, one should run the algorithm on indeces and then
randomly assign the indeces to team numbers after the algorithm
is run.

[Bharat Nain]

IT TOOK ME 5.015 SECONDS TO GENERATE A LIST. THAT IS UNACCEPTABLE!!!!!

Just kidding. It looks like a really good and random system but I think I am going to critically analyze this and then we can have a 100 post long debate on it's pro's and con's.

If anyone wants to join in, IM(teknobramha) or email me.

[Raul]

WOW - FIRST is asking our opinion! That is awesome.

Back to the topic - I did not even look at the algorithm. But if it is using Jim's algorithm used at IRI, then I think it is golden.

Raul

[Pat Fairbank]

I'm really glad to see that FIRST is being communicative about this issue; lack of communication was the biggest problem in 2007, IMO. I hope this is part of a new trend of openness when it comes to controversial issues.

Originally Posted by Raul

But if it is using Jim's algorithm used at IRI, then I think it is golden.

From the file:

MatchMaker by Tom and Cathy Saxton
(founding mentors for FRC Team 1318)
(c) 2007, Idle Loop Software Design, LLC
All rights reserved.

Seems like it's not the same one as IRI. Oh well.

[Joe Ross]

Originally Posted by Pat Fairbank

I'm really glad to see that FIRST is being communicative about this issue; lack of communication was the biggest problem in 2007, IMO. I hope this is part of a new trend of openness when it comes to controversial issues.


From the file:

Seems like it's not the same one as IRI. Oh well.

Here's a link to an explanation of Tom's algorithm (assuming he hasn't tweaked it too much) since march.

[Steve W]

If I remember properly, wasn't one of the issues a few years ago the maximum time between matches? Wouldn't having a minimum time between matches allow for better mixing of the teams?

[Joe Ross]

Originally Posted by Raul

Back to the topic - I did not even look at the algorithm. But if it is using Jim's algorithm used at IRI, then I think it is golden.

Using the parameters from IRI, it appears that this algorithm produces similar if not better results.

First, here is the explanation from the Saxton algorithm for the aggregated statistics he collects:

Schedule Statistics
-------------------

          #: number of matches played, a '+' after the number
               indicates one additional round as a surrogate
          d: minimum delta between matches (e.g. '1' means back-to-back)
       part: number of distinct partners followed by most frequent repeat count
        opp: number of distinct opponents followed by most frequent repeat count
       both: number of distinct teams seen as partner or opponent
               followed by most frequent combined repeat count
        r/b: balance between red and blue alliance appearances
               eg, 3b means team appeared as blue 3 times more than as red
 4+ repeats: any teams seen four or more times as partners or opponents

 team   #   d    part    opp    both    r/b   4+ repeats
 ----  --  --   -----   -----   -----   ---   ------------

And here is the results from Jim's algorithm at IRI (I had to guess a few places because of the inadequacies of FIRST's match lists, and I didn't have the original, but it should be very close, and the only difference would be in the deltas)

 best:  8  11 | 16  1 | 24  1 | 40  1 |  0
worst:  9   6 | 16  1 | 24  1 | 35  2 |  8 (2)

Here is Tom's algorithm at best, default match delta

 best:  8  12 | 16  1 | 24  1 | 39  2 |  0
worst:  8  10 | 16  1 | 20  3 | 28  3 |  2 (28)

Here is Tom's algorithm at best, with 6 minimum match delta, same as Jim's algorithm produced

 best:  8  10 | 16  1 | 24  1 | 40  1 |  0
worst:  8   6 | 16  1 | 24  1 | 38  2 |  2 (32)

With the 6 match min delta, Tom's algorithm allows the worst case team to see 3 more total teams then Jim's algorithm, with everything else being similar or the same. It also eliminates the need for any surrogates with the IRI data set and minimizes it for other data sets.

[AdamHeard]

I am very glad to see the open communication on this issue, as well as the elimination of the "tiers".

[Karthik]

I am impressed. Very impressed.

This algorithm blows the 2007 version out of the water. It's not even close. I'm actually giddy right now, because the really exposes what a farce last year's algorithm was. I just ran the 2007 Waterloo Regional schedule through "MatchRater". Here's what I got.

Waterloo 2007 was a 30 team event, with 11 matches. I chose Waterloo, because of the inherent difficulty of minimizing duplication at event so small, with such a large number of matches. Also, I knew exactly what the chose delta was for the event.

Data Format

Schedule Statistics
-------------------
          #: number of matches played, a '+' after the number
               indicates one additional round as a surrogate
          d: minimum delta between matches (e.g. '1' means back-to-back)
       part: number of distinct partners followed by most frequent repeat count
        opp: number of distinct opponents followed by most frequent repeat count
       both: number of distinct teams seen as partner or opponent
               followed by most frequent combined repeat count
        r/b: balance between red and blue alliance appearances
               eg, 3b means team appeared as blue 3 times more than as red
 4+ repeats: any teams seen four or more times as partners or opponents
 team   #   d    part    opp    both    r/b   4+ repeats
 ----  --  --   -----   -----   -----   ---   ------------

Actual Waterloo 2007 Schedule Data

 best: 11   4 | 15  2 | 23  3 | 27  4 |  1
worst: 11   3 | 11  5 | 15  5 | 21  7 |  9 (1)

Now, I just ran the exact parameters we used in Waterloo (delta of 3), through the new algorithm.

Waterloo 2007 Schedule, run through new algorithm

 best: 11   3 | 22  1 | 25  2 | 29  3 |  1
worst: 11   3 | 20  2 | 19  4 | 26  4 |  1 (30)

Hmm, lets see. In the best case we have, 7 more partners, 2 more opponents, and 2 more total teams seen (29 means you play with or against every team at the regional). In addition the most frequent repeat count drops each time by one. In the worst case we have, 9 more partners, 4 more opponents, and 5 more total teams seen. The most frequent repeat count drops drastically as well. There's no comparison. In fact the best case from the 2007 algorithm is somewhat poorer than the worst case from the new algorithm.

My early opinion, is that this new algorithm is a drastic improvement upon what we saw last year. Kudos to the Saxton's for creating this.

[Dave Flowerday]

Originally Posted by Karthik

Kudos to the Saxton's for creating this.

More importantly, I'm glad FIRST is using it, and I'm glad they're making the process more transparent.

I do have a lingering concern, though: every algorithm that's been used for the last several years (to my knowledge) has had the option to set the minimum match spacing. Obviously this is an important parameter, however the value used is often not a good one. Many times the people setting up an event seem to choose a conservative value, especially at smaller regionals (which is where it does the most damage).

Setting the match spacing incorrectly will cause a terrible schedule, no matter what the algorithm. This one is no different, of course. To really use this algorithm effectively, I think FIRST should decide on a match spacing ahead of time, and dictate it to the regionals. Maybe even put it in ranges (something like, 20-30 teams use match spacing 3, 31-40 teams use 4, 41-50 use 5, etc). I generally don't like hard-coding things, but perhaps make the scoring software automatically choose this number as a default and put the option to change it in a hidden menu or something.

To see what I mean, take this new match generation software and plug in 30 teams, 10 rounds, with minimum spacing of 5 (from what I've seen, 5 is a commonly-chosen number for minimum match spacing at many regionals). The resulting schedule is pretty ugly and would still generate a bunch of "the scheduling algorithm sucks!" messages here on CD if it were used at an event. Even 30 teams, 10 rounds, match spacing 4 isn't too great (and would still generate complaints, I'll bet).

[meaubry]

Yeah - for open communication and requesting input. Great idea!

As with most experiments or trials to validate that the program works one way or another. I would like to see an outcome based on more controlled variables vs. less controlled variables.

When evaluating the end result it would be nice to see which variables have the most impact in the outcome.

For instance, the variable controlling minimum number of matches between scheduled matches - when varied from 1 through X, may impact the final outcome more than balance between red and blue or # or teams at the event.

Based on posts already documented here in this thread, it sounds like those that have played with the code believe it to yield better results than last years algorithem.

I like that, alot - but as Dave F. has pointed out, if the event algorithem czar decides to use 5 or 6, instead of 2 or 3, for variable d in the code - at a large sized event vs. a small sized event - will the customer complaints from last year re-surface?

I agree that perhaps, strongly suggested values for those variables that may make the biggest difference in a good quality result - should be considered as an alternative, short of hard coding it into the code.

Mike

[Tom Saxton]

Originally Posted by Joe Ross

Here's a link to an explanation of Tom's algorithm (assuming he hasn't tweaked it too much) since march.

The algorithm is pretty much the same, but Cathy and I made it run about 10 times faster. We also added the red/blue balancing, which just switches alliance positions after the schedule is generated, so it doesn't affect any of the other schedule properties.

Originally Posted by Dave Flowerday

Setting the match spacing incorrectly will cause a terrible schedule, no matter what the algorithm. This one is no different, of course. To really use this algorithm effectively, I think FIRST should decide on a match spacing ahead of time, and dictate it to the regionals. Maybe even put it in ranges (something like, 20-30 teams use match spacing 3, 31-40 teams use 4, 41-50 use 5, etc). I generally don't like hard-coding things, but perhaps make the scoring software automatically choose this number as a default and put the option to change it in a hidden menu or something.

To see what I mean, take this new match generation software and plug in 30 teams, 10 rounds, with minimum spacing of 5 (from what I've seen, 5 is a commonly-chosen number for minimum match spacing at many regionals). The resulting schedule is pretty ugly and would still generate a bunch of "the scheduling algorithm sucks!" messages here on CD if it were used at an event. Even 30 teams, 10 rounds, match spacing 4 isn't too great (and would still generate complaints, I'll bet).

That's a great point. For 30 teams, with six teams per match, the largest gap between matches that can be applied to all teams for every round is 30/6 = 5. Setting the minimum gap to 5 gives the algorithm very little room to work, and produces a poor schedule.

If not specified as an option, the program uses two fewer than the best possible value, or if that value is less than one (i.e., fewer than 18 teams at a regional), it chooses 1. So for 30 teams, the default is 30/6-2 = 3.

We picked this rule because it seemed to give pretty good results across a broad range of regional configurations, but I wouldn't claim we've tested all reasonable cases.

It would be easy to remove the option to set it manually, but that would make it even more important that the default gives good results. We could also allow the option, but enforce a range, for example: teams/6-2 or smaller, with some appropriate minimum.

So, please experiment. If there's a default value, or range, that the FRC community and FIRST think is good enough to make mandatory, we'll be happy to make the change.

[Bharat Nain]

Originally Posted by Dave Flowerday

I do have a lingering concern, though: every algorithm that's been used for the last several years (to my knowledge) has had the option to set the minimum match spacing. Obviously this is an important parameter, however the value used is often not a good one. Many times the people setting up an event seem to choose a conservative value, especially at smaller regionals (which is where it does the most damage).

There are a couple problems with that because teams want time in between their rounds, but as you correctly pointed out, in a small-event, you really have no choice. Maybe the software should suggest the *optimal* round spacing depending on the number of teams participating and the number of matches. Either that or someone from FIRST should be responsible to tell the event organizers how to generate a proper match list. There was open communication between FIRST and the FTA's at event(at least at LI) so they were available if we needed help. I also have a feeling this is one of those problems that might never be *completely* solved, but rather we should make the best what we can.