Match Scheduling Algorithm Competition

[JesseK]

What about a feature called 'Titan Match':

• Consenting teams could ask to be versus each other, picking their partners as well.
• It would only be applicable to offseason events, and ethically only if all 6 teams consented.
• Most likely, it'd only be able to happen 1-2 times overall during the event so it didn't throw the rest of the schedule off.
• It would be easy to implement into the stitching algorithm, and would simply eat more processor time in most other algorithms since it's an additional constraint

[gblake]

I certainly wouldn't argue against adding "Titan Matches" to any of the feature lits I have put in other scheduling posts/threads (for the moment I'm being too lazy to go find and copy all of them into this discussion).

One big reason for saying that, is my belief that Jesse's excellent suggestion for developing an open source scheduler is best implemented by developing a "scheduler", not a the-way-we-always-run-FRC-matches scheduler, or a VRC scheduler, or an FLL scheduler, or a league-play scheduler, or an FiM scheduler, or etc.

If the team that implements an open source scheduler is mostly drawn from Chief Delphi participants, they will sometimes have to force themselve to lift their heads up out of the STEM robotics weeds (FIRST and VRC in particular) and look at the project as a scheduling project, not a FIRST (or BotBall, or VRC or ...) task.

The result should be something useful for the STEM Robotics world, and for other uses.

Blake

[Travis Hoffman]

Originally Posted by AdamHeard

Weighting matches based on current years ranking is inherently unfair. You are punishing a team and decreasing their chance of future success based on previous success, and rewarding teams with low success with a higher chance of future success.

In FRC efforts to make it fair should end after registration; Every team has equal opportunity to compete, build, find mentors, fund raise, etc... No competitive boost should be given to under-performing teams. They had just as much of a chance to make amazing happen as the teams that routinely do, don't punish the teams that work hard for that.

Why do performance metrics have to completely dominate the algorithm's decision making process? Why do we all have to view the inclusion of OPR or similar into the algorithm as an attempt to completely balance the competitive scales in each and every match?

Why couldn't we use OPR or some other performance ranking method in the scheduling algorithm as a "sanity check" during the scheduling process to ensure the net strength of an alliance relative to the proposed opposing alliance doesn't skew past some ultra-extreme, ridiculously-impossible to overcome threshold? Matches of this nature are likely to lead to an utter slaughter on the field. I would like to think that the slaughterers would not particularly enjoy such a monumental cakewalk, as it doesn't really challenge them, the slaugterees would definitely not enjoy it, and most importantly, the crowd would find such matchups boring as hell. So why not try to eliminate or minimize these outlying extremes in the schedule without trying to perfectly balance each and every match?

Not only do such matchups as described above happen a lot at events, they sometimes happen to the same team multiple times at an event. When that occurs, such teams begin to feel that they are not getting enough of a positive experience and equal opportunity for success relative to other teams for the money they invest in a competition. That should never happen.

There were people involved with writing earlier FIRST scheduling algorithms that stated overconfidently that certain scheduling goals were impossible to be achieved. People like Jim Zondag and the Saxtons took it upon themselves to prove those people wrong. They sought to create their own algorithm implementations, and they were successful in proving that "impossible" criteria could in fact be successfully implemented into a match scheduling algorithm.

So for all the newly doubtful, I propose there is someone out there who DOES have the ability to create an algorithm that mixes in some reliance on ranking metrics to balance out the match lists, at least enough to avoid frequent "slaughterhouse" matchups that no one really enjoys. I fully support anyone bold enough to take that challenge on and prove to everyone it CAN be done!

[gblake]

Originally Posted by Travis Hoffman

...
So for all the newly doubtful, I propose there is someone out there who DOES have the ability to create an algorithm that mixes in some reliance on ranking metrics to balance out the match lists, at least enough to avoid frequent "slaughterhouse" matchups that no one really enjoys. I fully support anyone bold enough to take that challenge on and prove to everyone it CAN be done!

Once the metric is defined, and prioritized (a task that can become tricky) in the list of metrics to be used, a scheduler is certainly do-able.

If the metric only depends on the 3 teams in a single alliance you can imagine easily pre-computing it for all possible alliances and then it just becomes one more attribute to consider along with all the others (time since last match, etc.). Who cares if there are a zillion possible alliances. Computer CPUs are fast and RAM storage is cheap.

If you need to use all 6 (or 4, or ...) possible teams to compute the metric, things change a bit but it is still do-able.

Blake

[Molten]

I'll completely admit that programming isn't my forte. With that said, please bear with my questions.

Would such an algorithm give the same schedule everytime? or would it vary greatly?
If we made it opensource, would I be able to use this knowledge to best guess my alliances for a given regional?

Next, as for the stacking the deck debate that has came up. Could they use such pre-ranking systems to judge the opposing alliances for a given team and ensure each team has approximately the same difficulty? Completely ignore your own team and alliance and just look at the opposing. Would this lead to the same issues? I wouldn't be opposed to going against an alliance made up of teams 1, 2, and 3 as long as my next match was against teams 5000, 5001, and 5002. That would allow for alliances to vary greatly during individual matches but give a general expected difficulty for the overall regional. Again, is this possible? and if so, would it give the desired results?

Jason

[gblake]

Originally Posted by Molten

I'll completely admit that programming isn't my forte. With that said, please bear with my questions.

Would such an algorithm give the same schedule everytime? or would it vary greatly?
If we made it opensource, would I be able to use this knowledge to best guess my alliances for a given regional?

...

Jason

While I want to say that, in general, most programs will produce the same answer every time they are given the same initial conditions, there are enough exceptions to that rule-of-thumb to make it something you don't want to rely on.

However, generally, whether an algorithm that attempts to use random numbers can be used to get identical answers during separate uses is almost completely up to the programmer who writes the instructions the computer executes.

If the author gives users the ability to kick off an algoithm's (pseudo)random number generator with an initialization value the user controls, and if they weed out a few other sources of possible variation; then users can get repeatable results by using repeatable initial conditions, or they can get unpredicatable (far, far less predictable) results by choosing unpredicatable initial conditions.

Because these and other ways of randomizing the way the schedule is applied to the teams involved, the degree of predictabilty in each match can be placed completely into the hands of the algorithm's users. There is no need to worry that they will be forced into giving anyone any useful knowledge before they want to purposefully release it.

Blake
PS: This is true even if all 2012 FRC matches, for example, were played using a (a set of) fixed schedule(s) published online tomorrow. Knowing that Alliance AQB will face Alliance SRK in the first match of every FRC tournament does you no good on the field if you don't know which of the teams in the tournament will get assigned to each of those letters (A, B, Q, S, R, and K) (that would happen the morning of the event).

But... knowing that AQB will face SRK would be a nice help for scouts. Once they (at the start of the day) matched up the real teams with the fake teams in the well-known "schedule", their scouting software, spreadsheets, etc. would know the complete actual schedule.

Entering the data necessary to correlate the fake and real team IDs means entering (by hand at the event) only a small fraction of the data necessary to describe the dozens of matches in a typical FRC/VRC/FTC tournament.

PPS: Of course, I realize that, pre-publishing a schedule filled with bogus place-holder team IDs, so that scout can simply/easily correlate its entries with the real teams at the start of a tournament, "isn't the way FRC works" ...

[ajd]

Why is this a programming challenge? It seems like creating the specification is the hard part, not the actual coding.

[EricH]

Originally Posted by ajd

Why is this a programming challenge? It seems like creating the specification is the hard part, not the actual coding.

Well...

You have variable numbers of teams.
You have a number of different parameters that the user needs to input. (Match cycle time, number of matches per team, break times--and all of those will vary slightly.)
You have the 7 items in the challenge statement, which will have different weightings.
You need to make it user-friendly.

Your program needs to handle every one of those items, and handle it cleanly and effectively.

That's why it's a programming problem (aside from the standard "Everything's a programming problem" jokes.)

The other thing is that the challenge was a 12-hour time duration, which greatly adds to the challenge.

[gyroscopeRaptor]

IMO, the only restriction for team age should be that rookies change their team color less. I'm speaking from personal experience that changing bumpers can be time-consuming and it would be easier if they changed them less- easier on the team and they would have more time to iron out the kinks in their system.

[Ed Law]

Originally Posted by gyroscopeRaptor

IMO, the only restriction for team age should be that rookies change their team color less. I'm speaking from personal experience that changing bumpers can be time-consuming and it would be easier if they changed them less- easier on the team and they would have more time to iron out the kinks in their system.

Ah bumpers, my favorite topic. Do you know that the rules for bumpers are three and a half pages long? You can easily use up 4 weeks just to design and build bumpers. That was how long it took us last year. Fortunately it was done in parallel with doing the robot.

About changing bumpers, in our rookie year, our bumper would take one person about 5-10 minutes to remove and re-install. Fortunately that was Lunacy and we didn't need to change bumper yet. We only had to do that to pass through a standard 30" wide door. In our second year, we had a better design but it would still take one person 1-2 minutes to change to a different color bumper. Last year, our latest bumper design only takes one person 20-30 seconds to change. WIth 3 people, we can do it easily in 5-10 seconds. We really like the design so we probably will not change it unless FIRST comes up with new bumper rules that are 6 pages long.

[Ed Law]

Sorry I changed the subject. Back to match schedules.

I think it is very important that the algorithm will produce the same answer no matter how many times you run it. The current one that FIRST use does not produce the same results each time, which leads people to suspect others may run it until they like the match schedule.

Even if it produce the same results each time, how do we consider assigning real team numbers to the placeholder numbers? People can still reassign it until they like it. I personally don't think people will do that, but my proposal earlier will take care of this problem if the average strength of opponents is about the same for everyone, then there is no difference.

[IKE]

Ed,
Your even average opponent strength has an inherent flaw that the performance metrics for teams do not follow a distribution that would be reasonable to apply such an algorithm.

For instance, last year the average match score was aroun 24-30 points, which would mean in theory the average team contribution would be 8-10 pts. In reality, the middle teams had a much lower contribution because several teams (5%) were able to do 60+ points on their own.

In order to balance the competitive levels, the good teams will invariably have the lowest scoring partners way more often. For games like last year or 2008, this might not be a deal breaker, but games like 2009 would be extremely difficult with the poorest performing partners. If you add in these parameters, teams may intentionally "game" such a system. If you are using OPR, they might shave points (2010). With other performance metrics, you could see other behaviours that one may not want to see.

Like coin flips, sample size with a more random generator will help a lot more than forcing a "fairness algorithm" function.

An important think to keep in mind is that this is 3 vs. 3. This can be demonstrated with some dice pretty well (actually the dice are even more "fair" in distribution and probability). If your team is a 3, and your partners are random draw, then on average, you will have a 6 on your alliance about 1/3 of the time (2 of 3 dice are rolled with 6 outcomes thus 2*1/6=1/3 in having at least one 6). On the other hand, the opposing alliance will on average have at least one 6 1/2 of the time (3*1/6=1/2). This would lead you to believe you were given an unfair schedule, even though it doesn't get much more fair than 3 dice vs. 3 dice. The "6" knows that 100% of the time, they will have a 6 on their alliance (its them), and 1/3 of the time (2*1/6), they might even get another 6. This would appear that they have a "stacked" schedule. The average combination for the "3" team would be 10 (3+2*(6+5+4+3+2+1)/6=10), where as the actual average would be a 10.5 (3*(6+5+4+3+2+1)/6=10.5), and the average for a "6" team would be 13 (6+2*(6+5+4+3+2+1)/6=13). The numbers only get worse if you are a 2 or a 1.

This is not to say that crappy schedules do not happen. You can roll double 1s in a game 2 times in a row.

I think the match scheduling challenge is a really neat exercise, but be warned that good intentions can have dire consequences. As others have mentioned, the "algorithm of doom 2007" was really tough on lot of teams. I did some trials after that year. With a 2x2 format, you can use a geometric progression in order to do pairings for many sizes of events. I tried using a similar geometric progression for a 3x3 and accidentally stumbled upon results very similar to "the algorithm of doom". Make and test your programs, and you will find that "easy" methods collapse after the first 3 rounds.

[Nemo]

I'm with the crowd that prefers a purely random schedule with no inputs based on team performance.

The scheduling algorithm adds some healthy uncertainty to the outcome of the game, which makes the game more exciting than an affair where the top team is virtually guaranteed to win. The best team has the best chance of winning, but other teams also have a reasonable chance. That is "fair." Tweaking the scheduling algorithm according to performance metrics will tend to artificially favor either the best teams or the other teams, depending on how it is tweaked, which I consider to be undesirable.

Admittedly, it would be nice if more of the matches were close. But I don't think the scheduling algorithm is the right tool for that job.

[Tom Bottiglieri]

Originally Posted by Ed Law

I think it is very important that the algorithm will produce the same answer no matter how many times you run it. The current one that FIRST use does not produce the same results each time, which leads people to suspect others may run it until they like the match schedule.

What stops me from re-implementing it and knowing my match schedule 3 weeks beforehand?

[johnr]

Would it be possible to run two sets of matches? First day would be random and second day would be based on first day results. Please understand i have no knowledge of programming and was just thinking outloud.