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.