"Random" match Schedules

[Tom Saxton]

I've done a thorough analysis of the "perpetual opponent" algorithm and implemented a better way of scheduling matches. The results and description of my algorithm are in a white paper here:

http://www.issaquahrobotics.org/MatchMaker/

In looking at the Friday schedules for Florida, Bayou, and Great Lakes regionals, it seems that the "random" method may improve the problems with opponent duplication, but sacrifices both partner duplication and minimum gap between matches. Lots of teams have as few as two intervening matches between their closest matches, which isn't much time to get back in line. I won't know for sure how the algorithm does over the full schedule until Saturday's schedules are posted.

[jgannon]

Originally Posted by Richard

Looks like Pittsburgh successfully chose the "random" match generation mode, rather than "perpetual opponent".

I'm here in Pittsburgh, and it's really not looking like that for some teams. We saw a lot of the same opponents and partners several times today, and I know we didn't get the worst draw. In general, it looks a little better than last week, but it doesn't feel like it's outside the bounds of statistical error. However, I'm pretty much at peace with that. It wasn't an uncommon sight for us in previous years. The biggest deal for me is that we never were allied with a team number greater than 677. (For historical purposes, I am on 1743.) Why do we never get to play with a 1038, or a 1249, or a 1629? These teams are among the best here... team number is not a factor. I'd also love to play against a strong pair like 291/306 or 375/379, but it's not going to happen. It *can't* happen.

There's a big difference between random and arbitrary. While the algorithm may be improved, it's definitely not random, and to call it that is misleading. I expect that this is how it will be for the remainder of the season, but without a compelling argument in favor, I really would not want to see this algorithm back next year.

[Tom Saxton]

Here's my analysis of the Pittsburg schedule so far.

http://www.issaquahrobotics.org/Matc.../pit-fri.shtml

It's similar to the other week-two regionals that I've looked at with lots of teams having matches very close together and still more duplication than is necessary.

[Michael Corsetto]

Man, I'm really nervous as to how SVR and Davis match pairing is going to turn out. I never got to play with/against a lot of the great teams at PNW, and I fear that even with this "improved" algorithm we still we only be seeing 1/3 of the competition at our next events. Which to me just takes all the fun out of seeing how our robot performs with and against a wide variety of strategies. I distinctly remember doing scouting review on friday night at PNW and not recognizing half of the robots our team had taken pictures of, and I feel like I missed out on all the awesome work the other teams did. Where is the inspiration in seeing the same robots over and over?

I would really like to know how FIRST rationalizes lower team numbers as "better", because in our 11 year team history we have yet to win a regional (emphasis on the "yet" ) So please, please FIRST, bring back truly random matches. I understand the constraints that need to be made so that teams are not having back to back matches, but other than that, just let the teams play.

I think FIRST made a step forward with week two, but they already took two steps back at week one, so IMO they still have a little ways to go.

Mike C.

[AdamHeard]

The algorithm worked pretty well at LA.


except being against 330 match 1, 254 match 2 and 968 in math 3.

The only three matches we were running before the banebots gearboxes completely siezed up.

[dtengineering]

Originally Posted by Rex114

I would really like to know how FIRST rationalizes lower team numbers as "better", because in our 11 year team history we have yet to win a regional (emphasis on the "yet" )

I think there is still some ambiguity as to whether FIRST has actually stated that lower numbered teams are "better"... certainly they did not fare any better under the scheduling system for the first week regionals... but that could well be due to the scheduling system itself.

As for determining what a "better" team is, I know you mean in the sense of winning qualification matches, but the way you guys helped out the rookies next to you (for those who don't know, they not only lent them their robot cart, but then went and built a new one and gave it to the rookies) and played at PNW certainly makes you one of the "better" teams in the big picture. I've already forgotten which teams, exactly, won the championship, (although the final match has got to go down as a classic) but it will be a long time before I forget the way you welcomed a new team to FIRST.

Well done, and I hope you get to see a wide variety of teams at your future regionals.

Jason

[Tom Saxton]

The LA regional is better than the other week two regionals I've looked at.

http://www.issaquahrobotics.org/MatchMaker/la-fri.shtml

It still has issues with very short match separations and partner distribution is reduced, but the opponent duplication is better.

[MariaChristineK]

They call this kind of scheduling random?!? At Pittsburgh, we faced the same teams in almost the same alliances numerous times! It is much worse than past years...What is going on?

[artdutra04]

Originally Posted by MariaChristineK

They call this kind of scheduling random?!? At Pittsburgh, we faced the same teams in almost the same alliances numerous times! It is much worse than past years...What is going on?

At 35 teams, Pittsburgh Regional is a small regional, and the new randomizing algorithm needs a certain number of teams to be effective. With a large regional, you have a much larger pool of teams to randomly draw from for generating the match schedules than a small regional, which is why Pittsburgh has many similar alliances.

Small number of teams at a regional = small pool of potential teams to compete in any match.

[GaryVoshol]

It appears that neither the new nor the old algorithm are random, but are different versions of controled permutations of team assignments. There is still seeding based on team number. The first step is to divide the team list into 3 pools by increasing team number. Then to create each alliance, a team is selected from each pool, although assignment to Red or Blue appears to be random. Each alliance always has one team from the lowest third of numbers, one from the middle, and one from the top. The old algorithm stressed maximum separation between matches, which created the maximum number of repeat partners and opponents. The new algorithm has relaxed that separation a bit, but it appears that smaller regionals with fewer matches per round still hit up against the limits.

The biggest mistake, in my opinion, was decision to create the 3 pools in the first place. It completely eliminates the possibility of super-strong alliances consisting of all long-term veterans, which is probably the intent. For example, there could never have been an alliance of 33, 67 and 70 at GLR - regardless of how well those teams did or didn't perform. This penalizes teams that are in the lowest-numbered third that do not happen to have a strong robot that year. We all know there are teams that go through rotations of personnel, or have a fatal design flaw that isn't discovered until it's too late to correct, or don't perform as well as usual due to any number of reasons. Worse, this gives an extreme advantage to great performing teams in the 2nd or 3rd pool, who are now always paired with a veteran.

I hope they come up with something different for Atlanta, because almost everyone who comes to the Championship can be considered a veteran, or at least should be a well-performing team. Even the rookies that get there because they were in a winning alliance, or because they are Rookie All-Stars, deserve to be considered equal competitors.

[gblake]

Originally Posted by artdutra04

At 35 teams, Pittsburgh Regional is a small regional, and the new randomizing algorithm needs a certain number of teams to be effective. With a large regional, you have a much larger pool of teams to randomly draw from for generating the match schedules than a small regional, which is why Pittsburgh has many similar alliances.

Small number of teams at a regional = small pool of potential teams to compete in any match.

AD4 - I think it is worth noticing that with 36 teams in a regional, and with no other constraints other than minimizing repeat allies and opponents, it is possible for a team to play a full 7 matches without ever seeing a repeat among the other 5 robots on the field.

In a 36 team Regional one should expect to have to hustle between matches because there are fewer teams that need to go out on the field before your own team is "up" again; but there is no reason to expect to see lots of repeat allies and opponents just because "only" 36 teams are present.

When you choose to maximize the smallest time between each team's matches, that starts to make things hard. When you allow teams to see other teams twice on the field, so long as that other team is an ally once and an opponent the other time; your ability to schedule matches starts to improve,,,

Bottom line: A small population of teams is not a reason to say that alliances will repeat or nearly repeat often. On the other hand, using a method that forms alliances from small medium and large team numbers does throw a pretty large wrench (i.e. constraint) into things....

Blake
PS: Once a match scheduling algorithm (suggested in this forum or elsewhere) that doesn't depend on team number is implemented; it is a trivial exercise to run it once for each possible number of teams from 1 to 100. After those results are reviewed and found correct, at each/any regional, the organizers just randomly assign the participating teams to fill the slots in the appropriate pre-generated schedule. Done.... No one will know who their opponents and allies are until the results of the random assignments are announced. Everyone will know the patterns in the match schedule beforehand; but who cares? The "worst" that could happen is that they detect a flaw in the algorithm ahead of time....

[Andrew Blair]

Okay, big Pittsburgh feedback post.

First of all, though Pittsburgh is a small regional and it's quite reasonable to say that there will be a few teams who play against the same teams all the time, it was pretty bad. It didn't affect us too much, but we were with or against 1629 in ~75% of matches, and others often as well. We didn't mind it, and I still thought our match scheduling was okay, but for others, not so much. I saw at least thee teams go back to back or every-other-match a couple of times, and they were still playing the same teams. Again, we didn't notice it alot, but other teams had a hard time.


Rookie advantage time. Our choosing alliance partner, though an excellent team that was alot of fun, not to mention having built their robot in only four weeks, and shaving 80 pounds practice day, was seeded #1 alliance.
Their robot however, was not so good. Literally a box bot, they could not score, descore, or climb too many ramps effectively. At least one qualifying match they did not run at all. So, their contribution to their seeding was limited to the few times that they climbed ramps. It appears that they could not have seeded any lower if they wanted to. They were basically in the top eight regardless of if they ran or not.

In the long run though, being first alliance actually put them at a disadvantage. They had first pick, and could pick what they felt was the best possible alliance partner from the beginning, but they could not pick again until last. So, effectively, they had one excellent hybrid robot, an excellent defending robot(#1990, thanks!), and themselves. They had no chance to pick a scoring robot second choice(all gone by that time), and as a result, they had one robot who could score and ramp, and two screening robots, only one of which could quickly climb the ramp. Had they been seeded lower or had been picked, they would have been on an alliance with two strong robots to start with. Their alliance didn't really have a chance.

And therein lies the problem with a non-random match selection process. A similar thing happened another alliance, who was a rookie box carried into the top eight by "random" selection. There are consequential reasons why rookies should not be helped into the top eight. If they score and win their way in, more power to them. However, if they do not, they actually stand a better chance of winning if they are not put there.


Again, we had a great time and I had more fun than I've ever had at a regional I think, but when the cards are stacked against an alliance with no way to reverse it, it's not really a good thing.

[Tom Saxton]

Here are the stats on the Pittsburgh regional schedule. As previous posters have noted, the gaps between teams' matches got pretty tight, with one team having to play back-to-back matches. There's rampant duplication among both opponents and partners, with teams 123 and 314 paired as partners in half of their matches. Teams saw between 23 and 29 of the other 35 teams.

I've posted a white paper on the scheduling issues and a better solution to the problem.

Even in a small regional, a much better schedule is possible, with a minimum match delta of 4, no partner duplication, much less opponent duplication and teams get to see between 29 and 34 of the other 35 teams.

[Jeff Waegelin]

My team, 830, managed to get matched up against both Martian teams 3 times apiece at GLR. We played 2 matches against 494, 2 against 70, and one against both of them. Somehow, that doesn't seem quite right...

[65_Xero_Huskie]

Originally Posted by Jeff Waegelin

My team, 830, managed to get matched up against both Martian teams 3 times apiece at GLR. We played 2 matches against 494, 2 against 70, and one against both of them. Somehow, that doesn't seem quite right...

Yea, we played 1503 3 times in a row, which is VERY strange because there were 60 teams there. So....Can someone clarify why this is happening?