

United States, CO, Broomfield
Joined Jan 2003
1,032 Posts

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 14 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 14. Then for each team I generate a random sequence of those permutations (124). 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 



Joined May 2006
4 Posts

Matrix



United States, CO, Broomfield
Joined Jan 2003
1,032 Posts

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 


New Zealand, Hawke's Bay, Havelock North
Joined Dec 2004
2,303 Posts

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. 



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. 


Australia, VIC, Melbourne
Joined Aug 2010
66 Posts

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 


United States, CO, Broomfield
Joined Jan 2003
1,032 Posts

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 oneoff 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 



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. 


United States, CO, Broomfield
Joined Jan 2003
1,032 Posts

Quote:
Please don't spend a lot of time on it though... Much appreciated... Jim 




Quote:
I'll post the excel sheets within a few days. Then everyone can tear the method to bits. 




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. Comments please 


United States, CO, Broomfield
Joined Jan 2003
1,032 Posts

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 nonrandom 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 



Quote:
Jerry 

Thread Tools  
Similar Threads  
Category  Thread  Thread Starter  Forum  Replies  Last Post 
For Sale  CRC 1/12 GenerationXL NIB  Mr. Deals  Cars  Accessories (FS/W)  2  Oct 23, 2011 10:21 AM 
Build Log  90mm Matrix Video Added! Test flight complete.  fh64_lucky  Electric Ducted Fan Jet Talk  224  Nov 01, 2010 10:24 AM 