Match Scheduling Algorithm Competition

[JesseK]

Originally Posted by Ed Law

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]

Originally Posted by 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.

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]

Originally Posted by Ed Law

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]

Originally Posted by gyroscopeRaptor

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" ), 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" 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

Originally Posted by gblake

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

Originally Posted by gblake

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" ), 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]

[JesseK]

Originally Posted by Taylor

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

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

[Nemo]

Originally Posted by JesseK

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

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.