Match Scheduling

[K-Dawg157]

I was thinking...

At the events, teams are randomly paired with other teams to create alliances and score as many points as they can. This means that some teams will get put with other teams multiple times, and other teams will never see that team.

This puts some teams at a disadvantage. If they never get matched with the best robot, there score will probably never be that good. So for the teams that were paired multiple times with that robot, their scores will be so much better, and if they are continuously paired with robots better than them, their ranking will actually be better than they deserve.

What I am proposing is to make the competitions so that each team gets paired with each of the other teams once No more, no less. Everyone is on the same alliance with all of the other teams at one point or another.

This would show the true value of the robot of the team instead of the possibility of a robot being carried into a high seed simply because of their alliance partners in Qualifications.

I realize this would result in longer competitions and scheduling would be more difficult, but that would be a true and fair representation of the robot instead of the robot's alliance partners.

[Green Potato]

Originally Posted by K-Dawg157

I was thinking...

At the events, teams are randomly paired with other teams to create alliances and score as many points as they can. This means that some teams will get put with other teams multiple times, and other teams will never see that team.

This puts some teams at a disadvantage. If they never get matched with the best robot, there score will probably never be that good. So for the teams that were paired multiple times with that robot, their scores will be so much better, and if they are continuously paired with robots better than them, their ranking will actually be better than they deserve.

What I am proposing is to make the competitions so that each team gets paired with each of the other teams once No more, no less. Everyone is on the same alliance with all of the other teams at one point or another.

This would show the true value of the robot of the team instead of the possibility of a robot being carried into a high seed simply because of their alliance partners in Qualifications.

I realize this would result in longer competitions and scheduling would be more difficult, but that would be a true and fair representation of the robot instead of the robot's alliance partners.

Currently, there is an algorithm that decides match scheduling, at least for regionals, and it tries to do just that. However, minimizing repeated alliance partners / opponents is only second order sort behind maximizing time between matches. Also, I worry that for the larger events, it may be unreasonable to do so many matches, and scheduling would be difficult without a significant number of surrogates. Unsure how this works at districts, though, but I presume the algorithm is the same.

[Richard Wallace]

At District events, where the standard is 40 teams, we would need to play 20 matches per team to ensure that every team gets to play with every other team. That would add 67% to the qualifying schedule, requiring an additional day.

Probably not going to happen.

[pntbll1313]

While I would have loved to play the required 32 qualifications to make this possible at the Lake Superior Regional, we only had time to play 9 in our normal 3 day event. A week of qualification matches would sure be fun, but I doubt many schools would like how many extra missed days this would add up to

[GeeTwo]

Originally Posted by Richard Wallace

At District events, where the standard is 40 teams, we would need to play 20 matches per team to ensure that every team gets to play with every other team. That would add 67% to the qualifying schedule, requiring an additional day.

Probably not going to happen.

At Bayou, we had 59 teams, so each team would have to play 29 matches, which would be a 222% increase in the qualifying schedule, requiring at least two additional (and longer) days, more likely three.

Definitely not going to happen.

[jvriezen]

Originally Posted by K-Dawg157

I was thinking...

There are three answers to this.

1. The scheduling algorithm already does the best it can in this regard, but there are other constraints that are even more important (available time, times between matches.)
2. Life isn't fair, FRC isn't perfectly fair either
3. Good scouting should cause the best teams to get to play in eliminations, regardless of the shortcomings of scheduling.

[MrTechCenter]

If you're relying on being partnered with the best robot at the regional for your average to be high, you're doing it wrong.

[MikeE]

Originally Posted by Green Potato

Currently, there is an algorithm that decides match scheduling, at least for regionals, and it tries to do just that. However, minimizing repeated alliance partners / opponents is only second order sort behind maximizing time between matches. Also, I worry that for the larger events, it may be unreasonable to do so many matches, and scheduling would be difficult without a significant number of surrogates. Unsure how this works at districts, though, but I presume the algorithm is the same.

The same scheduling algorithm is used in Districts and Regionals.
I don't think your description of the algorithm is correct. The cost function at the core of the optimization procedure prioritizes minimizing repeated alliance partners over repeated opponents. Time between matches is not part of the cost function at all, but the algorithm only considers solutions that satisfy a minimum match separation.
After generating the schedule the FMS provides overall statistics, which in my experience at District sized events does typically show the maximum number of distinct partners for most teams.

[plnyyanks]

Originally Posted by MikeE

The same scheduling algorithm is used in Districts and Regionals.
I don't think your description of the algorithm is correct. The cost function at the core of the optimization procedure prioritizes minimizing repeated alliance partners over repeated opponents. Time between matches is not part of the cost function at all, but the algorithm only considers solutions that satisfy a minimum match separation.
After generating the schedule the FMS provides overall statistics, which in my experience at District sized events does typically show the maximum number of distinct partners for most teams.

Here's a description of how MatchMaker works from the IdleLoop website:

The algorithm begins by seeding the match schedule with the simplest possible schedule: the teams are dumped in the schedule sequentially in the exact same order for every round. Thereafter, teams are only rearranged within rounds. This guarantees the round uniformity requirement: no schedule that breaks the round uniformity requirement is ever even generated.

When running the algorithm, the minimum match separation is specified. The algorithm ensures that no team is forced to play two matches with less than the minimum match separation. This is also handled up front by the way teams are permuted within rounds: no permutation that would violate the minimum match separation is allowed. No schedules violating the requirement are ever considered as candidates. No other consideration is given to match separation, so one team might have the average separation between each pair of appearances and another might have half at the minimum and the other half widely separated.

The most interesting part of the puzzle is pairing uniformity. This is handled by the simulated annealing. There is a "current" schedule, which is initially the simple schedule described above. In each iteration of the algorithm, the current schedule is slightly modified by permuting some teams around as described above.

Each schedule generated, which is guaranteed to satisfy the first two criteria, is assigned a score based on the amount of partner and opponent duplication. For each team, we count the number of times that team (in a non-surrogate match) sees each other team as a partner, as an opponent, or in either role. Penalty points are added for each duplication, doubled by each additional time a given team is seen in any category. The weighting for duplication in partners is slightly heavier than for opponents, since there are only two partners, but three opponents, per round.

If the newly generated schedule has a better score than the "current" schedule from which it was derived, it becomes the current schedule. If this were the only way in which the current schedule changed, it would be possible to get into a "local valley" where we get stuck with a poor solution which is structured so that it's just a little better than any "nearby" schedule which can be obtained by the permutation procedure. To solve this problem, simulated annealing allows for a small chance of replacing the current schedule with a worse schedule, with the probably decreasing exponentially with how much worse the new schedule is. This will cause the algorithm to jump out of a local valley where no forward progress is being made over many iterations.

In addition to the "current" schedule, there's also a "best" schedule which is updated any time we find a new schedule better than the previous best. This is to make sure that we used the best schedule encountered even if the algorithm happens to randomly climb uphill from the best solution while trying to find a deeper valley.

The final step is to analyze the red/blue balancing and to swap sides on the matches in the final "best" schedule to even out the balancing as much as possible. Notice that this swapping doesn't alter any of the other criteria, since no team moves to a different match or changes partners.

In my experience, the algorithm has done a pretty good job of making sure all teams have the same numbers of partners and the same number of opponents (which is the metric FMS reports), even at smaller district events.

[Alex2614]

At WVROX, we played just about every single iteration of the 24 teams on the field. Granted, running 24 hours will do that for you. We had a long cycle time, but still ran so that every team played against and with every team, multiple times.

As far as my experience, at most events, you will not see repeats. I think the only repeats we have seen on our team that I can think of were due to surrogate matches. At most events, we don't even get to see every team on the field (whether for or against), so we actually see no repeats.

[Koko Ed]

At the five events I worked at I can't recall any repeats.
In fact the last time I recall something like that happening was 2007 and I believe it caused FIRST to fix the scheduling algorithm so that wouldn't happen anymore.

[Richard Wallace]

Good memory, Ed. 2007 brought us the Match Schedule Algorithm of Death. Paul and John were very quick to bring the issue to my attention as a Week 1 FTA that year. It caused quite a stir, and everyone I have talked with was very glad to see FIRST HQ correct it.

Originally Posted by jvriezen

3. Good scouting should cause the best teams to get to play in eliminations, regardless of the shortcomings of scheduling.

This is generally true. However, better alliances are formed when the strongest teams seed highest. Scheduling algorithms were improved several years ago to help with this. The District-era trend toward 40-team fields and 12 match schedules helps even more.

Jim Zondag will gladly say more about this, if asked. He has a lot of data.

[rich2202]

Originally Posted by K-Dawg157

This puts some teams at a disadvantage. If they never get matched with the best robot, there score will probably never be that good. So for the teams that were paired multiple times with that robot, their scores will be so much better, and if they are continuously paired with robots better than them, their ranking will actually be better than they deserve.

That's life. With NFL Football, a Team mostly plays its own division. A good team in a lousy division could be ranked #1 in the playoffs, and all the benefits that comes with it.

Rankings only make a difference if you are one of the top 4 (who gets to do the picking from a wide open field). Aside from that, it is all scouting.

[Koko Ed]

Originally Posted by Richard Wallace

Good memory, Ed. 2007 brought us the Match Schedule Algorithm of Death. Paul and John were very quick to bring the issue to my attention as a Week 1 FTA that year. It caused quite a stir, and everyone I have talked with was very glad to see FIRST HQ correct it.This is generally true. However, better alliances are formed when the strongest teams seed highest. Scheduling algorithms were improved several years ago to help with this. The District-era trend toward 40-team fields and 12 match schedules helps even more.

Jim Zondag will gladly say more about this, if asked. He has a lot of data.

I think the event I remember the most glaring was Florida. Pink was scheduled four different times against Shark Attack who that year was a Pink killer and practically drove them into last place with their relentless defense.

[feverittm]

While I generally agree with the new algorithm and wistfully consider the possibility of playing against every team and with being allied with every team, I have seen personally a number of times when it appears the current algorithm breaks.

Last year we had a schedule where we were paired against the same team 3 times and never with them in our alliance.

This year it happened again with the two highest seeded teams (by unlucky coincidence), we were only paired with one of the top two teams once, but played against them multiple times.

I understand the algorithm and the concept of the optimization methods. However in this case it appears that the cost function must have really been skewed to generate these schedules. I need to build an analytic model of the cost function and see what exactly happened. Maybe when I get some time to breath again

Enjoy!