Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

Bill & Sean,

If I remember correctly, this suggestion from Bill was about giving all robots on a victorious alliance a qual score increase equal to the total points earning by the alliance in the match they won. It was not a suggestion that we attempt to track the number of points scored by each individual robot. This would take the place of giving each winning alliance member 2 qual points.

Am I remembering correctly?

Blake

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

@ Blake:
How do you get a tri_match (3 matches) in the time it takes for 2 regular matches? If it is proposed to run these matches back to back with little (or no) down time, I think that is a far worse factor than the fewer opponents. Repair/downtime is essential to being competitive, and often, even functioning. If you have no time to repair, then if something breaks in the first match of the set, then you're essentially doomed (along with your partners) in the next two.
If that factor was removed, then you'd be running identical number of matches to the previous style, and as shown (with the exception of 9 matches and 32 teams), you'd get less repetition, particularly in the larger competitions where the repetition was half of the "tri_match" format or even less.
And Farmville did only get three qualification matches per team, I'm positive about it. Each team also got a few practice rounds in during the morning, and 24 of the 29 got at least one match in the eliminations (their alliance's at least got two).
And my comments weren't that you two were friends, but rather that because he has met you, that it is likely he's involved with Vex in Virginia to an extent, and likely went to Farmville.
Finally, I don't think there's six hours of actual playtime for qualification matches once you factor in opening ceremonies, inspection, practice matches, lunch, and alliance selection. At least not from what I've experienced at my previous one-day vex events.
And yes, I think the defense would change his results, given that you face each team twice as a defender. You could be the best at scoring Goal X, but if Defender Y can shut down Goal X, you're likely to pick up two losses (and you're less likely to face Defender Y twice in the current format).

@Billw
The results are curious, as I've been to an FRC competition (in 2006, so not with last year's algorithm) with around 32 teams, and with 9 qualification matches (and with 3 teams per alliance, so even more total partners), and we had far less repetition than that. Perhaps FIRST's [old] algorithm is in fact not truly random, but written to avoid repeat match-ups whenever possible.
In your simulation, it does show at the 32 team (which is moderate sized, only a couple vex competitions were larger), that repetition in your system is not much worse, but with the likely outcome of the 3-6 match range (based on my experience with FVC), it is still slightly worse, but perhaps in the tolerable range. But when applied to something like the Championship event in Atlanta, which had hundreds of teams and each only had 4 qualification matches, it would be a much higher repeat range.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

Let's suppose that teams would ideally play nine matches across a 4.5 hour window. This means that there are nine trips to/from the pits, nine attempts at getting drivers/coaches on the field, nine attempts at making sure the batteries are charged and plugged in, nine attempts at obtaining and correctly inserting crystals. That is a lot of coordination with a lot of room for mistakes--all of which I witnessed this past season over and over when only playing 3 or 4 times. (Nine trips in Atlanta might not even be physically doable--given the distance.) So, I had this idea that it might simplify things if teams played three successive matches with two minute breaks in between. This is not unlike what occurs during the finals. I also recognized that some robots will fail. Therefore, I proposed that the previous teams remain at the field and be available to fill in for no-shows and broken bots. Even though this system adds only a minimal efficiency gain (.28 vs. .37 matches per minute by my calculations), you greatly eliminate the "herding cats" problem of running nine matches.

Sean, I understand that you do not want to play any repeats, and if you can change the scoring to a "total alliance points" (not total per-team points) method, there is practically no benefit to doing so. I do believe, however, that there is a benefit of only having to "assemble the troops" three vs. nine times. So perhaps it would be possible to mix the teams playing on the two fields and create a no-repeat partner system that still plays three matches in relatively quick succession.

Blake, do you know what the total number of no-repeat partner combinations is for a given number of teams? If so, how many teams are necessary to enable nine no-repeat matches per team?

Although I am not writing the code, it seems to me that you could solve this algorithmically by tracking teams prior partners and removing them from a list of teams still available and then randomly selecting from that pool. I do think it becomes much more complex if you do not have sufficient teams to fill out the schedule with entirely unique partners.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

Given n teams, the number of no-repeat partner combos is :
(n-1) + (n-2) + (n-3) + ... + 1

To get 9 unique partners, you need at least 10 teams.

# of combos//pairings listed (teams are labeled 1 through 10)
9 ///////////// 1-2, 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, 1-10
8 ///////////// 2-3, 2-4, 2-5,... 2-10
7////////////// 3-4, 3-5,...3-10
...

1////////////// 9-10

Add up the first column, and you get 45 pairs. Since 4 teams (2 pairs) play a match, you need 22.5 or 23 total matches.

The hard part is not in choosing unique partners -- it's in choosing unique opponents. Since each team plays 2 opponents, you're twice as likely to see a given opponent. Also, pre-setting the condition of avoiding repeat partners first gives less freedom in choosing opponents.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

I have been looking at this as system of entirely unique groupings where none of the four participants has had any of the others as a prior offensive partner or defensive opponent.

A pair can be solved by using the standard combinatorial formula: N! / P!(N-P)! where N is the total number of elements and P is the number of elements in each grouping. The problem is that it does not work for P greater than 2 because it does not enforce the restriction that members of a grouping may appear only once with any other member.

I don't know of a formula that answers this question, although I would expect it exists. In any case, I believe it would show that for N=8, P=4, the result is 2; for N=16, P=4, the result is 12. My brain is not wired to figure it out via brute force out any further than that. And given the way the combinatorial formula works, I very much doubt that I could derive the underlying relationship on my own.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

By removing the overhead associated with bringing four "new" teams onto the field every match, I predict that one would see a speed-up of of the sort I put into my assumptions.

Building machines sturdy enough to survive 3 matches in a row would seem to be a fairly reasonable criterion. We are supposed to be in pursuit of excellence, not mediocrity.

Allow time-outs for repairs and remind teams to build modular machines that can be repaired in the duration of a timeout.

I'll need to dig into this... My recollection is different, but we did some unusual things (like filling in for at least one team that was a no-show for a match). Those might be clouding my recollection.

Predicting 6 hours of qual time in a long one-day tournament is a number that came out of another thread.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

This is pretty much what I am doing, along with trying to maximize the time between any given team's appearances on the field.

It is working pretty well except for a few odd results.

Blake
PS: Recently I have been making trips to SC for family medical fun, and I just got back from a "delightful" week of heat and humidity at Boy Scout camp, so I didn't do much with the software last month; but I should be able to clean up the output enough before July is over to be able to post some of the match scheduling routine's results.

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

Some day, I'll run this experiment just to see who guessed correctly - I'll bet you a favorite beverage on it :)

Why don't you beat me to it while I am working on my match scheduler??? :) :)

Blake

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

If you are asking how many unique two-team pairs can created from a pool of N teams, the formula for what MM described is
(N/2)*(N-1)

For N = 4 the pairs are AB, AC, AD, BC, BD, CD (six pairs).

In this case each team can be paired with any of three allies; but with N=4, for each ally of A, there is only one opposing alliance available.

With larger N, there are more opponents available, so once all possible pairs of teams have been on the field, when they start going out again, the scheduler needs to pick a new opponent alliance for them to face.

If you want to have each team be in 9 matches with new allies and totally new opponents in each match, you need not only the 10 teams required to supply 9 allies, but you also need 18 more teams to supply 9 pairs of no-repeat opponents. That adds up to 28 teams.

Blake

Re: [FVC]: Analysis Shows Improvement Possible in Ranking System
 

Blake,

I think we are talking about the same thing:

The formula above is just the simplified form (which can be used for pairs only) of the more general formula I provided that allows any number of elements in a group:

In any case, I am still puzzled by this:

If we constraining the problem to no repeat allies or opponents, then each team must be grouped with 3 entirely new allies/opponents in each round of matches. This means that for nine matches: 9 * 3 + 1 = 28 teams will be required. This is just a simplification of the formula (algorithm) you supplied and, as such, works out to the same result.

Unfortunately, however, I am not sure it is that simple. Take, for example, the question of how many teams are required to play 2 matches: 2 * 3 + 1 = 7 teams. The first match would be 1-2-3-4, the second 1-5-6-7. The problem is that there is no way to form any additional matches for teams 2-7 that will not result in some previous partner being included--obviously not what we had in mind.

The above formula would also predict that 5 matches require 16 teams, but I can show that at least 12 unique matches are possible. So it is obviously not useful in this setting. The twelve matches that I can derive, however, are neatly divided into three rounds of four matches each. (There may, in fact, be more possible matches--up to 16 theoretically--but I don't have the patience to try and sort through the combinations.)

In any case, as I have played with this in my head over the last couple days, I am suspicious that it will require 64 teams to reach 6 unique matches for each team and 256 teams to reach 9 matches.

The reasoning is that even if I add 16 more teams to the existing 16, I can't create even one additional match beyond the 12 + 12 = 24 that I know are possible. This is because all possible combinations within each group of 16 have been made. To form another group of four, I need to draw two members from each group, but they have, of course, already been matched.

It is not until I have four subsets of 16 teams that be unique members can be drawn from each to create additional matches. At that point, I think the same formulation that gives 12 combinations in 16 teams can be distributed across the 64 teams to arrive at an additional 3 matches for each team, giving each team 6 unique matches.

If this logic holds, the next three matches would require 64 * 4 = 256 teams.

I am hoping that you or someone else will prove me wrong, but it appears to me that it may, in fact, require quite a few teams to reach the nine match goal.