Match Scheduling Algorithm Competition

[Ether]

for modern computers, there just aren’t all that many ways to combine 16 to 128 teams, in 4 or 6 team matches.

[sub]128[/sub]N[sub]6[/sub] = 5,423,611,200

[sub]6[/sub]N[sub]3[/sub]/2 = 10

[sub]128[/sub]N[sub]6[/sub]*[sub]6[/sub]N[sub]3[/sub]/2 = 54,236,112,000 (possible matches)

So for a 40-match tournament,

[sub]54,236,112,000[/sub]N[sub]40[/sub] = 2.88x10381 (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

**

[JesseK]

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/08/collections-library-for-millions-of.html

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

[gblake]

…

*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

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

[Ether]

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.

**

[Ed_Law]

Ed,
In order to balance the competitive levels, the good teams will invariably have the lowest scoring partners way more often.

An important thing 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 21/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 (31/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 (21/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.

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.

[GaryVoshol]

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.

[Ed_Law]

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.

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.

[GaryVoshol]

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.

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.

[gblake]

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

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.

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

[IKE]

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.

[Nemo1]

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.

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.

[JesseK]

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.

[Ed_Law]

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.

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.

[JesseK]

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.

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

[Ed_Law]

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.

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.

[IKE]

Your “penalty” of having a high strength is only (26.33-25.77)*2=1.12…

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.

[gyroscopeRaptor]

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

Dean had the opportunity to speak at the 2011 TopCoder Open and always looking for ways to promote and support FIRST, he accepted their offer to dedicate one of their competitions to a FIRST related issue. FRC currently uses a very effective algorithm written and generously donated by Idle Loop to generate match schedules at FRC competitions. However, some teams still complain to event officials if they believe they or any other team have been assigned to the same color alliance, the same player station, the same alliance partner, or to too many rookie teams, or against too many experienced teams, too many times. TopCoder offered a unique opportunity to explore the inclusion of variables not currently accounted for in the match generation algorithm. FRC requested the design include the ability to turn on and off various attributes and the ability to change the weights assigned to attributes when creating optimized schedules. FRC staff will review the winning algorithm, (and like last time, we will turn the algorithms over to teams for input if we decide we like it enough to seriously consider adopting it), but we are not under any obligation to utilize the winning design. My thanks to team 1251TechTigers who set up a booth at the event and answered questions from participants and attendees curious about FRC.

[gblake]

The latest post on Bill’s Blog revealed some information about the purpose of the 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

…
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” …

[Ed_Law]

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.

[Taylor]

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.

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]