MatchMaker - Balancing Station Positions
MatchMaker program by Tom & Cathy Saxton
MatchMaker and FIRST
In 2007, we created MatchMaker, a tool to generate FRC competition match schedules that gives each team the opportunity to see as many different partner and opponent teams on the field as possible. FIRST has been using MatchMaker for FRC since the 2008 season and for FTC since 2009. The basics of what it does are documented in section 10.4.2 in the FIRST Steamworks™ Game Manual and more detail is available on the MatchMaker home page.
The Issue With Random Station Assignments
In January, 2017, Branden Gunn, an FRC alumnus and long-time mentor for many teams, brought to our attention that station assignments may matter to teams this year due to proximity to the boiler. In past years, station assignments didn't matter much, scoring was mostly done in the middle or far end of the field, but in 2017 the boiler is right next to one of the driver stations. Being in that first station makes it easier to see what's going on and direct loading fuel into the boiler. That prompted us to look at station appearance distributions for MatchMaker schedules. We expected station appearances to be unbalanced – random distributions are not even distributions – but it was much worse than we expected.
At a 9-round competition, we'd like to see each team appear at each station three times, a 3-3-3 distribution. Running stats on 1,000 75-team, 9-round schedules, we found those balanced distributions weren't the majority, in fact they weren't even the most common. In fact, for 9-round tournaments, on average only 8.5% of teams were getting 3-3-3. The most common distribution type is 2-3-4 (in some order) at 38.4%, followed by 1-3-5, 2-2-5, and 1-4-4, all more common than 3-3-3.
That's not a good thing! We expected things would be uneven, it was a lot of work to get other things like partner teams, opponent teams, and red/blue alliance appearances to be even, but that's just ugly. Maybe there's something wrong with MatchMaker, so let's do some math.
Let's Do Some Math!
If you want to assign a team to one of three stations for 9 matches, there are 3 ways to make the first assignment (A, B or C), then for each of those choices there are three choices for the second match, and so on, for a total of 3^9 = 19,683 choices. How many ways are there to assign a team so it has a 3-3-3 distribution? The team has to appear at Station A three times, and there are (9x8x7)/(3x2x1)=84 ways to do that. For each of those choices, there are 6 remaining matches, so there are (6x5x4)/(3x2x1)=20 ways to choose the Station B appearances. Once you've chosen the A and B appearances, there are only three unused matches left, so only one way to assign the Station C appearances. That leaves 84x20x1 = 1,680. So the odds of getting a 3-3-3 distribution at a 9-round competition with randomly assigned stations is 1,680/19,683 = 8.535%.
So, MatchMaker is within measurment error of being perfectly random on the 1,000 schedules we tested. What about the others?
That's good. MatchMaker is totally random, which it's supposed to be for assigning stations. However, as with pretty much everything else: random isn't what we want, we want even distributions.
When we discovered this issue, we developed a method for balancing station positions without altering any of the other schedule parameters. With this new balancing, MatchMaker now produces schedules that heavily favor the more balanced station appearance distributions. For the 1,000 new schedules we tested, on average 81.21% of the teams had a 3-3-3 distribution and the other 18.79% get a 2-3-4 distribution, in some order. While it's theoretically possible, we saw no team get a less balanced schedule than 2-3-4. (See the update below, MatchMaker now produces schedule where all teams get the best possible station appearance distribution.)
Below is the chart showing the new version stats.
Getting 81% of the teams to have a 3-3-3 distribution is a challenge. As adjustments are made to the schedule and more teams get there, they lock up the schedule. A 2-3-4 can't swap positions with a 3-3-3 team without messing up their schedule, so the schedule becomes blocked and there's no way to make the remaining teams perfect. Still we're very pleased to eliminate less balanced schedules like 2-2-5, 1-4-4, 1-3-5, 1-2-6, etc., which together made up 53% of the random schedules.
The Even Better News
The situation is even better for competitions where the numbers of rounds isn't a multiple of the number of stations. For a 10-round FRC competition, the most balanced station distribution for a team is 3-3-4, in some order. The great thing about that is even when the schedule is mostly balanced, unbalanced teams can swap stations with balanced teams. For example, swapping teams at stations B and C to change one team from 3-5-2 to 3-4-3 while changing the other team from 3-3-4 to 3-4-3. With this much flexibility in adjusting station assignments, MatchMaker is able get, on average, 99.75% of teams at 75-team, 10-round competitions at the optimal 3-3-4 station distribution with the remaining 0.25% getting the next best distribution: 2-4-4. (Update, December, 2021: now it's 100% balanced for all schedules.)
Below is the graph for the 10-round case.
The situation is similar for 7-round and 8-round tournaments, with 6-round tournaments looking more like the 9-round case.
Update - 2021
Thanks to a new method created by Caleb Sykes, station balancing is now perfect for all schedules. Testing with over 10,000 schedules shows that with MatchMaker version 1.4, all teams get the best possible station appearance balancing.
FRC Steamworks Schedules
We discussed the issue with FIRST, and the Game Design Committee decided it was worth addressing. FIRST FRC Steamworks will use a new version of MatchMaker that balances station appearances by boiler proximity without compromising any of the other schedule goals.
For FRC Steamworks, MatchMaker balances by proximity to the boiler, so between stations A (Red1/Blue3), B (Red2/Blue2) and C (Red3/Blue1). There's a MatchMaker setting that controls whether balancing is done based on that scheme or by station number, so it is flexible for use in future years or other competitions.
The old and new versions of MatchMaker are available for anyone who wants to try them out.
Visit the white paper to learn more.
© 2007-2022, Idle Loop Software Design, LLC
|©2000-2023 Idle Loop Software Design, LLC. You may not copy or reproduce any content from this site without our consent.|