Phase Shift Lane Rotation Schedules

[Mr. Slick]

In this thread I hope to cover all aspects of the scheduling method that I refer to as Phase Shift Lane Rotation.

It is a method that evolved years ago here in the northland during the months of snow and ice. . . commonly refered to as Pinewood Derby Season to the people of this forum.

Some one should make a post that has the bestest description they can come up with based on prior posts.

This method is primarily for TIMED RACING, it has limits in doing more than one round of racing.

Times to run races this way are typically in the 1:00 to 1:30 per heat.


The basic ideas are:

Track Fairness:
Each car will race in each lane.

When will my car race:
Each car will be in Lane A for the heat that is the same as the car number.
Each of the other lanes will cycle through the car numbers in order, starting at 1 once they have hit the maximum car number.

Opponent Equity:
The "Phase Shift" should be done to allow car number 1 to race as many opponents as possible.

How many Heats will there be:
There will be the same number of heats as there are cars.

How many times will my car race:
As many times as there are lanes in the track.

How often will I race:
Each car will race roughly every (# cars divided by # of lanes) heats.

[gpraceman]

How many times will my car race:
As many times as there are lanes in the track.

Many users want the ability to run multiple times per lane. If the algorithm can be tweaked for each successive run per lane, then that would add the greatest flexibility for the users.

In all likelihood there will be some combinations of lanes/racers/runs per lane that a suitable chart cannot be found but this is true with all methods that try to maximize opponent equity.

[Mr. Slick]

I had some time on the bus ride home . . . one aspect could apply to multiple runs.

The concept of multiple runs could be simplified by doing a multiplier on the number of lanes.

2 runs down on a 3 lane track would be the same as doing a six lane schedule and then using Lanes 1-2-3 as the first set of heats and lanes 4-5-6 as the second set of heats. This may simplify the calculations for determining optimal solutions without changing the algorithym.

still thinking. . .

[Stan Pope]

I had some time on the bus ride home . . . one aspect could apply to multiple runs.

The concept of multiple runs could be simplified by doing a multiplier on the number of lanes.

2 runs down on a 3 lane track would be the same as doing a six lane schedule and then using Lanes 1-2-3 as the first set of heats and lanes 4-5-6 as the second set of heats. This may simplify the calculations for determining optimal solutions without changing the algorithym.

still thinking. . .

This is better thought of as Rounds * (Lanes - 1) + 1.

2 runs down on a 3 lane track would be the same as doing a 5 lane schedule and then using Lanes 1-2-3 as the first set of heats and lanes 1-4-5 as the second set of heats.

The problem is that this actually reduces the array of possible solutions by introducing unintended limitations. In so doing, it may prevent solution. Even so, it prevents fewer solutions than the proposed Round * Lanes approach.

[Mr. Slick]

huh?

I was thinking:

Want two rounds of racing on a 3 lane track, calculate a full 6 lane single round.

sample full 6 lane first 4 heats for a 40 car race:
-- L1 - L2 - L3 - L4 - L5 - L6
H01 01 03 11 20 28 35
H02 02 04 12 21 29 36
H03 03 05 13 22 30 37
H04 04 06 14 23 31 38

Using a 3 lane track where you want 2 runs down each lane:

Round 1: (first 4 heats, uses values from L1, L2, L3)
H01 01 03 11
H02 02 04 12
H03 03 05 13
H04 04 06 14

Round 2:(first 4 heats, uses values from L4, L5, L6)
H01 20 28 35
H02 21 29 36
H03 22 30 37
H04 23 31 38

[Mr. Slick]

In response to a post in "the old thread"

This method should work for any number of car with any number of lanes.
I haven't found any issues for a few hundred packs, churchs, service units, etc. (lots of practice at 20+ races for years . . . hint: youngest son will soon be a Life Scout, oldest is a registered adult)

The aspect that is lost first is the need to have a car from one race in the following race with small values of numCars/numLanes.

This aspect is traded off rather than diminshing opponent equity. I trade off race operators' ease to spectator perceptions with regard to racing as many different cars as possible.

[Stan Pope]

huh?

I was thinking:

Want two rounds of racing on a 3 lane track, calculate a full 6 lane single round.

sample full 6 lane first 4 heats for a 40 car race:
-- L1 - L2 - L3 - L4 - L5 - L6
H01 01 03 11 20 28 35
H02 02 04 12 21 29 36
H03 03 05 13 22 30 37
H04 04 06 14 23 31 38

Using a 3 lane track where you want 2 runs down each lane:

Round 1: (first 4 heats, uses values from L1, L2, L3)
H01 01 03 11
H02 02 04 12
H03 03 05 13
H04 04 06 14

Round 2:(first 4 heats, uses values from L4, L5, L6)
H01 20 28 35
H02 21 29 36
H03 22 30 37
H04 23 31 38

Yes, I fully comprehended.

With this approach, you are "using up" possible match-ups more quickly than needed. Using just the first 5 columns accomplishes the goal with more economy: 1-2-3 and 1-4-5. 6 can be combined with one more column to make a 3rd round if needed!

Round 2:(first 4 heats, uses values from L1, L4, L5)
H01 01 20 28
H02 02 21 29
H03 03 22 30
H04 04 23 31

It would not be such a good chart, though, since the Lane 2 and 3 match-ups will be repeating because of the repeated delta of 8 in the original chart! As you showed it, the round 1 lanes 2 and 3 match-ups are repeated in lanes 1 and 2 during round 2. But that is due to a fault in the original 6-lane chart which appears to prevent the maximum number of opponents with either approach.

Given all the costs and losses (the different numCars/numLanes loses the racing frequency balance, the additional requirements for 6 lanes reduces the number of solutions available to choose from, maximizing opponents is harder to manage), I'd be inclined to stay with fully separate charts for each round.

[Stan Pope]

Opponent Equity:
The "Phase Shift" should be done to allow car number 1 to race as many opponents as possible.

You correctly rely on other cars to have the same opponent distribution profile as car number 1 has.

This requirement should be weakened in order to avoid the kinds of exhaustive generator searches needed in creation of PPN chart parameters.

It is possible to compute the optimistic best possible opponent count. The number of other track slots for any car is known to be numRounds * numLanes * (numLanes - 1). if numCars - 1 <= that number, then you expect to be able to race against all of the opponents, unless number theory stuff gets in the way. If numCars - 1 > that number, then you expect all of the opponent to be unique, again unless number theory stuff gets in the way. A search for chart can continue until all possible charts have been exhausted or a chart is found that matches that "best possible" numbers. Depending on the chart, this may take hours to locate.

Since timed racing and not final standings (heat points) is the racing mode of interest, it might be better to accept a chart that is close to satisfying the "as many opponents as possible" requirement, e.g. 80% or 90% or 95%. This probably cuts the search time down to acceptable durations. Or, perhaps you set a search time limit and use the best chart found within that time limit.

That way you get a wide variety of opponents and you still have the total lane equity inherent in LR charts.

[Mr. Slick]

I was wondering about simplifing the chart selection process.

With N cars there are only N sequences for each lane.

For example, a 9 car group would have the following possible sequences.

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

The total number of possible charts for 3 lanes would be:

N*(n-1)*(n-2)

but, given that we don't want cars racing in the next heat, if we choose a specific sequence, the sequences immediately above and below it are eliminated from further consideration. Since the first sequence, Car 1 in first heat is "next to" the last sequence with car N in the first heat and car 1 in the second heat, and it is also next to the second sequence, Car 2 in first heat, car 1 in last heat. Selecting the first sequence would eliminate the other two, last and second, due to cars racing in consecutive heats.

so, once I got to this point, I finally feel like I just want to take a refresher in combinational stats. Not really, but I did enjoy things like ring theory and cylinder combinations like we have here!

I wonder how many people who have races based on total time, have more than one round of every car going down every lane?

Trying to solve the multiple round issue may be only applicable to a small minority.

Also, what is the distribution of the number of cars being raced in a group?

[Cory]

Some one should make a post that has the bestest description they can come up with based on prior posts.

Here is a basic C/C++ implementation for 1-round charts. It is equivalent to the Excel cut-and-paste description from the other thread, but it attempts to tie down some of the details. There is no error checking for valid charts in the case when the initial phase shift ends up being 1.

Code: Select all

using namespace std;

#include <iostream>

#define MAXLANES (10)

// ===============================
// Strict phase shift LR algorithm
//  for one round charts
// ===============================

int main()
{
    int numCars = 13;
    int numLanes = 4;
    int i,j;

    // determine initial phase shift

    // first pick a "rough" candidate
    int candidate = (int)(floor((double)(numCars/(numLanes+1))));

    // just in case numCars = numLanes
    if (candidate < 1)
        candidate = 1;

    // refine the rough candidate, if necessary
    while (1)
    {
        if (candidate == 1)
            break;

        // the idea here is that we want to spread each car's heats throughout the chart
        // and any two heats for a car will be at least "candidate" or so apart
        int sumShifts = 0;

        for (i=1; i<numLanes; i++)
            sumShifts = sumShifts + candidate + i - 1;

        if (sumShifts < (numCars - candidate))
            break;            //       ^   
                              //       |
        candidate--;          //  we don't want car 1's last race to be too close
    }                         // to the end of the chart.  if it is, then some races
                              // of some other cars will be too close together
                              // because of wrap-around

    // okay, we'll use this value
    int initialPhaseShift = candidate;

    // determine generators
    int gens[MAXLANES-1];

    for (i=1; i<numLanes; i++)
    {
        gens[i-1] = numCars + 1 - i - initialPhaseShift;
        cout << gens[i-1] << endl;
    }

    // generate chart
    for (i=1; i<=numCars; i++)
    {
        int car = i;
        cout << car << '\t';

        for (j=1; j<numLanes; j++)
        {
            car = (car + gens[j-1]) % numCars;
            if (car == 0)
                car = numCars;

            cout << car << '\t';
        }

        cout << endl;
    }
}

My two cents on the other general issues:

Opponent Equity:
The "Phase Shift" should be done to allow car number 1 to race as many opponents as possible.

Finding charts that meet this condition can be difficult and time-consuming. In some cases, the charts can't be found. IMO, choosing this path eliminates any hope of a straight-forward algorithmic implemention like the C/C++ code above. You'll basically end up with a "copy" of the PPN method, with all of its inherent frailties.

How many times will my car race:
As many times as there are lanes in the track.

Multi-round charts seem like an attainable goal, based on the discussion above

[Stan Pope]

So, Cory, have you updated the PPN dll to generate on this basis when there are no predefined PPN generators to use???

It sounds like a natural growth direction ... a class of "time only" charts in which opponent equity is only fairly good, but still strong on lane equity. All of the other charts are okay for time or points.

[Cory]

So, Cory, have you updated the PPN dll to generate on this basis when there are no predefined PPN generators to use???

It sounds like a natural growth direction ... a class of "time only" charts in which opponent equity is only fairly good, but still strong on lane equity. All of the other charts are okay for time or points.

Me? Shoot from the hip?

It's a reasonable extension, I agree, from a purley PPN-centric world view, it would be good at filling the holes we have. There are still the questions of how to handle multi-rounders -- the numRounds*(numLanes-1) + 1 approach seems easy to implement -- and what to do when sumShifts >= numCars, which means you might not have a valid chart.

Randy, what are your thoughts on adding this to the DLL? If it does get added, I'm thinking it makes sense to provide clients (e.g. GPRM) with several options, perhaps...

1. Pure PPN (i.e. today's implementation, including the Misc charts)
2. Pure Phase Shift LR
3. PPN with Phase Shift LR extension

And, Mr. Slick, what are your thoughts on adding the algorithm to the PPN DLL? I doubt that it would happen without your concurrence. Adding Phase Shift to the DLL makes Phase Shift more widely available, provides a consistent implementation, and lets developers like Randy spend more time on their never-ending streams of enhancement requests.

There are probably between 5 and 10 programs out there that use the DLL now -- the majority of them are non-commercial -- and there will likely be more in the future. Stan and I make the DLL generally available at no charge.

[Stan Pope]

Code: Select all

        for (i=1; i<numLanes; i++)
            sumShifts = sumShifts + candidate + i - 1;

If I understand this part correctly, the shift magnitude decreases from about numCars/numLanes down toward 1. It might be good to start a few spots higher so that the steps bracket numCars/numLanes, e.g. at
int(numCars/numLanes + (numLanes-1)/2)

Also, to provide more "elbow room" for chart generation, it may be useful to also step the shift magnitude up toward numCars/2. In fact, this makes it easier to go to 2nd or 3rd rounds.

This could be combined by changing the step value up 1, down 2, up 3, down 4, etc. from the numCars/numLanes starting point. Or recognize the extra room above by stepping up 1, up 1, down 3, up 4, up 1, down 6, etc. I think that these increase the probability of more opponents.

[Cory]

Code: Select all

        for (i=1; i<numLanes; i++)
            sumShifts = sumShifts + candidate + i - 1;

If I understand this part correctly, the shift magnitude decreases from about numCars/numLanes down toward 1.

My intent was for the shifts to increase by 1 each time, as in Mr. Slick's examples -- i is increasing so the shifts get bigger. Equivalently, each generator is one more than the previous one.

Here is the output of my program for 25 cars 4 lanes, which I believe matches the original 25x4 example:

1 21 15 8
2 22 16 9
3 23 17 10
4 24 18 11
5 25 19 12
6 1 20 13
7 2 21 14
8 3 22 15
9 4 23 16
10 5 24 17
11 6 25 18
12 7 1 19
13 8 2 20
14 9 3 21
15 10 4 22
16 11 5 23
17 12 6 24
18 13 7 25
19 14 8 1
20 15 9 2
21 16 10 3
22 17 11 4
23 18 12 5
24 19 13 6
25 20 14 7

Am I missing something?

I can try the oscillation approach, also, it might be interesting to see the effect on the heat number sums and on the opponent counts.

[Stan Pope]

Am I missing something?

Ummm ... no, I was! With all the "plussing" and "minusing" and shifting down instead of up, I got turned around ... again.

Increasing the spread is usually a good thing, but as started, it pushed the last column too close to the first column, resulting in a opponent repeat. I think that -4 would be a nicer starting place than -5.