MatchMaker Scheduling Algorithm

By Tom and Cathy Saxton
Latest Revision: October 27, 2022 • MatchMaker Version: 1.5
© 2007-2022, Idle Loop Software Design, LLC

Update

In December, 2021, MatchMaker adopted a new station balancing algorithm created by Caleb Sykes that results in perfect balancing and is faster than the original method. In September 2020, MatchMaker improved support for small tournaments. An update to MatchMaker in 2017 balances station assignments to improved the team experience at the 2017 FRC Stronghold competitions (station balancing details).

Abstract

The algorithm used by FIRST to generate the qualification match schedule at the FIRST Robotics Competitions (FRC) is critical to the success of the regional and championship competitions. This paper discusses the desired properties of the match schedule, and an algorithm that finds near-optimal solutions in a practical time frame.

Match Format

The match format used at FRC competitions is currently three against three. So the match schedule consists of a list of multiple sequentially numbered matches, each with three "red alliance" teams and three "blue alliance" teams.

The outcome of these qualifying matches are used to determine team rankings, which in turn are used to determine which teams are invited to play in the elimination rounds which determine the winner in the robot performance category.

Note Prior to 2005, there were two teams per alliance.

Algorithm Specifications

There are several criteria that are desired in the match schedule.

Round Uniformity The matches should be divided into rounds, where each team plays exactly once in each round. The round boundary may occur in the middle of a match when the number of robots is not a multiple of 6.

Match Separation Teams need time for queueing and robot maintenance between matches, so we require a minimum gap between matches for each team. For maximum scheduling flexibility, this minimum gap is measured strictly by match numbers without regard to breaks, so the minimum gap is preserved even if schedule problems force the matches to be moved relative to the scheduled breaks.

Pairing Uniformity Teams naturally want to play with and against as many other teams as possible. It's typically impossible for all teams to see all other teams in match play, but it's desirable to minimize duplicates so that teams see as many different teams as possible. It's especially desirable for a given team not to have the same team as a partner more than once, nor as an opponent more than once. If match duplication does occur, it's preferable that a team that is seen twice is seen once as a partner and once as an opponent, rather than twice in either role.

Red/Blue Balancing Some arenas are not symmetric, offering some difference in experience between teams playing on the red and blue alliances. Most significantly, some arenas have the large video screen showing scoring and video of the current match are at one end of the arena rather than in the middle, so teams and spectators get a better or worse view of the screen depending on which side their team is playing on. So, we'd like the match scheduling algorithm to try to balance each team's appearance on the red and blue sides.

Station Position Balancing For the 2017 FRC Steamworks™ competition, there was a potential preference between the different alliance station positions. Version 1.2.2 added station appearance balancing, with an option to do it either by station number (the default) or with pairing stations mirrored, i.e. Red1/Blue, Red2/Bel2 and Red3/Blue1.

Surrogate Appearances In order to give all teams the required number of appearances on the field (the number of rounds) it is sometimes necessary to have some teams make an extra appearance. These are called surrogate appearances. The outcome of these matches count for the non-surrogate teams, but do not affect the standings of the surrogates. (Gracious Professionalism and good sportsmanship require the surrogate teams to compete as if their appearance did count.) For a properly constructed schedule, there will only be surrogate appearances if the number of teams appearances (number of teams multiplied by the number of rounds) is not a multiple of the number of teams in each match (currently six). There will be at most five surrogate appearances. For example, 32 teams playing 8 rounds requires 4 surrogates, but 32 teams playing 9 rounds doesn't require any surrogates. Historically, these surrogate appearances have occurred in the last round. Beginning in 2008, FIRST will be scheduling surrogate appearances in the third round.

The Problem

Every match schedule is going to be unfair; a fair, round robin style tournament format is completely impractical for this type of competition. It's unavoidable that some teams will have a schedule that gives them more weak partners and more strong opponents than other teams in the schedule. This is not only a scheduling algorithm issue, but a simple matter of not knowing in advance which teams will turn out to be more effective than others.

The goal is to implement a scheduling algorithm which provides schedules which maximize the qualities listed above and can be generated with an inexpensive personal computer in a brief amount of time, a few minutes at the most.

The Solution

The algorithm we have implemented to generate match schedules which meet these criteria uses a simulated annealing algorithm that is very efficient at finding a good solution to a class of problems where finding the optimal solution is impractical. In the case of a typical regional with 54 teams and six rounds, there are (54!)^6 possible match schedules (about 8.1 * 10^570), most of which don't pass most of the desired criteria. Simulated annealing examines a select subset of these possibilities and, if implemented correctly, finds a very good solution in less than a minute.

The various qualities of the schedule are implemented by different aspects of the algorithm in a way that largely eliminates most interaction and trade-offs between the criteria. Required rigid criteria are handled first, then more variable criteria are maximized without breaking the earlier criteria.

The algorithm begins by seeding the match schedule with a simple schedule: the teams are dumped in the schedule in random order for each 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, and likewise for station position balancing. Notice that this swapping doesn't alter any of the other criteria, since no team moves to a different match or changes partners.

Implementation

Getting all of this to work was an interesting and challenging programming problem.

We had to experiment with the scoring algorithm to get the pairing uniformity working correctly. Before we changed the weighting of the partner and opponent penalties, opponent duplication was being removed at the expense of partner duplication.

The constant in the exponential function that determines when a worse solution gets selected had to be adjusted to be strong enough to get the algorithm out of a local valley, but not so strong it jumps out of a valley before it finds the bottom.

The remaining 90% of the effort was spent on the last 10% of the problem: making it fast enough to be usable. The first implementation, which was both efficient and straight-forward, was too slow. Using the "best" quality setting required about 20 minutes to complete. By carefully optimizing both the permutation generator and the scoring function, we were able to speed it up by a factor of 10, dropping the time required for the best quality to a couple of minutes. The optimizations made the code run more quickly, but at the expense of code complexity. To ensure that the optimizations didn't change the results, we ran literally millions of test cases, comparing the results on the original implementation with the optimized version to ensure that the optimizations produced identical results to the more straight-forward implementation.

Notes

Minimum Match Separation Some care must be given when choosing the minimum match separation. Consider a tournament that consists of 42 teams playing some number of rounds. Since there are six teams per match, this means that on average, each team has to play once every seven rounds, for an average match separation of seven. Obviously, we can't require a minimum match separation greater than seven, since the average of numbers larger than seven can't be equal to seven. Said another way, such a restriction would require every team to appear later in the second round than in the first, which clearly can't happen. Even requiring a minimum match separation of 7 would restrict the schedule to require that every team appears in the same group of six in each round, so every team would have to play with the same five teams in every single round. As the minimum match separation is lowered, the algorithm gets more flexibility in how it permutes the teams within rounds and thus can better increase the pair uniformity. Setting the match separation to 1 says teams can be scheduled to play in back-to-back matches, which gives the algorithm too much freedom.

Red/blue Balancing With an even number of rounds, it is possible for a team to have a perfectly red/blue balanced schedule, but for an odd number of rounds, it's impossible for any team to have a perfectly balanced schedule. For example, with 9 rounds, the best schedule would be 4 on one side and 5 on the other, for a imbalance rating of 1. Also, any change to a team's schedule will always change that team's red/blue balance by an even number. So, for an even number of rounds, we seek a schedule with most teams having a red/blue balance number of 0, and as few as possible having a balance of 2. For an odd number of rounds we want mostly 1's with as few 3's as possible.

Station Position Balancing When the number of rounds is a multiple of the number of stations, it's possible for teams to have perfectly balanced station assignments. When the number of rounds isn't a multiple of the number of teams per alliance, e.g. 8 or 10 rounds for a 3-on-3 competition, the most balanced schedule is 2-3-3 (8 rounds) or 3-3-4 (10 rounds), in some order. With the new algorithm created by Caleb Sykes and added to MatchMaker version 1.4, all teams get the best possible station appearance distribution. More information.

Quality The algorithm allows the user to specify a desired quality. This simply determines the number of schedules that are generated and evaluated in the simulated annealing algorithm, as specified in the list below.

Fair: 100,000
Good: 750,000
Best: 5,000,000

Since the quality parameter sets a number of candidates, rather than a time to run, it will produce comparable quality schedules on different computers, just taking longer on slower models.

We have implemented this algorithm in a flexible, customizable way using platform-neutral C++ code (which could easily be simplified to straight C), and have made it available to FIRST for use by the FIRST community free of charge.

For evaluation purposes only, our program is available for download. For licensing, contact us at [info].