Is the qualification match robot randomizer really "random"

[Dillon Compton]

Originally Posted by Rich Kressly

You also need to realize that if you desire to win, you'll have to best the "top tier" anyway. Eight of us on 1712 spent our entire lunch break repairing a claw just for the privelege of going up against the 103 alliance - and I do consider it a privelege.

-Rich

I'm going to hijack this thread for a second to thank Rich and 1712 for giving 1391 the chance to share in that privilege of going up against 103's alliance. I thought 1712, 1391, and 381 put up an excellent fight against a very competitive alliance (even if we did get eliminated in QFs).

I also want to echo that match pairings and distribution have been MUCH better this year than in my previous experience. This algorithm is a huge step forward in generating good, distributed matches.

//Dillon

[coalhot]

Since we all are getting off-topic, ill do too and give a plug to Metal Moose. So good hurdler they could throw it out of the ring (literally). Great 'bot. And 304 had a match against them, and almost lost were it not for a good matchup. Ill look for you guys in the Atlanta vids!!

~Philip

[Knippschild]

I was a scorekeeper for the Philadelphia Regional. I was present when the match schedule was generated (by the lead scorekeeper).

The FMS (the event management software) uses a very complicated algorithm to generate a completely RANDOM schedule. When FMS calculates who should be paired with whom, and who should be pitted against whom, it has no knowledge of the team's "big name"ship nor of that team's standings at other regionals.

The match parings take about 3-5 minutes to generate. Last year's algorithm only took seconds to generate... this one is definitely a lot more random by definition.

Also, once a match is generated, it is impossible for a human to edit the schedule and rearrange the pairings to fit some sort of side agenda.

I assure you, the Philadelphia Regional's schedule was generated once, and that was the official schedule used for the qualifying rounds.

[dlavery]

Originally Posted by Knippschild

The FMS (the event management software) uses a very complicated algorithm to generate a completely RANDOM schedule. When FMS calculates who should be paired with whom, and who should be pitted against whom, it has no knowledge of the team's "big name"ship nor of that team's standings at other regionals.

The match parings take about 3-5 minutes to generate. Last year's algorithm only took seconds to generate... this one is definitely a lot more random by definition.

As previously noted, the match pairings are anything but random. Rather, it is a highly constrained process, with many factors influencing how the pairings are established. As outlined in Section 9.3.2 of The Manual, there is a specific set of criteria that are used by the match pairing algorithm to generate the match list. The match pairings generated by the algorithm are evaluated for a "best fit" against these criteria as the list is generated, and adjusted mid-process if necessary. So, by definition, the resulting list is NOT random. Nor would you ever want it to be random. A truly random list will have a significant probability of having teams playing back-to-back matches, being allied with or opposing the same teams, or having uneven numbers of matches. All of these are situations that we clearly want to avoid.

-dave

[The Lucas]

This year's algorithm is a tremendous improvement over the previous years IMHO. I have read up on it and downloaded it to test(I recommend reading it before posting in this thread). I agree with how it approaches the problems, and love how it is customizable from the command line.

The most important factor in evaluating a schedule, at least in my opinion, is paring uniformity. Here is my grading for the 3 schedules that it generated for my teams:

FLR #365: A Philly #365: C Philly #1495: B

Making broad judgments about the algorithm based only on 3 team schedules at 2 event is flawed because it is a minuscule sample size. However, I think I can provide some analysis. The big problem with 365's Philly schedule is the series of 4 matches (in a row) in which we were with/against 357 (1 with, 2 against). 486 was also involved in back to back matches in this series in a home and home aspect (with one match against the next). This series (or cycle) suggests to me that the algorithm was having trouble maintaining maintaining paring uniformity around the minimum match separation constraint.

I think the default minimum match separation was higher than optimal for Philly. In the 3 schedules, the lowest match separation was 4 at FLR and 5 at Philly so I guess that was the minimum. My guess is that minimum match separation is set to

# of teams / 6 (round down) - 2

since FLR had 40 teams and Philly had 44 (42 would yield exactly 5).

I would be willing to sacrifice some match separation for better match uniformity. At events the size of FLR and Philly, I personally would be willing to go for a minimum match separation of 3. The software already gives the scorekeepers the option to specify a minimum match separation (although I don't think many scorekeepers do), but I think the way the program computes a default match separation needs some tuning for the next revision (even it is just subtracting 1).

What does everyone else think about the tradeoff between pairing uniformity and minimum match separation?

Originally Posted by Knippschild

I was a scorekeeper for the Philadelphia Regional. I was present when the match schedule was generated (by the lead scorekeeper).

The FMS (the event management software) uses a very complicated algorithm to generate a completely RANDOM schedule. When FMS calculates who should be paired with whom, and who should be pitted against whom, it has no knowledge of the team's "big name"ship nor of that team's standings at other regionals.

Since volunteers from both 357 and 365 were present when a schedule that called for them to face each other 3 times was generated, I think we can all lay the "algorithm paired big names theory" to rest (not that anyone has been talking about that lately)

[Tom Saxton]

Cathy and I have just released a new version of MatchMaker, the schedule generation program, to FIRST. This new version includes several changes to avoid the clumping effect first reported on this thread.

The clumping was caused mostly by setting the minimum gap between matches too high, which was mostly caused by MatchMaker picking a default that was too large for larger tournaments. To a lesser extent, the way the algorithm was seeded contributed to this problem.

The changes are:

1. MatchMaker now limits the values specified for the minimum match separation so that values that will yield poor schedules will not be allowed.

2. The default chosen when MMS is not specified on the command line is improved, especially for larger tournaments.

3. The starting schedule that is used to seed the match generation algorithm is now randomized both to reduce clumping and also to mix teams up to improve fairness even in situations where constraints on the schedule force some amount of clumping.

4. MatchMaker has a new command line option, -x, which will cause it to just print out the lowest and highest allowed value for MMS, which may be used by the scorekeeper interface to show the range of allowed values.

If you want to give it a whirl, you can get a copy of the build from the MatchMaker download page:

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

There is also a white paper on the same site that describes the algorithm used.

Please let me know by direct message if you find any issues with this release.

[Seth Mallory]

Tom,

I want to thank you and Cathy for your efforts. The improvements in 2008 over 2007 were impressive. I for one was satisfied with that system. You must have spent a lot of time to engineer this new system. Thank you

Seth

[coalhot]

Hey,
I was very tied up during the last few weeks, but i have to say (from seeing it work) good job!!!! It works to perfection. Couldn't be happier!

(now i have to find a way to remotely use the randomizer to our advantage )

Again, thanks!!!

--Philip

[Elgin Clock]

In doing some research with the "randomizer" this year to improve our scouting techniques, & while I agree with the rest of the folks here that 2009's version is VASTLY improved over previous years, I only have one suggestion to add to the "randomizer" for future years.

With this paper I generated for the NJ Regional: ( http://www.chiefdelphi.com/media/papers/2224 & testing the match list in NYC which I didn't release a paper for) I found that the placement of teams during qualification matches in the alliance stations were not equal.

For instance, one team could play a total of 8 matches, of which 4 of those would be in one Alliance Station spot (As shown in that paper, Team 103 being in spot Blue 3 a total of 4 times for example).

I'm sure this could be an easy fix or addition to the algorithm if it was approved.

I know, speaking from an operators perspective, it's nice to bounce around your placement on the field rather than always stand in the same spot & have the same view on either red or blue side of the field.

[Jared Russell]

With 41 regional competitions, it's going to happen that sometimes the best bots end up with and against each other consistently. The schedule generator takes a lot of factors into consideration, but robot ability is most definitely not one of them.

But yes, this year in Philadelphia it seemed that there was not a lot of parity in the schedule. The proof is in the pudding: the better robot were selected for the finals, including some with poor qualification records because of who they had to play against. Yet several top 20 seeds missed the playoffs altogether.

The scheduler doesn't have to be "rigged" in order to generate a match list without robot parity.

[Tom Saxton]

Originally Posted by Elgin Clock

With this paper I generated for the NJ Regional: ( http://www.chiefdelphi.com/media/papers/2224 ) I found that the placement of teams during qualification matches in the alliance stations were not equal.

The algorithm does try to balance each team's appearance on the red and blue alliances, but doesn't attempt to balance positions within each alliance.

The red/blue balancing was added because some event arenas are asymmetric where it's better to view the match from one end or the other, so it's a pain if your team is always playing from the less desirable end. The schedules generated before FIRST asked for that (before the 2008 season) were *much* more imbalanced red/blue than what it does now.

[GaryVoshol]

In five weeks of Michigan Districts, I have not noticed any clumping problems. This is especially significant given that there are 40 teams playing 12 matches each; obviously many see each other more than once. But that doesn't take away the perception - I heard of one complaint that they had to play with "that rookie team" (said disparagingly) 3 times. I hadn't noticed - and sure enough, a check of the schedule showed only one such pairing.

The only downfall with that size of events is the minimum match spacing has to be set to 3 - meaning sometimes a team barely has time to return to the pits before they are being requeued. But even that doesn't "clump" - if a team has a 3 or 4 game separation, likely there will be 11 or more games before their next match.

Good job, Tom.

[martin417]

I believe that the algorithm is written as fairly as can be achieved, given the limited number of matches teams play. However, I did see some oddities that caught my attention. The most unusual was one team that had a drive-train problem on arrival, and missed their first 5 matches (I saw many people from many teams lending a hand to get them up and running, FIRST at its best). They did send a human player for each match, and had very good alliance partners, so they were highly ranked, even though they hadn't had a robot on the field.

[Elgin Clock]

Originally Posted by Tom Saxton

The algorithm does try to balance each team's appearance on the red and blue alliances, but doesn't attempt to balance positions within each alliance.

Oh, I definitely understand that.
All I ask is that for next year, (if possible) for it to be stepped up just a bit to include randomization within the red or blue as well a bit more.
What fun is advancing the program, if it will stay the same every year?
I guess I'm just an Engineer by nature (but not degree yet) and always want to see something improved. lol It's a curse... & a blessing all in one.
The jump from last year to this year's alliance pairing system was progress by leaps & bounds no doubt, and I congratulate you on that!!!
For next year, I only have that one request if possible with that said.
Just a suggestion!

Originally Posted by Tom Saxton

The red/blue balancing was added because some event arenas are asymmetric where it's better to view the match from one end or the other, so it's a pain if your team is always playing from the less desirable end. The schedules generated before FIRST asked for that (before the 2008 season) were *much* more imbalanced red/blue than what it does now.

I think the regional I went to this past weekend (CT Regional) is a perfect example of one of those where teams can play on the "less desirable end" as you noted.

The main screen which shows the field (and thus real time scoring, & video) is behind the Red Alliance station, so I can see where that request came from - Blue has an advantage in that scenario by being able to see the HUGE screen very nicely with a quick glace up forward, while the Red Alliance has a rather tiny LCD screen to glance over at in retrospect, or has to look behind the or rely on their coach to look behind them.

I guess it's true, every simple request has a good reason behind it!