Match Scheduling Algorithm Competition
 

At the TopCoder open the "marathon match" problem is scheduling for FIRST events. Contestants have to come up with a computer program to generate schedules for FIRST events. They are scored on a number of things like the amount of time between matches for each team, number of times the same teams play, etc. FIRST is sponsoring the problem so they will probably use the winning algorithm at future events. You can view the problem statement here (needs an account) http://community.topcoder.com/longco...21964&rd=14632

For those who don't know TopCoder is a programming contest. The TopCoder Open is their yearly championship which is in Florida this year. In the marathon match format the contestants get 12 hours to come up with the best solution to a problem given. They have about 3 hours left in the contest now.

Re: Match Scheduling Algorithm Competition
 

I wonder why FIRST didn't publicize this?

Re: Match Scheduling Algorithm Competition
 

Best I can tell from rooting through their site, this particular challenge is their championship round and is thus invite-only.

The challenge has seven quality metrics they're trying to minimize (with each metric carrying its own definable weight):

-Difference in average team age on each alliance between the two alliances
-Difference in average rank of a team (defined from 1 to 10 in the challenge, where 1 is rookie and 10 is reigning champion) between the two alliances
-Unique partners
-Unique opponents
-Time between matches (more is better)
-Assignment to red or blue
-Position in player station

If FIRST took the current match assignment criteria (as defined in The Tournament--PDF link) and put the age and (reasonably-calculated) rank criteria in beneath the unique opponent/partner criteria, then it could reduce the number of "oh-crap-we-play-against-Beatty-AND-Simbots-this-match?!" rounds--at that point, the algorithm is likely to switch one of them to your alliance (especially at Championship, where they'd have the benefit of regular-season data).

TLDR: This could evolve into a good thing or a bad thing, depending on what weight you put on the factors.

Re: Match Scheduling Algorithm Competition
 

FIRST has no valid way of ranking teams, and thus the only fair way to do selections is randomly. Factoring age or some arbitrary rank will never be fair.

Re: Match Scheduling Algorithm Competition
 

I'd go with ditching the age entirely. Remember the Algorithm of Doom in 2007, where you might end up against 1114 AND 2056 (a rookie that year) AND 71 at the same time, and all of them multiple times (assuming that the age breakup worked out that way), and very rarely with one or the other?

Yeah. Age has very little to do with anything around here--I'm somewhat scared of what Dr. Joe is starting up in Boston...or any team 1114 mentors.

The rank part, OTOH, I can live with, if it's done right. If you're careful about the implementation, and use the available data about record/seeding/result, then I think it could work very well. If you're arbitrary about it, like the Algorithm of Doom was with age, it'll go down as a lousy idea.

Re: Match Scheduling Algorithm Competition
 

Take the other point of view and ask yourself how to minimize the "Hey, we're one of the top teams at this event and we get to play with a box on wheels and one that only spun in circles last match". True random is the only way that you can make fair schedules. The last time FIRST tried to introduce "smarts" into the system the worst schedules in history were seen (remember the low/mid/high system)...I hope they never try to do that again.

EDIT: Looks like Eric was thinking along the same lines as me.

Re: Match Scheduling Algorithm Competition
 

Agreed--there will always be really great rookies and really awful veterans, and there are teams that reach Einstein one year that fall off the radar entirely the next. No formula accounting past years' performances will account for student and mentor turnover perfectly.

However, one could certainly compute rank for within the season, especially at the Region Championship and Championship levels where everyone has played this game before.

Edit: Dave got in between my reading and my posting. I'm not advocating for those two to be anywhere before line D in this year's criteria (read: just ahead of equal red/blue assignments), if anywhere. I'd definitely want to see some sample outputs before I put my blessing on any such method.

Re: Match Scheduling Algorithm Competition
 

If they want a good algorithm... why not put the challenge out there, offer a cash prize or a free pass to champs for your team, and give everybody 3 MONTHS (instead of 12 hours) to work on it

Re: Match Scheduling Algorithm Competition
 

I wouldn't take a single coder 3 months, and a team of 4-6 could easily do a rough draft in 12 hours. I'd say that we should give them the same length as the build season: 45 days. There are 2 basic approaches I've tried in the past:

1. A combinatorial approach that uses all 500,000-some unique match pairings of a 84-team event (worst case example) and begins to brute-force build a schedule based upon rules. Conceivably this would be a fine approach until the end, where the rules would be harder to meet given the dwindling pool of match pairings that meet the rules.
2. An approach that calculates the 'buckets' of teams, assuming even spacing. For example, if 24 teams play 6 matches each, then one can create a long list of teams that is a simple stitching of 6 shorter lists {{1...24}{1...24}...{1...24}}. For minimum match spacing, the edges of the stitches should be checked for duplicate teams (easily done if one uses Collections.disjoint() in Java). After that, the list could be broken up into alliance pairings (multiple of N teams per alliance) and then match pairings (M alliances per match). Then an algorithm could check for duplicate alliance pairings, duplicate opponent pairings, etc. If the algorithm finds them (very likely if the stitched lists are randomly-generated) it's up to the coder to figure out what to do next -- live with them, regenerate new stitched lists to find a better pairing with less duplicates, etc.

I dug into match scheduling some, with various modifications to the approaches for efficiency. It's not easy to get it perfect, but it IS easy to get it started and is a great way to teach object-oriented programming to students who already have the basics of programming under their belt.

Really they should have 2 competitions: 1 that creates the algorithm, and 1 that creates an intuitive User-Interface for it. Both are equally difficult, IMO, and the latter would teach very fundamental concepts of software product design.

Re: Match Scheduling Algorithm Competition
 

I am vehemently opposed to the idea of factoring either team age OR rank into FIRST match schedules - AT ALL.

Re: Match Scheduling Algorithm Competition
 

Co-Signed, with one exception:

I'd prefer to not see Three Rookie Teams playing on the same alliance at the same time.

Re: Match Scheduling Algorithm Competition
 

So am I. The only thing equal to or more inspiring/motivating than teaming with 1114 is getting stomped by them (lol). IMO, the problem is more about the perception of what 'should not' happen under 'random' circumstances. Under random circumstances, lopsided match pairings are equally likely to evenly-skilled match pairings. Yet at run-time (i.e. at competition), the lopsided matches are often undesired and perceived as the product of a 'bad' algorithm.

This perception is similar to the perception of coin-flipping: often times, after a streak of 'heads' one incorrectly often perceives the chances of getting 'tails' to be higher -- when in reality nothing about the probability has changed. I don't have the article that I read on probability psychology bookmarked, but I'll look for it later if I remember to.

Re: Match Scheduling Algorithm Competition
 

Of course not. But 3 months calendar time (not man-hours) makes the challenge accessible to a larger talent pool.

Re: Match Scheduling Algorithm Competition
 

And allows for adequate testing and analysis.

Re: Match Scheduling Algorithm Competition
 

Like Jesse, I too have written a scheduling program. I took the brute force & heuristics approach. It wasn't too hard even for someone like me who does software work mostly as a hobby. Mine was for 2-team matches because I was focused on FVC (FTC/VRC) at the time.

Truth in advertising - The heuristics still need to be tweaked to avoid getting "trapped" by early arbitrary choices that force a bad choice later; but the overall results are pretty good.

A couple of points to make:

1) I have written this before, but it bears repeating; there is no such thing as a scheduling algorithm that is simply "fair". Algorithms are only fair in some "sense(s)". In conversations like this thread, if you don't pair the word "fair" with a description of the sense(s) in which you are using it, the conversation falls apart.

When the word is used you have to clarify whether you mean fair in the sense of putting all teams at each of the red and blue alliance station positions evenly, or do you mean fair in the sense of ignoring the expected skill level of their allies, or do you mean fair in the sense of attempting to give each alliance a similar expectation of winning each match, or...

In this and many other contexts, I recommend banishing the word "fair" from your vocabulary if it isn't paired up with more information.

2) I remain surprised that the scheduling algorithms at STEM robotics tournaments aren't drawn from open source descriptions and code. The scheduling problem isn't that hard. Tournament organizers (either at a worldwide HQ level or at local levels) should choose the heuristics they want to employ, proudly announce them, pluck a tried-and-true implementation off the shelf, and then get on with the rest of the season.

In the scenario I outlined above, folks (participants) could certainly suggest different heuristic choices (and certainly would), but once the choices are made, there shouldn't be any mystery about them or about how they are implemented.

Blake

Re: Match Scheduling Algorithm Competition
 

Well said !

As have I, for widely different tournament situations.


Meaning what, exactly?

- generate the space S of all possible tournaments

- assign a score to each of these tournaments using weighted criteria

- pick the tournament with the highest score

OR

- randomly generate a tournament

- assign a score to the tournament using weighted criteria

- stop when you find one with an acceptable score

OR

- construct a tournament using some rules

- assign a score to the tournament using weighted criteria

- stop when you find one with an acceptable score

OR

something else?


Finding an acceptable solution isn't that hard. Finding the solution that best fits your selection criteria can be quite difficult if the search space is large.

Re: Match Scheduling Algorithm Competition
 

The FRC scheduling algorithm has been pretty good in the past few years, hasn't it? I don't think they need a new one.

Re: Match Scheduling Algorithm Competition
 

I'm all for iterating on systems to improve them but when you have things that don't work and things that do you need to prioritize utilization of resources. That being said, outsourcing this to a competition is a pretty good use of resources. It only costs FIRST some time writing requirements and reviewing results rather than spinning up a dev team.

But who knows, they might not ever use the results. They could have just had the problem description laying around from when they had their algorithm written.

Re: Match Scheduling Algorithm Competition
 

It is hard enough for the seeding algorithm to work accurately with such a small sample size; deliberately biasing the schedule for or against some teams will just make it harder to determine who should be ranked where.

Re: Match Scheduling Algorithm Competition
 

After the algorithm of doom* (2007), FIRST did a few things.

They provided a list of requirements for a scheduling algorithm.

FIRST also solicited comments on additional requirements, but did not incorporate any. Most of the comments I remember related to the minimum time between matches, either taking into account natural breaks (end of day and lunch) or allowing a single long break, for things like judge interviews. I don't remember any proposals for incorporating team rankings or age into the schedule.

Third, they provided a program that would provide rate a schedule based on the requirements. This way, any other algorithm could be evaluated objectively.

Finally, they provided a reference program, Idleloop Software's MatchMaker (Written by Tom and Cathy Saxton of team 1318) and challenged people to beat it. I only know of one other scheduler that was submitted, and it was marginally worse then MatchMaker. The challenge was issued in September, so there was about 3 months, however, it seemed like all activity died out within 2 weeks or so.

Even though the MatchMaker software was available for months, just having it available didn't catch all the initial bugs. It was only a week before the championship that people started noticing a clumping problem with large events.



*One thing to remember was that while the Algorithm of Doom did group teams by team number the main reason it was hated is that it did a horrible job at creating a schedule with varied opponents and partners. If the algorithm had done a better job at giving teams different partners and opponents, it might still be used.

Re: Match Scheduling Algorithm Competition
 

Thanks for the history lesson Joe. Very interesting.

Four years have passed since 2007, and a whole new student class is now in place. Maybe it's time for FIRST to put this out there again.

One point of clarification:

I assume that means "maximize the minimum time"

Re: Match Scheduling Algorithm Competition
 

From memory, and it was a while ago...

Compute all possible (2-team) alliances.
Use a simple arbitrary scheme for pairing alliances in 1st round matches
For 2nd round and beyond matches:

Disregard possible alliances that were used in previous matches
Assign each possible alliance the shortest off-the-field time associated with the two teams in that alliance.
Pick the possible alliance that has been off the field for the longest (break ties arbitrarily).
Pick an opponent from among the remaining alliances. Choose one that:

Doesn't include a team that was allied before with the teams of the already selected alliance
Doesn't include a team that previously opposed the teams of the already selected alliance
Has been off the field the longest

Continue

Continue

I also think that, in order to preserve a minimum inter-match time interval, I put in a heuristic that would permit the first alliance put into a match to face opponents who had been allies earlier.
[Edit] Thanks to Joe I was reminded of this long post that I wrote a while ago - It contains a better description of the heuristics I used - Look near the bottom of it.Link [/Edit]
As you know, looking for the "best" of solution to problems in algorithmic domains like one is often fraught with confusion, peril, and frustration. Looking for "good enough" often is the best choice ;)

I should have been more clear. I was willing to accept minor separation between my results and perfection. Creating a good enough scheduling implementation isn't all that hard.

Blake
PS: Joe's info surprised me - Either I totally forgot or totally missed the solicitation and evaluation process he described, so I sent him a PM asking if has any still-valid links or other info I can look at to learn about it.

Re: Match Scheduling Algorithm Competition
 

At this point, I dunno why we aren't simply creating our own open-sourced algorithm and associated interface. The software engineering prowess of the CD community as a whole could probably out-do a single contestant in any contest, regardless of how long the contest ran. Multiple small tasks are very easily delegated and worked on with a good group.

When I find some time (heh, my fiancee moves in this weekend) I'll resurrect some old stuff and make a Google Code project out of it. It'll start off in Java since that's what I made it in at the time.

Re: Match Scheduling Algorithm Competition
 

I'll contribute.

Re: Match Scheduling Algorithm Competition
 

If it is possible, the software should have an option to take into account the team's performance so far in the season in order to generate a "fair" match schedule for FiM or MAR Region Championship or World Championship. Let me define what is team's performance and what is fair.

Team's performance can be highest OPR, weighted average OPR or season world ranking.

Fair does not mean trying to make every match as close in score as possible so that any alliance would have a fair chance of winning. Fair means no teams should have a heavier "load" than other teams. Mathematically, it will mean that the average OPRs of the opposing alliance that each team will have to face will be about the same. In this way, teams that have higher OPRs will still have a higher chance of winning their matches. I like this way because it does not actually look at the predicted score of each match based on OPR and artificially modify it to force the outcome. There is still some inherent randomness to it.

Re: Match Scheduling Algorithm Competition
 

What about years where OPR/metric du jour are not really applicable?

Re: Match Scheduling Algorithm Competition
 

If FIRST wants to follow the sports model, tell me a sport where there is scoring that OPR is not applicable? The only recent game I know that does not work is 2007 Rack "N" Roll where the score goes exponentially up if you have a few tubes forming a chain. What can I say? The game may be good but the scoring is bad from spectators' viewpoint. It is too complicated. We need games and scoring that is simple to explain to visitors. I think I am going off topic.

I guess we can use win/loss, being alliance captain or be drafted in elimination round and how far they advance, which is what the ranking point system is for the Michigan district model.

If you don't like using OPR, do you have any suggestions what we can use?

Re: Match Scheduling Algorithm Competition
 

I'm not saying OPR is a wrong metric. I'm just saying that algorithms are determined before the game is played, what if it is found that the metric chosen is not a good indicator of performance?

I'll also come out and say that any attempt to make schedules "fair" is doomed to failure in my opinion due to differing opinions on what metrics to categorize on. I claim that the only fair way to do scheduling is to not look at the team numbers at all. That way every team has the same chance of getting an easy schedule or an impossible one.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

OPR has biases in each and every year. In general, given the nature of FIRST scoring (finite number of game pieces and/or scoring locations), as the quality of teams at an event trends up, OPR for teams near the top and bottom flattens out - at some point, there are simply not enough tubes, or balls, or whatever for each team to score to their maximum ability. Compare the OPRs from the Michigan State Championship with those from a middle-tier Regional and tell me that they make sense.

Regardless, I think there is no need to balance scheduling with any consideration of robot performance or capability. Random is at least as "fair" as any other method. If you draw an easy schedule, enjoy your cakewalk but have fun getting bounced out of the playoffs if your bot isn't up to the task. Likewise, if you draw a tough schedule but the robot performs up to its abilities, you will be drafted and have a great chance to go deep into elims. IMO, the best way to be "fair" about it is to maximize the number of matches (random draws) that each team plays.

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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!

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

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

Re: Match Scheduling Algorithm Competition
 

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.

Re: Match Scheduling Algorithm Competition
 

Ouch.

Ouch.

Ouch.

Not from the programmers, mind you--from the people who have to run the program again. Once you get those people doing less work (i.e., making the second day's run automatic), then it's from the programmers. Once they figure out how to do it (how I don't know), then it comes from the teams that get shortchanged one match (or sometimes 2) due to scheduling, then from the programmers again trying to fix that problem.

Could it work? Probably. Is it optimal? No.

Besides that being the way alliances are chosen for Saturday afternoons...;)

Re: Match Scheduling Algorithm Competition
 

The software can be written pretty easily to do just about anything that isn't completely insane, and that is actually achievable/feasible given the number of teams, matches, and user-defined attributes.

I am comfortable saying this because for modern computers, there just aren't all that many ways to combine 16 to 128 teams, in 4 or 6 team matches. No human would want deal with all the combinations, while juggling a bunch of screwy attributes, to create a schedule; but our computers are fast, tireless, accurate, and don't complain about doing boring, repetitive calculations for us.

So.... the central question in this case isn't whether a computer program can be written to accomplish the task. The question is whether the humans specifying what the program's instructions should accomplish, can ever agree on what they would want the program to do.

Echoing Eric's sentiments: Compared to agreeing on the requirements for, and then properly specifying, the algorithm, the coding will be the easy part. ;)

Blake

Re: Match Scheduling Algorithm Competition
 

₁₂₈N₆ = 5,423,611,200

₆N₃/2 = 10

₁₂₈N₆*₆N₃/2 = 54,236,112,000 (possible matches)

So for a 40-match tournament,

_{54,236,112,000}N₄₀ = 2.88x10³⁸¹ (possible different "tournaments", not counting the order that mathces are played)*

*Of course, the vast majority of these "tournaments" are patently ridiculous - like one team playing all 40 matches and another not playing at all. With just a bit of smarts, the number could be reduced greatly. And, unless you are designing an algorithm to examine all possible tournaments and pick the "best" one, you don't have to deal with this search space

Re: Match Scheduling Algorithm Competition
 

Interestingly enough, the quantity of combinatorials for match numbers are somewhat inflated since "order matters" -- i.e. with these algorithms {A,B,C} is not the same as {B,A,C}. Where it gets really interesting is that it takes more time and more memory to say "order doesn't matter", even with quick disjoint() calls, than it is to simply handle a huge list of team alliance combinations.

A really smart guy created some benchmarks for Huge Collections that take advantage of Java's bytecode optimizations when using a collection of interfaces instead of a collection of objects (less GC'ing):
Code https://github.com/HugeCollections/Collections
Benchmark http://vanillajava.blogspot.com/2011...llions-of.html

I will see if this next week brings me enough time to start a project, heh.

Re: Match Scheduling Algorithm Competition
 

OK, I'll slightly revise my statement. "... there just aren't all that many useful ways to combine 16 to 128 teams, in 4 or 6 team matches. ..."

I'll add that if your goal is creating a tournament schedule that is good enough, you don't ever need to evaluate all possible useful tournament schedules. Given a pseudorandomly chosen starting point, you just need to be able to complete at least one useful tournament schedule built on that initial choice.

And, (I think this is partly what Jesse means when he talks about "stitching"), for the most part you can create the schedule one match at a time (perhaps with some occasional backtracking) without ever having to examine any schedule except the partial one you are in the process of completing.

Blake

Re: Match Scheduling Algorithm Competition
 

There are 54 billion "useful" ways to pick the first match randomly for 6-team matches and 128 teams.

With each succeeding pick, the space of "useful" matches from which to randomly pick can be decreased using selection rules (e.g. don't assign teams to back-to-back matches; when any given team has been assigned 3 matches (for a 64-match tournament) drop them from the search space; etc)

I don't think it's mathematically guaranteed that you will achieve a valid tournament following this simple procedure. You may come to the last match and there's no valid match to pick from the remaining search space.

Re: Match Scheduling Algorithm Competition
 

Isaac, based on what you said, I think you misunderstood the criteria that I have in mind. First of all, the algorithm is not to select alliance partners for a team. It is also not to make matches even in score. Let me try to explain again.
It is based on strength of opposing alliance, the other 3 teams. Using your "dice" example, regardless of who your alliance partners are, you will get some opponents that are "6" and you will get some that are "1" and anything in between. On average, every team should face the same total strength of opponents out of all their matches. I don't see how it can be more fair than this. Even if the distribution is not "normal" in terms of strength. Let's say there are very few "6"s and a lot of "2"s and "3" so the average is still 3.5. What I said can still happen. The algorithm will work such that if you face a "6" in one match, then on other matches you will face more "2"s and "3"s to balance it out.
The algorithm I am proposing does not care who your alliance partners are. It also is not trying to prevent blowout matches. There is still a lot of randomness to it, which is what I like also. But nobody can say their schedule is harder than others in terms of the opponents that they have to face. So if you are a better team, the destiny is still in your own hands. And if you are an average team, you may still do well if luck is on your side and you got some good partners. Your assertion that good teams will get weaker partners is not an outcome with what I have in mind. It will only happen if you try to balance your alliance's strength which is a bad criteria.
If anyone out there understand what I am trying to say, please help.

Re: Match Scheduling Algorithm Competition
 

Ed, I understand your scenario. If Team1's opponents cumulatively have the same relative ranking (whatever the measurement) as Team2's, Team3's, ... TeamX's, then it doesn't matter who you play WITH. You might be playing with two powerhouses against 3 weaklings in one of your matches, but to make up for that you will be playing against powerhouses in another match.

My question is how you determine the initial conditions. For example, how do you rank the teams for Kettering in Week1? And then how do you rank the teams for Week2, given that the vast majority of those teams will be newbies that week - but there will be one or two teams at TC or Waterford who have played at Kettering.

I also question why for any given set of teams, the schedule that comes up must be unique? Surely there might be more than one schedule that meets the stipulated criteria equally well. Simply switching the order of matches might give some equally good permutations.

Re: Match Scheduling Algorithm Competition
 

Thanks Gary, I am referring back to my original post. I am proposing that the software has this performance metrics as an option that a user can turn on and off. We can turn it on for FiM and MAR Region Championship only at the organizer's discretion and also for World Championship. We can not use it for Week 1 and 2. We should not use it for Qualifying (district) events when there are only 40 teams. It will work well at the Championships when there are 64 (FiM) and 87 (World) teams.
Yes it is true that there can be multiple solutions that are "good enough" and all of them will work. The only reason why I think the solution should be unique is so that no one will suggest somebody keep running the program until they like the results. However assigning the actual team numbers to the placeholder team number can still be manipulated. Ideally no human should be involved in creating the schedule except for the programmers who programmed it and somebody pressing a button. We also do not want teams to run the program themselves and know ahead of time what the schedule is.
Gary, are you involved in generating the schedule at an event? Maybe somebody can shed some light as to how it is actually done so people don't speculate.

Re: Match Scheduling Algorithm Competition
 

I've seen them do it. The computer crunches through multiple possible schedules (5000, 20000, 6000000, I don't know how many) and it picks out the "best" one considering the established parameters: time between matches, multiple matches with and against other teams, red/blue, etc. There are some parameters the scorekeeper puts into the program - starting times, lunch, number of rounds desired, match cycle time minimum match separation, etc. Some of these inputs could make an unworkable schedule - for example, with a 36-team event, you can't select a minimum of 5 match separation; each match would have the same teams in it.

While the scorekeeper could possibly look at the generated schedule, reject it, and start over, I would doubt that would happen. They are usually pressed for time.

Re: Match Scheduling Algorithm Competition
 

I'm sure having a hard time conveying that I agree with you. You were right when you said "With just a bit of smarts, the number could be reduced greatly."

One useful method I like for the picking the initial match's alliances from among a field of N teams is using a user-defined seed to generate pseudorandom (integer) numbers between 1 and N until I have created a list of 6 unique numbers (4 for VRC or FTC, 2 for FLL?).

Another is to create a list of all m-team alliances (my past implementation ignored order (ignored which driver station a team would be assigned to in FRC)) and then iteratively use a user-defined seed to ... pick any two alliances that don't share any teams.

Neither of these requires dealing with 54 billion possible 6-team matches.

Don't forget this parenthetical statement from one of my earlier posts "(perhaps with some occasional backtracking)", and combine it with a "good enough" frame of mind.

Blake

Re: Match Scheduling Algorithm Competition
 

For an event like MSC, the average score was about 79 pts. The equal strength of opposition would then try to balance out your opponents so that on average, you would play opponents whose average contributions would be 79 pts. This would give an average contribution of around 26.3 points. If you were a team with an OPR of 60, the pool of rremaining candidates would now have an average lower than the 26.3, and thus in order to get to the average 79 pts/match of opposition, you would on average have to play a tougher than "random" schedule. If your team had a OPR significantly below 26.3 (some would), then you would have a softer than random schedule as it would require balancing in the other direction. Unfortunately, algorithms must do the groupings at the same time (opponents and partners), and invariably work out the way I discussed (at least on average). While the differences are not huge, there is a shifting that occurrs.

The "dice" example was more of an illustration of the psychological effect that occurs when it comes to "schedule" and preceived unfairness. As you have 2 partners, and 3 opponents, you are 50% more likely to oppose any kind of team than you are to have as a partner.

Re: Match Scheduling Algorithm Competition
 

I know that Ike has already responded to this pretty well, but I think another important thing to point out is that you and your allies are somebody else's opposing alliance. Therefore, the adjustment you are proposing would still give stronger allies to weak teams and weaker allies to strong teams on average.

Re: Match Scheduling Algorithm Competition
 

The real problem with gauging 'strength', which has been stated before, is that some teams' strengths vary wildly from year to year. Lose a mentor, gain a sponsor, graduate 90% of the students, gain access to a full machine shop -- any of these things could wildly change how well a team does.

I would conjecture that attempting to stack alliances based upon supposed unproven strengths will most likely create more confusion and controversy than a 'bad luck' fully-randomized schedule would. For example, any one of the powerhouse teams could have an off year in 2012, making the rest of us "totally screwed" if we're allied with them since they're the supposed counter balance to a "strong" opponent alliance.

Re: Match Scheduling Algorithm Competition
 

Hi Jesse, I completely agree with you. We should not use previous year's strength data for current year's match assignment. That's why I advocate taking strength into consideration for Region Championship and World Championship only where current year's data would be available. I have not seen anybody on this thread or elsewhere that advocate on using previous year's data.

Re: Match Scheduling Algorithm Competition
 

Ah, missed that part of it. Thanks for clarifying.

Re: Match Scheduling Algorithm Competition
 

This is going to be difficult to explain but I will try. I understand what you are saying. I knew that and I thought through it already. By trying to achieve an average opponent strength of 79 pts/match (using your example), there will be an effect on your alliance as well. Afterall, the total strength of all the teams is a constant. However the key is that the algorithm do not force your alliance to be 79 pts also even though you are somebody else's opponent. Those 3 opponents that have to play your alliance will most probably be playing an opposing alliance that is higher than 79 for that match, but it is still possible for each of them that with all their other matches, their average opponent strength is still 79.
In this optimization, even though everything is related, we are only trying to control average opponent strength and not your alliance strength. Yes, your alliance strength is affected as you said. So let's do the numbers as in your example.
Let's say your team has strength of 60. Your opposing 3 teams have a total strength of 79. In a 64 team tournament, the remaining teams will have an average of ((79/3)*64-60-79)/60=25.77
Explanation of the formula: 79/3 is the average strength of each team. There are 64 teams. Hence the total strength is (79/3)*64. However we have to subtract out your team with strength of 60 and the combined strength of opposing alliance which is 79. Since we took out these 4 teams, we should divide by 60 which is 64-4. So the average is 25.77.
The original average was 79/3 or 26.33. As you can see, the change is very small. The irony is that the perceived assignment of weaker partners is due to your team's strength of 60. So what is the bottom line, your alliance's strength is 60+25.77+25.77=111.54 and is still way higher than 79. Your "penalty" of having a high strength is only (26.33-25.77)*2=1.12. Your alliance is still at an advantage of 111.54 versus 79 due to your high strength.
Before I continue, I need to address other people's concern that by controlling average strength of opponents that it will guarantee a team with strength of 60 will be at an advantage to win every match. That is not the case. We are only talking about average here. This strong team is not going to face opposing alliance with strength of 79 in every match. Sometimes they will face opposing alliance with strength of 110 and sometimes they will face opposing alliance with strength of 48. But the average is 79. As far as their partners are concern, they will not have partners with 25.77 in every match either. This is especially true since we are not controlling what the total alliance strength is. Sometimes they will get strong partners and sometimes not so strong. However when all is said and done, with their strength of 60, they will probably win a lot of matches, and there is nothing wrong with that. They deserve to.
Remember that this algorithm still allows quite a bit of randomness in it since we don't look at the predicted outcome of each match.

Re: Match Scheduling Algorithm Competition
 

That is correct. On average I would have alliance partners with 4% lower scoring potential than an average team. A team at the opposite end of the curve might have a 4% advantage to their partners on average.

Adding in the additional constraints would likely lead to a balancing effect. If I am partnered with another good team, it would require a substantially larger number of bad teams to even out that influence of the 1 good partner. Thus driving down the average of my additional match partners substantially lower. The "good" news is by luck of the draw, I had a match with 2 good partners. The "bad news" is that to work out the averaging function, the rest of my partners are now well below average. The same would hold true from opponents. You could go up against 3 60 point opponents, and then the average leftover would be... (79*12-180)11=69 pts for the new average for your additional matches.. Thus a substantially easier road to and 11-1 record.
At an event where there are fewer matches, this is compounded even larger. Run the numbers for a championship division. If you have 1 death match, you would essentially have very easy remainder matches.

Re: Match Scheduling Algorithm Competition
 

The latest post on Bill's Blog revealed some information about the purpose of the competition.

Re: Match Scheduling Algorithm Competition
 

See the quoted text below.

I wonder if FIRST will ever become so tired of the complaining that they decide to test drive using well-known, precomputed schedules containing placeholder team IDs (before any/all tournament(s) folks can go over the well-known schedules with a fine toothed comb as many times as they like until they are groomed into perfect "fairness" :ahh:), and then simply replace the placeholders with actual teams IDs at the start of each/any tournament.

No one could complain that any perceived problems with the schedule(s) were the fault of a scheduling algorithm that treated any category of team better or worse than any other. The algorithm couldn't. It wouldn't have any information about the teams participating in any of the tournaments. It could be run in Dec 2011 and then retired permanently (after any nit-picking of its results was completed).

FIRST could even challenge (potential) complainers to massage the pre-computed schedules until they were so thoroughly "fair" :ahh: that any conniving attempt to put weak or strong teams into special slots in the schedule would have no significant effect aside from one match (Yes - I know even one successfully gerrymandered match would be bad...).

Blake

Re: Match Scheduling Algorithm Competition
 

I enjoyed the discussion with others on this topic but this is probably my last post on this subject. The reason is I have changed my position on this. I no longer think we should use strength in the algorithm. I was reminded that any rules no matter how well it was intended can have undesirable consequences. Think about the ranking points rule of 2010 that leads to 6 vs 0. If teams know that strength is being considered in the algorithm, the strong teams may start sandbagging during the season in hope of coming out stronger than their statistics show in the post season. This will destroy the game.
The only effect a tough schedule has on a team is they may not be alliance captains because they don't get enough wins. However if the team is indeed good, the OPR numbers and scouts will recognize that. Even if they rank low, they can still be number one pick. So it is not as bad as it seems.

Re: Match Scheduling Algorithm Competition
 

That's a great idea ... until a team doesn't show up.
I don't think I've been to an event - regional or offseason - in which 100% of the teams that were on the list the week before actually made it to the arena and competed every match, every day. When there are 41 teams participating instead of the expected 42, the pre-drawn match structure goes out the window.

[edit] Are you proposing that there are match schedules drawn up for every number of competing teams, from 24-104, these schedules are on hand before every event, then are printed on the morning of the tourney? If that's the case, then I Emily Litella-ed it. [/edit]

Re: Match Scheduling Algorithm Competition
 

Yea that's what he's proposing. It's quite easy to debug algorithms that always deal with team #'s 1-N (or 0-N).

The only issue I see with developing all possible schedules is the aggregate size of the files, unless Blake's proposing ONE 'best' schedule for a given # of teams be used. If that's the case, then generating 80 'best' schedules could be done via team ID's (0-N, where N = # of teams) and then another algorithms simply randomizes the team lists at the events and assigns the ID's to a team #.

Heck, 80 'best' schedules could probably even be generated by hand...

Re: Match Scheduling Algorithm Competition
 

This approach would offer an opportunity for incremental improvement over the existing algorithm, because it is designed to be run in a short amount of time. A set of canned schedules could be prepared using an algorithm with more stringent specifications, regardless of whether it takes hours to run it.