Random Match Generator Challenge

[Mark Hamilton]

Last year FIRST changed the algorithm to garuntee teams had a certain minimum amount of time between matches (I heard 10 min. but I'm not certain). This was a good idea, but had an unexpected consequence. After the first round of matches was randomly allocated, the computer had to start picking a second round. Unfortunately, the 10 minute rule meant when it came time to pick a second round, instead of choosing from the large pool of teams, it could only pick from the small pool of teams that had had 10 minutes, but hadn't been assigned to another match. The only teams that fit that criteria are the teams that were in the same match roughly 10 minutes ago. This meant teams saw the same teams over and over again throughtout the competition.

The Challenge: Design an algorithm in the language of your choice (or even just pseudocode) that creates a random distribution of teams, but still allows for each team to have a predetermined minimum amount of time between matches.

Remember that FIRST will probably want to implement this randomizing function in Filemaker Pro, so it needs to be done without extremely exotic math functions.

Come up with a working solution and I'll try to make a Filemaker Pro script out of it and try to talk the people at FIRST into using it. If possible please include a sample output with your idea.

[Andrew]

One of the ideas that was mentioned last year when this problem manifested was to generate a list of matches that had all of the good characteristics (time between matches, good "randomness" of matches) for n teams, where n = 24, 25, ...55, 56, 57, ...

Then, at the competition, randomly map the teams at the competition to the match list.

In other words, Generic Team 1 = Team 356, Generic Team 2 = Team 400, Generic Team 3 = Team 25, etc.

[WernerNYK]

FIRST will not be using Filemaker Pro this year, I know that for a FACT They will also have new scoring/field control/display software as well, hehe.

[Brandon Martus]

Didn't Nate Smith come up with a modification of the system that was used at a few off-season comps?

[Allison K]

Originally Posted by Andrew

One of the ideas that was mentioned last year when this problem manifested was to generate a list of matches that had all of the good characteristics (time between matches, good "randomness" of matches) for n teams, where n = 24, 25, ...55, 56, 57, ...

Then, at the competition, randomly map the teams at the competition to the match list.

In other words, Generic Team 1 = Team 356, Generic Team 2 = Team 400, Generic Team 3 = Team 25, etc.

I am definitely not a programmer, so I couldnt get it into computer language, but last year in math I figured out a pattern for generic numbering where no one team was on the field with any other team more than once, and each team has at least two other matches between theirs. I don't remember where I put it, I'll have to find it.

The pattern worked for any number of teams I believe above 48 (maybe 42) but only held for 8 or 9 rounds of matches. The more teams there were the more matches it held up for.

It took me a long time to do since I wrote it all out by hand. Like two months.

Allison

[EDIT]

To Mongoose: The only regionals I've been too had (I think) 54 and 62 teams, but I'm from Michigan where there's a rather large concentration of teams, so I guess I don't know the average regional attendance.

General Comments: That two months was only 50 minutes a day minus the weekends (no school) minus the time it took to check homework (wouldn't look too good if I was not doing classwork, especially if I had forgotten to do my homework) minus quiz days and test days and the days I needed to pay attention and the days she got supispicous about me writing so many "notes."

I found what I worked out for 48 team attendance. If anyone wants I can either scan it in or quickly type it in excel and post it.

[/EDIT]

[Mongoose]

I know it's a good exercise/challenge, but wouldn't it be more practical for them to just work it out by hand? It seems like it'd only take an hour or two, which equates to less than one can of (insert preferred caffeinated beverage here).

Allison: I've only been to the PacNW regionals, but I'm assuming each regional has roughly 40 teams? The PacNW had something like 38 last year.

[Jeremy_Mc]

Actually there are some regionals that are sub-35 (Detriot has 32 I think...).

I have an algorithm that would work but VB is being stupid and will not let my pools fall into place like they do on paper. I've worked it out with 34, 37, 44, and 53 teams and it works every time. I haven't worked it out as far as the total number of matches needed, but then again I don't remember how many matches there are in seeding. Can anyone help me out?

[Jeremy_Mc]

I've attached a simple graphic of my algorithm to this post.

It's not the easiest thing to work out/comprehend, but it will work. I worked it out a bunch of different ways and it works out fine every time. The graphics uses a small dataset (23 teams) but I just wanted to illustrate the way to work it, and some of the problems that might arise from using it.

If there are any questions/comments please PM me or post here or something...

I'm sure this would be easy to work into a program of sorts (using linked lists or arrays), but I'm simply too lazy to worry about doing it in VB or C.

[edit: forgot the file...]

[Swan217]

Originally Posted by Brandon Martus

Didn't Nate Smith come up with a modification of the system that was used at a few off-season comps?

I agree - Nate's system worked much better than FIRSTs.

[danielkitchener]

Are we assuming:
2 minutes per match
1 minute between matches for setup/cleanup
4 teams per match?
Also, how many matches per team?
If I have time tonight (unlikely) I can code it in C++ in an hour as long as I have the above information

[Jeremy_Mc]

Originally Posted by danielkitchener

Are we assuming:
2 minutes per match
1 minute between matches for setup/cleanup
4 teams per match?
Also, how many matches per team?
If I have time tonight (unlikely) I can code it in C++ in an hour as long as I have the above information

The FIRST site says that each match has 2 minutes per match and one minute between for robot setup and takedown. I'm guessing each match is ~5 minutes more or less...

And yes 2vs2 and I'm not sure how many matches are in seeding That's something you'd have to ask FIRST.

[dez250]

Originally Posted by Mongoose

I know it's a good exercise/challenge, but wouldn't it be more practical for them to just work it out by hand? It seems like it'd only take an hour or two, which equates to less than one can of (insert preferred caffeinated beverage here).

Allison: I've only been to the PacNW regionals, but I'm assuming each regional has roughly 40 teams? The PacNW had something like 38 last year.

As a regional scorekeeper, i would say no. Because when you have only a few hours to not only get the system set up in technical details, you also have to get the physical system set up also, and with some regionals that have up to 50-80 teams there, doing the match list by hand and then inputing it all into the scoring system would take close to a days worth of work. And that is not including the physical set up time.
Mike

P.S.~ Yes Nate S. did come up with a plug in or last years game, i dont know if it will work this year, but it was a great addition to the off season events, along with the best out of 3 finals plug in.

[piotrm]

Originally Posted by Jeremy_Mc

I've attached a simple graphic of my algorithm to this post.

It's not the easiest thing to work out/comprehend, but it will work. I worked it out a bunch of different ways and it works out fine every time. The graphics uses a small dataset (23 teams) but I just wanted to illustrate the way to work it, and some of the problems that might arise from using it.

If there are any questions/comments please PM me or post here or something...

I'm sure this would be easy to work into a program of sorts (using linked lists or arrays), but I'm simply too lazy to worry about doing it in VB or C.

[edit: forgot the file...]

here is your algorithm as far as I understand it: (its in perl, accepts number of teams and number of matches as command line arguments)

my ($teams, $matches) = @ARGV[0,1];

if ($teams < 16) {
  die "need at least 16 teams";
}

my @teams   = 1..$teams;
my @matches = 1..$matches;

my @pools;

while (my @slice = splice(@teams, 0, 4)) {
  push @pools, [@slice[0,1], @slice[2,3]];
}

foreach my $match (@matches) {
  print "match $match: ";

  my $pool1 = $pools[0];
  my $pool2 = $pools[2];

  my @red  = splice(@$pool1, 0, 2);
  my @blue = splice(@$pool2, 0, 2);

  my $off = ($match % 2 ? 0 : 2);
  $red[1] = splice(@{$pools[1]}, 1 + $off, 1) if not $red[1];
  $red[0] = splice(@{$pools[1]}, 0 + $off, 1) if not $red[0];
  $blue[1] = splice(@{$pools[3]}, 1 + $off, 1) if not $blue[1];
  $blue[0] = splice(@{$pools[3]}, 0 + $off, 1) if not $blue[0];

  print "@red vs. @blue\n";

  if ($match % 2) {
    push @pools, [@red];
    push @pools, [reverse @blue];
  } else {
    push    @{$pools[-2]}, shift @blue;
    unshift @{$pools[-2]}, shift @blue;

    splice @{$pools[-1]}, 1, 0, @red;

    splice(@pools, 0, 1);
    splice(@pools, 1, 1);
  }
}

It seems to make a nice match list. I have not yet analyzed to results are far as how good the match listing is of this method. Will see.

[Jeremy_Mc]

Originally Posted by piotrm

here is your algorithm as far as I understand it: (its in perl, accepts number of teams and number of matches as command line arguments)

[...]

It seems to make a nice match list. I have not yet analyzed to results are far as how good the match listing is of this method. Will see.

Great job. I thought about Perl, but I really have very limited experience with it.

Hopefully FIRST will take this into consideration