F3J Flight Matrix Generation - RC Groups
Sep 29, 2011, 12:17 PM
Registered User
Discussion

F3J Flight Matrix Generation

As many of you know I regularly run F3J events and handle all the matrix and scoring tasks. In the past I have always generated the flight matrix using a random assignment and rarely have any complaints. However, I am now looking at generating the fairest possible matrix for the US F3J Team Selections and have run a number of tests and often see anomalies in the matrix where a pilot flies against another an inordinate number of times or very few times. I ain't the sharpest pencil in the box, so I could use some suggestions on how to improve the matrix from some of the smart math people in the group. I am a programmer so if I understand the algorithm I can program it..

Here are the constraints:
1. There are 10 teams
2. Each team consists of 4 pilots (if there are less than 4 pilots a BYE will fill the empty slots).
3. Each pilot will fly once in a round (so there are 4 groups in a round)
4. Pilots on the same team are protected and will never fly against another team member.
5. We will schedule 24 total rounds in the matrix

Here is what I have attempted so far:
1. Pure random – for each round I process each team. On each team every pilot has a fixed pilot number between 1 and 4 (including BYES). I then compute a random sequence of the position numbers 1-4 and assign the flight group based on that sequence. Repeat for each team. When all teams have been computed for a round I go on to compute the next round.
2. Random with statistical preference – I do the above, but I calculate a factor to use in determining the variance in the matrix and run 1000 trials and select the one with the least variance. To do this I compute and record how many time each pilot flies against the other pilots. For each pilot I compute the standard deviation of these numbers. I then add all the pilots standard deviations together and compute the average standard deviation for the entire matrix. I pick the matrix that generates the lowest standard deviation in 1000 trials. Generally I see a minimum standard deviation of about 1.28. Some individual matrix SDs are 1.9 or so.
3. Random with statistical preference and permutiations – for this approach I calculate all the possible permutations of the sequence 1-4. Then for each team I generate a random sequence of those permutations (1-24). I then assign the group position for each pilot in a round based on that teams random set of permutations. I then do the same as #2 and calculate the minimum SD of all the matrixes and select the lowest. Interestingly this approach was nearly identical in minimum SD as the #2 approach.

It just feels to me like there should be a better way to get a more even distribution – I’m hoping one of you math heads out there can help me improve the matrix…

If not – it is what it is and I did my best…

Jim
Sep 29, 2011, 01:11 PM
Registered User

Matrix

Have you seen this
It is widely used and FREE

http://www.gliderscore.com/
 Sep 29, 2011, 02:00 PM Registered User Yes - but I already have a great web based scoring system where pilots can put their scores in on their mobile devices and the scores and results are instantly available on the web for everyone to see. I just want to improve the matrix. Jim
 Sep 29, 2011, 04:04 PM launch low, fly high Jim, The below is one possible algorithm for making a flight matrix that may meet your needs a bit better. !comment: store a matrix of the conflicts (pilot vs pilot count) Random draw for the first pilot in a flight group (heat). 1) If number of pilots on a team as yet undrawn = number of heats left, then first draw a random pilot from that team. 2) For the second pilot draw in a heat, look at the conflict matrix with respect to the pilot already in the heat and select the pilot with the minimum number of prior conflicts. Use #1 above if applicable. If multiple pilots have the same conflict count, do a random draw amongst them to select the second pilot. 3) For the remaining pilots in the heat, sum the number of conflicts for the remaining pilots with respect to the already drawn pilots. Use #1 above if applicable. Pick the pilot that has the minimum conflict count with respect to the pilots already drawn. If there is more than one pilot with the same summation, do a random draw amongst these pilots. Repeat until the heat draw is complete. Repeat for the remaining heats in a round. Update the pilot conflict matrix Repeat for the number of rounds desired. An alternate method that can result in better overall matrixes is to sequentially build all of the heats for a given round in parallel rather than in series as is described above.... Extra credit to pick the initial two pilots in a heat by looking at the conflict matrix for the lowest number, assuming the #1 constraint. Again, random draw if there are multiples. The next fun part is to optimize this draw. Save what you finished with, and sum the # of times a pilot flies against each other pilot. You will end up with a histogram. For example, you might have 4 instances of pilots seeing another pilot 3 times, 17 instances of pilots seeing another pilot 4 times, and 5 instances of pilots seeing another pilot 5 times (just making numbers up right now, the counts should be much higher than this). After saving the initial draw, you repeat and then compare the old vs new histogram. You are looking for the tightest grouping. Depending on the number of rounds flown, you may want to update your "best" draw via minimizing the number on the low side or the high side of the median pilot conflict count. Ideally, you do both! With a low heat count/round, this can be difficult to do... Certain pilot #s and heat/round # can result in perfect matrices (everyone flies against each other the exact same number of times). An algorithm such as the above can produce a flight matrix that is orders of magnitude better than a simple random draw. The above methodology is what I put together about a dozen years ago in order to have a "fair" matrix for US team selection events. I have it in Excel/VB, but it is not very user friendly as I wrote it solely for myself. I'm a hack programmer, and just wanted something that produced results.
Sep 29, 2011, 04:36 PM
Play loud, Fly high

Matrix generation

Jim, give me a day or two to think about how to describe this, (currently on meds for a pinched nerve) but consider how I dealt with this in the old days when I had to shuffle entry forms the day of an event. It is based on who is excluded in any hole in the matrix rather than random generators or an ideal matrix. I never did figure out a way to set it up in Paradox, but I could do it by shuffling cards very easily. I will send you a pm.
Essentially I was building a 3d matrix by laying out playing cards with pilot names stacked in piles with frequency conflicts (Teammates in your scenario) and optimizing minumum conflicts until everyone had flown against everyone else. Back then we were not flying MOM or one per frequency but the idea was exactly the same. Think at any given time there are 10 slots to fill, when you fill the first one certain entrys are excluded from the second. Once number two is filled, even more are exluded from #3 and so on. As you start the second group there is a large number of exclusions ....You will very quickly reach the point of guys flying against someone they have met previously and this is where I lacked the skills to program on Paradox, but it was easy to do by hand.
Last edited by Gil Gauger; Sep 29, 2011 at 04:48 PM. Reason: Coherent thought
Sep 29, 2011, 06:24 PM
Registered User

Matrix Generation

Jim,

Joe has pretty much described how GliderScore creates a matrix, but getting it right might take a bit of work.

You could consider generating the matrix using GliderScore, then downloading the draw and importing it into your own program. Provided that your program then handles late landing penalties, pilot reflights, group reflights and special reflight groups you should be fine.

While it seems attractive to have instant scores on the web, I think that posting complete rounds as they are finished is enough. Outputting flight scores and results from GliderScore to a .pdf file, and posting that to a web site achieves this quite nicely.

Gerry
 Sep 30, 2011, 12:28 AM Registered User Hi Gerry - thanks for the input. Your program is quite nice. I have one that does all that and allows pilots to enter their scores from their smart phones on the flight line, and get all the data on their standings and their competitors performance in real time. All the flight details are also immediately available on the web for those wishing to follow along with the event. While it might not be necessary, everyone that has used it really liked that. It does all the necessary stuff, so I only really want to improve the matrix generation. I have looked at your MDB and I'm sure as a one-off I can take my registration and team data and reformat it to import into your program and then export the matrix info back out and get it into my DB. I'm hoping to implement a better algorithm so it's easier for me than those gyrations in the long run. Thanks for a nice program.... Jim
 Sep 30, 2011, 05:12 AM I hate propellors I have written an algorithm that keeps a matrix of counts of all pilots against all pilots. The diagonal is always zero as are the cells for team members against each other. The draw is done with random number seeding and 100 possible draws are stored. Each of these is tested against the cumulative matrix of counts and a score is obtained to show the efficiency of each in improving the head to head count matrix. The draw with the greatest efficiency then becomes the next next round. The matrix of all pilots is updated and the process is iterated. When I wrote it I had to deal with frequency clashes as well and it became a huge program that bogged down the small PC's around at that time. If you are interested I could put the code back together to meet your specs. Basically it seeks out best next increments. The distribution of combinations does not follow a normal distribution so parametric statistical measure do not help much. There are systematic harmonics formed if you try to use incremental rotation of teams. These are set by the ratio of number of teams and number of persons in teams. AS Gerry points out, reflights mean that the scoring system has be able to deal with different reference scores, but luckily they do not impact on the combination of fliers.
Sep 30, 2011, 07:51 AM
Registered User
Quote:
 Originally Posted by emufingers If you are interested I could put the code back together to meet your specs. .
Hi Ed - I appreciate the offer. I don't want to bother anyone solving the problem for me, but I'd love to see the code you have for the approach to the problem...

Please don't spend a lot of time on it though...

Much appreciated...
Jim
 Sep 30, 2011, 01:21 PM Registered User Are you making it freely available Jim? There are software out there that does this but it is not free or put on web for anyone to use.
Oct 01, 2011, 02:09 AM
I hate propellors
Quote:
 Originally Posted by jimsoars Hi Ed - I appreciate the offer. I don't want to bother anyone solving the problem for me, but I'd love to see the code you have for the approach to the problem... Please don't spend a lot of time on it though... Much appreciated... Jim
I can't find the code but Iam doing a quick and dirty in excel that demonstrates the method. I am enjoying trying to remember what I did. I have plenty of time for something that is interesting.

I'll post the excel sheets within a few days. Then everyone can tear the method to bits.
Oct 01, 2011, 09:15 PM
I hate propellors

A quick and dirty model

Please find attached an excel workbook which demonstrates the principles of my techniques. A spreadsheet is not the most efficient way of doing this, but I thought it ould be easier to demonstrate what is happening and let others develop the idea. There may still be some bugs in the code, but it produces swensible results.

It was really hard to describe what I have done in the notes, so feel free to post questions and any mistakes you find.

It is relatively easy to add to the spreadsheet to allow for more rounds. I only did four to save time.

The way to proceed is to reprogram the ideas into C or Java and to develop an iterative algorithm for systematically rotating the matrix, meqasuring the gaain porduce by each of a large number of rotations and selecting the best at each round. This would allow am optimised competition matrix to emerge and mean that at any number of rounds the best possible competition in that number of rounds will have been flown.

Last edited by emufingers; Oct 01, 2011 at 09:23 PM.
 Oct 02, 2011, 12:00 AM Registered User Super - I think I understand what you are doing. I'm prototyping it in Perl and will see how the Absolute Mean Deviation looks over 24 rounds. Thanks - Jim
 Oct 02, 2011, 12:16 AM Registered User My quick test indicates I have a harmonic. For example the folks in team 2 always fly against the same people in team 6. I think this comes from the roation of the order as shown in your matrix on the non-random rotation sheet. Unless I misunderstood the rotation - since we go down the teams and rotate by 4 every 4th team has the same rotation - therefore the same meetings.. Am I missing something or perhaps I coded it wrong? Jim
Oct 02, 2011, 12:38 AM
I hate propellors
Quote:
 Originally Posted by jimsoars My quick test indicates I have a harmonic. For example the folks in team 2 always fly against the same people in team 6. I think this comes from the roation of the order as shown in your matrix on the non-random rotation sheet. Unless I misunderstood the rotation - since we go down the teams and rotate by 4 every 4th team has the same rotation - therefore the same meetings.. Am I missing something or perhaps I coded it wrong? Jim
You are spot on because there are more teams than members in teams some teams will move the same amount and not rotate against each other. The trick what the harmonic starts to form is to make sure that the teams that are stuck move aginst each other in th next round. Thuis can either be done manually or you could write a Perl script to identify the harmonics and deliberately rotate to ensure a shift. This is why I think that the deliberate rotation method is likely to be more effective in balancing the draw than random because random seleftion does not use the information from previous heats. The aim if to keep the number of zeroes and repeatd as low as possible.

Jerry