**FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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!

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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?

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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:

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)
Here is Tom's algorithm at best, default match delta
Here is Tom's algorithm at best, with 6 minimum match delta, same as Jim's algorithm produced
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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Actual Waterloo 2007 Schedule Data

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

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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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.

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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

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.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Mark,

Are you implying that FIRST staff and the GDC are searching for an algorithm, or that they have chosen this algorithm from among a list of candidates solicited earlier?

If there was a solicitation, I'm surprised that I missed it.

If there is going to be a solictation, can you tell us when?

If there isn't going to be a solicitation, I'm a bit disappointed.

About this algorithm, some quick questions are listed below. If the answer to some of them is "Read the description at ___"; that answer won't hurt my feelings. I think the answers to some of these questions might turn up points that should become part of a match scheduling algorithm's requirements; and that the others might turn up points that should constrain the implementation of those scheduling requirements.

1) Does it allow one to start with a partial schedule and then compute only the rest of the schedule?

2) Does it allow users to create a schedule and then submit it to the algorithm (as input data) for initial or further annealing?

3) Does it allow users to request that each team have at least one long break (perhaps at a user selected time) (for things like giving a team a chance to have a chat with the judges)?

4a) Does it currently anticipate matches in which only 2 teams comprise an alliance, or in which more than 3 teams ally?

4b) In a long shot I'll ask if it anticipates matches comprised of more than 2 alliances?

5a) Are the results deterministic (same input always yields the same outputs)?

5b) If the results are deterministic, unless one wants to do some of the iterative activites I mentioned in questions #1 and #2, why pass out the results of this work as a black-box algorithm? Instead just run it for a large-enough number of matches (25 or so) for each possible number of teams from 6 to N (N would be 100 or so); and then just publish the resulting schedules. Those schedules can be analyzed by people and the people can adjust them to fix any glitches that survived the annealing.

6) Does the implementation allow us to vary the importance of each of the five constraints you listed in your request?

7a) Does the algorithm search forever (until a user spec'ed time limit is reached) for a globally optimal schedule, and in that search recognize when it finds a globally optimal one? If we run it for a long time do we get a better answer?

7b) When searching for an optimal schedule, if the algorithm gets stuck on a locally optimal one, does it recognize that situation and then tunnel over to some new part of the search space to look for the globally optimal one?

8) During the annealing, when evaluating whether a match should be changed, are the five criteria you listed applied in a sequence of decisions or are they the basis for a metric (aX + bY+ cZ +... = evaluation) that is compared to a threshold or is compared to the other matches' evaluations?

9) Does the algorithm insure that when teams face repeat opponents (let's say that everyone has faced everyone else already, and teams have to start facing repeat opponents), does it ensure that the team is not facing the same alliance in which it encountered those opponents the first time around? What about avoiding making a team face alliances that contain pairs of teams that were paired when the team faced them in an earlier match?

MM and I started on some similar algorithmic work earlier this year (http://www.chiefdelphi.com/forums/sh...4&postcount=42) (http://www.chiefdelphi.com/forums/sh...7&postcount=40)
(http://www.chiefdelphi.com/forums/sh...9&postcount=43) and the constraints I set for myself are listed below (I have some preliminary results for two algorithms for 2-team FTC alliances). I think that the constraints net out to be identical (or nearly so) to the five constraints you set out above; but some implementation differences might show up in the resulting schedules. That is one reason why I asked question 8 above.

Near term

• Number of teams is an integer from 8 to 32,
• Teams compete in alliance vs alliance matches
• Each alliance consists of two teams.

Want to conduct M matches in which

• No team is ever allied with the same team more than once (until after is has allied with all teams at least once)
• No team ever faces the same opposing alliance more than once (unitl after it has faced all teams at least once)
• Minimize the number of times each team is on the field with any other team (until it has been on the field with all teams once)
• Each team sees each other team on the field (as an ally or opponent) at least once (if enough matches are played)
• Maximize the minimum number of matches between any/all single team's consecutive appearances on the field.
• All teams play the same minimum number of matches.
• No team plays more than one match more than any other team.

Longer term

• Number of teams is an integer from 8 to 64
• Each alliance consists of 3 teams
• Otherwise no change from near-term constraints.

Blake
PS: I'm jealous :) of the folks who put together the simulated annealing, that is one of the many fun/hobby projects I have taken a bite out of in the past, but have not finished. I want to write my own routine that will rearrange graphs of connected nodes in order to minimize the greatest distance between any two connected nodes (or perhaps minimize the average of the lengths of the links connecting the nodes, or....) when the graph is projected onto a plane.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

There is another solution to this dilemma for small events: use the minimum match spacing, but set a minimum time between a team's matches and allow the number of rounds to adjust. After all, what the teams are really looking for here is having enough turnaround time between matches. It then becomes a balancing act between number of matches each team plays and the event's pace.

So, teams, would having more time between matches be worth giving up one round of matches at smaller events?

Of course with this scheduling, we'd have to reign in us FTAs and Field Managers - whose natural tendency is to drive the teams and field reset crews with whips cracking, to minimize match turnaround time...

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I'd like to echo (and rephrase) Pete's question for teams: Assuming a fixed limit on time available to run qualifying matches, would you prefer one more match with the potential for one or more short turn-around(s), or one less match without that potential?

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Mark is just the messenger posting the e-mail that FIRST forwarded. Many of these questions and comments would be better directed to the post on the official FIRST forums.

I'll attempt to answer the ones that I know from playing with the program and general knowledge of simulated annealing. In some cases the implementation that was provided doesn't have a particular option, but it seems that it would be trivial to add.

No.

As a small team, having the option to have a longer break where we could guarantee that there are people to talk to the judges would be great. I'm not sure I've ever seen someone suggest this, but I think it is definitely something that FIRST should consider.

It has options for 2 teams per alliance and 3 teams per alliance, but not more alliances.

The exact team numbers in each match are non-deterministic, because by design, simulated annealing uses randomization. It does seem to do a decent job at producing the same final statistics (repeated opponents, time between matches, etc).

No.

It provides 3 different "qualities" which vary in time from a few seconds to a few minutes

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

When given identical inputs, its a pretty good bet that single-threaded computer programs only create different outputs if they purposefully invoke functions with pseudorandom characteristics.

So, I'm guessing that either this code has multiple threads that are racing one another, or that it explicitly includes pseudorandom operations as part of its use of simulated annealing methods. I don't think (however, my recollection could certainly be fuzzy...) that non-deterministic results are inherently a part of simulated annealing.

Regardless, I definitely thank you for the bottom line answer - Given identical inputs, separate invocations of this software will produce results that are likely to differ.

Thanks for that and the other answers!
Blake

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

You may want to check the Wikipedia article that's been mentioned a few times on simulated annealing to better understand what it does. Randomization is a very critical piece of the method. The whole point of the algorithm is that you explore (semi-)random spaces of the solution set because it is impractical to search the full solution space.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

The "results" in this context might mean different things to different people. The actual alliance pairings are almost certain to differ from run to run, but the statistical nature of those pairings seems to be pretty consistent. Those statistics are what the algorithm was designed to produce, and that's the "results" we've been asked to assess.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Yes - But. That approach makes things harder than they need to be. Once a suitable schedule exists for a large number of matches for any/each desired number of teams, you can choose to be done for the rest of eternity.

Just randomize the assignment of actual teams to the hypothetical teams in the approrpiately-sized, precomputed schedule each time an event's staff knows the final team list for the event.

I think doing this would be "best for FIRST" because teams could come to events already knowing the pattern in each pre-computed schedule and could fill in the actual team assignments quickly once the event staff announces them. That would mean that teams could create elegant tools for scouting and related matters, and could use them at events without having to waste time punching a jilliion numbers (the match pairings) into them at the events.

I think doing this would be best for FIRST because it would eliminate the need to be able to execute a program to create match schedules. Instead anyone with a text editor and a printer could produce a fine schedule quickly. A simple, optional, runs-almost-anywhere, Java program could make the process nearly painless, would be more portable than a .net program, and would ice the cake.

Blake

PS: Maybe you were asked to evaluate the statistics of a simulated annealer's outputs; but I don't recall seeing that question posted here. Scheduling approaches exist that are deterministic, and given that I prefer them (for the reasons given above), I hope you can better understand my line of questioning.

PPS: I'm not sure that the current algorithm satisfies the criteria Mark listed. It does minimize and maximize appropriate features of the schedules it produces; but I don't think that we can claim yet that it produces schedules that exhibit the minimum and maximum values of those features (requested in Mark's criteria).

We might be able to come up with a set of deterministic heuristics that do produce true minimum numbers of repeats, etc. MM and I are already reasonably close (but can not guarantee success) for the 2-teams-per-alliance version of the problem.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Dave,

It appears my recollection was rather fuzzy, and at the same time a bit correct.

In general, folks using the term "simulated annealing", almost always are referring to both the metric simulated annealers use to evaluate candidate solutions and the typical pseudo-random searching process used to generate those candidate solutions.

On the other hand, it is only that metric, and not the searching process, that gives the method its name. Using a pseudo-random exploration of the search space is just one way to explore it.

However, by doing the suggested reading I was reminded that using a deterministic heuristic to generate candidate solutions would be a very rare thing to combine with a simulated annealing metric. Thanks.

I think I was wise to insert the "fuzzy recollection" escape hatch into my earlier post. ;)

Blake

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I posted a description of the scheduling problem and the solution Cathy and I developed on our team web site in April:

http://www.issaquahrobotics.org/MatchMaker/

This is the article that describes the general algorithm used:

http://grids.ucs.indiana.edu/courses/xinformatics/Scientific%20American%20Analysis%20Algorithm%20of% 20the%20Gods%20March%201997.htm


Most of the questions have been answered correctly. I'll just answer the ones not already covered.

It doesn't handle that now, but there are only a few bits of code that would need to be adjusted to accommodate more alliances. Are duplicated opponents all the same for accounting purposes, or does it matter which opposing alliance they are on? How should alliance position balancing be generalized?

No, we intentionally used a randomly seeded pseudorandom number generator. Even if we didn't, the results would differ from one OS version to another.

Surprisingly, most of the criteria are orthogonal, that is they have no effect on each other.

The minimum number of matches between each team's successive matches is a fixed rule, no schedule that breaks that rule is even considered.

The minimum number of surrogate teams is just a matter of structuring the match so that only one match at the end has surrogate teams to fill in any odd slots for the last team getting their last match.

The red/blue balancing is done after the schedule is computed by swapping red/blue sides, so it has no effect on the other criteria.

The only criteria that play against each other is avoiding duplicate opponents and avoiding duplicate partners. Slightly extra weight is given to avoiding duplicate partners.

The "quality" setting determines a number of randomly generated schedules that will be considered, 100,000; 750,000; or 5,000,000. The program runs for however long that takes, so the running time will vary according to the speed of the computer, but the quality of the results will not be afffected by the machine.

The algorithm can get out of a local minimum. The Scientic American article explains how that works.

There is a scoring function that rates the duplication criteria; that's used to evaluate the schedules.

No specific consideration is given to that, but the randomness of the algorithm should make it pretty unlikely for any team to see the same alliance multiple times. For the data sets I've looked at, there's so little partner duplication that full duplicate alliances just don't happen. If there are cases where that happens, I'd like to see an example.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

It's actually not a .Net program. It's written in very portable C. The download includes both Windows and Mac OS X versions. It would be easy to recompile it for any platform that supports an ANSI C compiler.

I couldn't figure out a way to get the latest version of Visual Studio to produce an executable that doesn't require the very latest version of the C runtime libraries. That's a problem with VC, not an inherent dependency of the program.

It's pretty easy to generate the schedule with our program: just give it the list of team numbers in a text file, hit enter, and wait a few seconds or a minute for the schedule to pop out. It you don't like that one, do it again.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I used the program to generate schedules with a variety of parameters... 12 to 144 teams playing 7 to 10 rounds with minimum match separation between 1 and the maximum possible separation. Each of these nearly 6700 schedules was made using the "fair" setting, but only for lack of processing power. I then used a variety of tools to aggregated the data into a spreadsheet.

Interesting trends I noticed:
-The program was able to produce optimal schedules whenever the match separation was at least 5 less than the maximum possible separation. It usually produced optimal schedules when the minimum separation was 4 less then the maximum.
-The program created the worst schedules when team size was a multiple of 6.

I have attached the aggregated raw data spreadsheets. If anyone is interested in the entire data set, contact me with a way to receive a large file, and I'll give it to you.
~Phil

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Interesting analysis. We actually did a similar, but smaller, data set like this when we were testing performance optimizations to make sure that those changes didn't alter the resulting schedules.

It would be interesting to see how much that improves using good or best. If we could divide up the work across several computers, it could be done in a day or two.

If the number of teams is a multiple of 6, and the minimum separation is set to the maximum value, every team plays with the same five teams in every match. No team can move to an earlier match without breaking the rule, and no team can move to a later match without forcing another team to an earlier match. So, the only thing that can be done is swap the alliances around in the each group of six. This would be true of any algorithm given these constraints.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Good point... i just missed the obvious.

~Phil

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

There's one very practical issue when looking to implement scouting tools like this. It's not uncommon to go to an FRC event and have the actual team list differ slightly from the most recently published team list on FIRSTs and regional websites. This is even more true when you attend offseasons. Since 2001 in helping to develop scouting systems for teams (very low tech ones most of the time) we always built in the flexibility to add, delete, or switch teams. I've always found that doing lots of reasearch on teams ahead of time was good, but showing up at the event with a little flexibility built into your system was even better. It would be frustrating to develop an elegant tool, only to have to make changes at the event anyway. My .02

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Rich,

You and I agree.

When I wrote "once the event staff announces them" I meant at the start of the event, not predictions announced before then.

I presumed that once the actual team assignments (to the placeholder IDs that were used to pre-compute the schedule), were entered into the scouting utility, it would then execute some code, or would use Excel's capabilities, or would ... to cook up lists of the matches/teams the scout wants to study.

Blake

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

gotcha...I misread the first time

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

In reply to my "long-shot" question about scheduling matches comprised of more than two alliances, Tom wrote: My answer is "Beats me" :)

I don't have the answers to those questions either.

When/if the subject becomes worthy of serious investigation, maybe we can get some insight from other gaming domains or from game-theory research papers (or from economic theories?).

Blake

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I've just posted an update to the MatchMaker program that Cathy and I wrote which includes an option for scheduling any surrogate matches in a specified round.

http://www.idleloop.com/matchmaker/

As described in the 2008 manual, surrogate matches will be scheduled in the third round instead of in the last round, so this new option implements that strategy.

This is the engine that FIRST will be using this year to schedule matches at the regionals and the championship, so it would be great to get in some testing before the regionals start off. If you do find any problems, please let me know ASAP!

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

So................

How has the new alliance pairing algorithm treated you so far this season?

I still notice some repetition - are regional staffers correctly parameterizing the algorithm to yield optimal results?

http://www.thebluealliance.net/tbatv/team.php?team=48

Personally, I'm rather agitated and puzzled by the fact that 48 has been stuck in Qualification Match #1 at 3 different regionals, regardless of whether we are the lowest numbered team there or not. At Midwest, 33 didn't even play til Match #5, so it's not like all the lowest-numbered teams are stuck in Matches 1-3.

One begins to wonder if this rather annoying fate is intentionally being forced upon us, given the supposedly random nature of this year's algorithm over last year's...... It's a running joke with us to predict, accurately, that we're in Match #1 at every event we attend, and find out later that we are correct.

After last year, where the Algorithm of Death pretty much forced us to be in one of the first three queued matches, it's GETTING OLD. I'd prefer not to be queued up as soon as we get to the venue on Friday, just for ONE TIME. Is that too much to ask? Perhaps in Atlanta we can have a bit of a break? Cuz, ya know, sometimes it's nice to be able to get a breath in and perform functional checks and such without having the event pit announcers breathing down our necks as soon as we walk in. K? thx, bai.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

On a side note: Interestingly enough, my team has never been in the first match of any event in all of my years of FIRST.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

We found at Waterloo regional that the pairing was almost always that you would play WITH a team, and then one match later you would play against that team.

ie. Match X 1075/1114/m v p/q/r, Match Y 1075/188/b v 1114/c/d, Match Z 1075/e/f v 188/g/h

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

The algorithim was very harsh for us. We frequently found ourselves paired with very inexperienced teams and went up against many of the titans of the CT regional (Uberbots, Gaelhawks). It wasn't until our matches on Saturday that we were paired with any really strong teams (love ya Cyberknights), and there was one team we saw three times (once with us, twice against), while many of the 62 teams we never saw, either with or against us.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I wouldn't swear that this is the case, but I definitely noticed this trend in our match schedules. This was probably not an intentional design, but rather a side effect of the constraints on match spacing and opponent diversity. If a team was your partner in one match, then the way to ensure that you both get the same amount of downtime is to put you both together in the next match, but on opposite sides. This seems like a pretty good behavior... it should guarantee that no team gets to play with a whole bunch of good teams without having to face some of them, or vice versa.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Of course, it still hosed us, because 1114's distro block disconnected itself in our match with them, and they demolished us when against us.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I think there's still issues with how the individual regionals are setting things up. At Midwest, we felt the scheduling algorithm did a very poor job (especially since we had to play against 1625 three times in a row). However, the schedule at Boilermaker seemed to have excellent diversity (at the expense of occasionally very short cycle times between matches). I also felt that the diversity of the Boilermaker schedule was responsible for a more accurate Top 8 at the end of qualification matches (completely subjective, of course).

I'd say the algorithm is better when used correctly, but honestly I think a lot of the problems in the past were also due to incorrect use (minimum match spacing set too high). I think that option really needs to be taken out of the control of the local regional.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I have to say that I am very pleased with how the new scheduling algorithm is working out. Through 18 qualifying matches in Portland and Seattle we saw and played with a wide range of partners and opponents and had matches that were reasonably well spaced.

As for starting first at the three regionals that Team 48 has been to so far, it would seem the chances of that happening randomly are about 0.3% Which sounds pretty unlikely.

On the other hand there are other patterns that would have similar significance to teams... always having the first match on Saturday, or always having the first match after lunch... always being scheduled for the last match of the qualifiers, etc. so that means that the chance of a team seeing a significant pattern to their matches across these three regionals increases to maybe a bit over 1%. Considering the number of teams at regionals, it may not be surprising that at least one of them has found a pattern to their matches.

This doesn't mean that 48 shouldn't be asking "is something weird here?" There are certainly grounds for them to ask. It merely means that if the answer comes back as "no", then no one should be too surprised. Luck... good, bad, or just weird (I would consider three Q1 matches good luck, as I like to have as many people as possible see our robot) does create funny patterns sometimes and we humans are very good at assigning significance to those patterns.

Jason

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

You may note that we have LOST each of those Match 1's in which we have played. Good luck, indeed. :D

You want our spot? ;) I'd rather have the extra prep time. To each, his own.

We're used to weird patterns this year, whether we are in control of their creation or not.

For instance, in addition to being in the first match at each event, we've finished as quarterfinalists at all three regionals this season, losing the first match, winning the 2nd, and losing the 3rd. :rolleyes:

We've also won 2 awards at each event, with the UL Industrial Safety Award being the common component.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I might suggest that the weirder co-incidence is Team 48 losing any three specific matches. You guys always put up a solid machine and have a very focussed team.

While I appreciate the desire for more pit time on Friday morning, there are actually 18 teams that have to be queued up before the opening ceremonies, so starting in Q1 doesn't actually reduce the pit time any more than starting in Q2 or Q3. I note that at Pittsburgh there were 36 teams, so fully half of the teams would have been queued prior to the start of the opening ceremonies.

And, to put it bluntly, "yeah, I want your spot". Although we've often had to queue up before opening ceremonies, we've only been in Q1 once as far as I can recall (last year in Portland) and put on a wild show in autonomous and nearly scored... before going on to lose the match. But I can understand... especially if you're working out bugs, how a later start would be appreciated.

Jason

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

For all of 330's years, we have felt really wierd on the rare occasions when we were not in Match 1 or 2. This began long before people started messing with the algorithm. In fact, NOT being in the first match was the only thing we liked about last years's pairings. Sometimes random things are just random, they only look like there is a pattern.

Before the match schedule is locked in, it can be "audited" to see how many different teams each team will play with and against. If there are "too many" repeats, then the algorithm can be run again. But it takes 10 or 15 minutes each run and the Field Management System can't be doing anything else during that time. If you have to run it more than twice, you can forget handing out match schedules at lunch time. In fact, the scorekeeper and FTA can forget lunch altogether.

There is a lot af variability in the performance depending on the constraints. If you have 48 teams and tell it you want 7 matches between times a team plays, then you only have 6 options for opponents and partners. A match schedule set up this way will have a lot of repeat teams. On the other hand, if you set it for 3 matches between times a team plays, then you have more sets of three opponents than you have matches. The algorithm is very sensitive to this and it takes some experimentation to get it right.

At the LA regional the fewest number of unique teams a team faced was 24, the maximum was 27, the average was somewhere between those two. ( The number of unique partners for every team was 18, the maximum except for surrogates, they had 30 oppponents and 20 partners). But we purposely set the minimum time between matches very low. I forget if we used 3 or 4. This guaranteed teams a minimum of 18 minutes between matches. Since a round took 8 matches to complete, the maximum time between matches was 90 minutes. This is typical of our experience under the pre-2007 algorithm. In actual practice I believe the average time between matches was more like 45 minutes, with very few, if any having turnaround times that short or long.

The best thing to do is set the minimum time between matches fairly low and let the algorithm sort out which schedule gives teams the most time between matches. It will probably pick a schedule within 5% of optimal.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I wonder if the time between matches was not entered correctly at CT. Almost all our matches were exactly 1 hour apart. And, I was a little surprised at the lack of variety in the pairings, we were with and then against many of the same teams.

Maybe we should be thankful we weren't against the same teams twice like last year. But, I wouldn't mind going 45 min or 1 hr 30 on occasion, so we could see a wider variety of the competitors on the field.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

As the scorekeeper for the Waterloo Regional, I was pretty happy with the scheduling algorithm considering what a small event it was (30 teams). The seedings at the end of the qualification round really seemed to reflect team quality well.

One thing that I noticed - not sure if it's a negative or not - is that the algorithm seems to optimize the number of other teams each team is paired with, possibly at the expense of optimizing the number of opponent teams. For example, at Waterloo, where each team played 11 qualification matches, each team had 22 different alliance partners (the maximum possible), while having a number of opponents ranging between 20 and 25. So no team was paired together with the same team twice, while having a repeated opponent anywhere between 8 and 13 times.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

I agree that it should be taken out of the control of the local regional. Why even have a new and improved algorithm if they differ greatly from regional to regional. Our first regional had 64 teams with the second being 61 teams. The VCU one was pretty diverse, however, we played with one team, only to play against them in the next match, repeatedly. The Chesapeake one had us playing same teams over and over again. 4 times in 5 consecutive matches is a bit too much.
I still dont understand why we cant play against and with ALL different teams if there are only 8 matches in a field of 60++ teams. If they have to extend play time in order to do this (due to matches not evenly spaced apart), then I think its the lesser of two evils. Why go to a regional with a large no. of teams only to see the same few ones over and over again.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

That's because you need more opponents than partners. In fact with that small a pool, you HAD to have repeat opponents. With 11 matches you needed 22 unique partners and 33 unique opponents to not have a repeat. That is really hard to do with only 29 other robots. Under these circumstances it is understandable that virtually every match had at least one non-unique opponent.

Which would you rather have? Play eleven robots twice or two robots eleven times? Admittedly those are the extremes and the likely result is somewhere in between ie. 6 robots three times and 3 robots twice, but you get the idea...

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

You know whats kinda funny about all this, FTA and the Scoring table can talk live w/ other fields operating that week to ask for help in general. While the FTA don't touch the score table during competition, I'm fairly certain they are trained how to operate the software since they have to sit and make sure the matches generated are correct.

I know our FTA guy sat there w/ a book, laptop and something to pull his hair out. Although unlike my many other FTA friends he actually was running numbers down to the decimal to make sure all was right :). They were working real hard on thursday to get er done and even help up a match or 2 in the process. I don't see why they can't just calculate the schedule and have it run in the back round that way it doesn't delay the match.... anyways

LI's pairing algorithm wasn't too bad... may have a couple of repeats but wasn't noticeable at all. Seemed fairly random in LI.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

The algorithm used in the Hawaii one was pretty good.
We saw an opponent twice only twice during qualifying matches, considering there was only 37 teams here, and both of those teams happened in our last match. Considering the small size and 10 matches, I'd say its pretty random and spread out.
Cool!:p

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Running the scoring system is part of FTA training. Partly so we know how it works if something goes wrong and partly so the Scorer can take a break without shutting down the field.

The schedule generating algorithm makes something like 5 milliion schedules and compares them against each other accoring to various criteria. The processor is pretty well maxed out while this is going on. We wouldn't want it to miss scores because it was too busy doing something else now woud we?

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Is the software/source for the scheduler available? I had read the white paper that purports to be its basis, but am looking for the real thing now.

Thanks,
rnd

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

The software is available in the link here: http://www.chiefdelphi.com/forums/sh...1&postcount=34 but the source is not available.

Re: **FIRST EMAIL**/Updated Alliance Pairing Algorithm
 

Thank you man
you save me
hahaha jkjk:D :D