When playing your favorite board game, having the option to set a different initial setup every time is a good way to keep things fresh.
In Flamme Rouge, a study of game variability, I examined all sorts of mechanism that games use to avoid blandly repeating themselves from one game to another.
However, I left you hanging with a crucial and very specific question about board game modularity, namely: How many unique races can be build from the tracks provided in the Flamme Rouge game ?
Today, we are going to find that out !
In case, you are not familiar with the game, and you would like to know more, you may want to start at the beginning with my actual review and rules explanation in:
The total number of unique Flamme Rouge race tracks
In the box, Flamme Rouge provides 6 initial race plans for players to try out. But since you can arrange the tracks any way you want, this evidently only offers a limited sample.
Knowing that a racetrack is composed of all available pieces, and that the box contains 21 of them… double-sided, it can make for quite a bit of possibilities! Finding an exact number however is not exactly a walk in the park…
The upper limit of combinations
Since part of my goal is to make this understandable for the greatest number, and allow for criticism of my approach, I’ll try to describe the full process.
So let’s start with defining an upper limit on how many race tracks we can build with the given game content.
Combinatorial track building
Considering only the shape of the pieces, we have the following:
- 1 x Start piece
- 1 x Finish piece
- 7 x Straight lines
- 6 x 45-degree turns
- 6 x 90-degrees turns
Assuming that we use all 21 pieces to build the track, how many unique track can be built ?
The start and finish pieces will always be at the same place. This mean we can ignore those in our initial count. For the rest, if we build the race one piece at a time, starting after the starting line, we have the choice of:
19 pieces for the 1st segment.
18 remaining pieces for the second
17 remaining pieces for the third.
16 for the fourth
And so forth….
So in total we have 19 x 18 x 17 x 16 x 15 x … all the way down to one.
A simple factorial usually noted as: 19!
This gives us:
121 645 100 408 832 000 different ordering!
122 Quadrillions !!!
If you were to play one game every second, this would take 3.59 billions years!
But this is not the whole story.
Since all the 21 track pieces are reversible, one side being flat racing ground, and the other usually having some form of upward or downward slope, we need to count 2 possibilities for each track pieces, or rather all the possible combination of choosing side-A or side-B for each piece.
For a fixed 3 pieces ordering, by just selecting side A, or side B you have choices for a total of 8 different tracks. For example:
Which mean that for each of the previous 19! ways of ordering the pieces, we have ways of actually setting them. And i say 21 because the starting and finish pieces can also be flipped, so we need to include them this time.
This leaves us with ways of setting the race track.
121645100408832000 * 2097152 = 255 108 265 612 582 846 464 000
This however is only an upper limit…
- First because, some pieces looks the same, at least on one of their side.
- Second, because the track is not a straight line, there are some ways to set the pieces that would end up crossing each other, and create tracks that are impossible to build on a flat surface!
So while this number is astronomical, it does not represent the real amount of possible ways of setting the track. And since I do not shy away from a challenge, I decided to get a better approximation of the real number of tracks we can build.
A small note about racetrack shape: While the most important aspect of a race track is its elevation profile (where the up and own slopes are), having different race track shape is also interesting because when you play, it feels different. Also, I will come back to elevation profile in a moment.
So let’s have a look at how we can improve our estimate on the number of track shape!
Counting the number of possible shapes
From a track shape perspective, we do not really have to consider 19 individual pieces, but only have to consider three types of pieces:
- Straight lines
- 45-degree turns
- 90-degrees turn.
And to simplify thing even more, only the 45-degrees and 90-degrees pieces will change the overall track shape when flipped. A flipped straight line, is still a straight line after all.
This two simplification drastically reduce the number of possible unique track shapes that can be built!
To calculate our new number of meaningful ordering, we take the original count, and divide it by the count of interchangeable ways we can order the identical pieces without affecting its shape.
So the ordering count becomes:
And for the flipping portion of the problem, we now have only 12 turning pieces that can be flipped to change the track shape. Which is instead of .
So it gives us:
46558512 x 4096 = 190,703,665,152
You do not need to be a wizard to see that 190 billions is a much more manageable number than 255 108 265 612 582 846 464 000 !
Approximately 1 000 000 000 000 times more manageable… We still don’t know how many of those shapes are non-intersecting and thus playable, but this is a good start!
At this scale, would the modern wonder of computers makes it possible to visit each individual racetrack and check if it offers a valid non-intersecting shape? It certainly does!
So why not write a simple program that will visit each of those shapes?
Warning: Checking if a track self-intersect is not as simple as it may seem.
- First because you have to try to represent the track as a series of lines, close to the real thing. And check if they intersect.
- The real pieces have some slack, so you end up with tracks that would be slightly overlapping in theory, but that are perfectly playable in reality.
So I made an executive decision. I simplified a bit the track representation to make it easy to compute. Using points along the turn pieces exterior instead of curves, and I decided to ignore the slack issue, only evaluating a track as valid if it would not be intersecting using rigid pieces.
Since I’m a half a perfectionist, I worked really hard to make it an honest representation of the real thing, but the exact number of correct track may vary by a few millions, depending on what you accept or not as overlapping.
Far from perfect, but likely the closest you’ll ever get to real answer to this unlikely question…
How many valid track shapes
Now that we have a tractable number of possible track shape, (about 190 billions), how many of them are non-intersecting ?
For the curious, here are some optimizations I made to reduce a bit the number of actual number of track examined:
- I only examined track where the first turn is a left turn. I assumed here that all those track have a mirror equivalent track where the first turn is to the right, and I double counted them. I only did this for the first turn, because for subsequent turns it gets too complicated to determine if the mirror image of the remaining track would intersect with previously laid tracks without actually checking. This divide the actual count to check by about half.
- I built the track exploration in a depth-first search pattern, killing a branch of my search tree as soon as I encountered an invalid track crossing, thus limiting the total number of final track to consider.
For the curious, here what a depth-first search looks like in our case (You can see that we go as far as we can, then backtrack as little as possible to explore the whole in ordered manner).
I’ll save you the details about the actual implementation, and visualization that took me quite a bit longer than I expected, but, I finally made it and…
The actual number of unique valid track shape is:
86 728 760 224
or approximately 45.48% of the 190 billions track tested!
Just to be clear, this number is manageable, but it still took my computer almost 3 days to complete the computation, so not that trivial a task either!
What about track permutations ?
When playing Flamme Rouge, the only concern for a competitive player is the race track elevation profile, the upward and downward slopes that offer the most strategic plays.
Here is a crude way of representing the elevation profile of a race track:
My representation is a bit simplistic for the moment, but since I’m not providing info graphic for anyone beside our own entertainment, it will have to do. However, doing a quick search I found this fun article showing that I’m not doing that bad of a job: how bad elevation profiles abound in the cyclist world.
So, forgetting the race shape and it’s validity for a moment, I decided to see how many unique elevation profiles we can get for a fixed ordering of the track pieces. This is a bit of a detour, but this gave me enough understanding of the problem to allow me to really answer the big question of how many unique races are possible. So bear with me!
How many unique elevation profiles can be obtained from a fixed track ordering?
Flamme Rouge track pieces all have a letter assigned to them. One side is a lowercase, and the other side is uppercase, allowing race tracks to be identified by a single string such as:
Or as presented in the game itself:
So let’s say we take a particular ordering of the track pieces. Keeping all the letters in the same order, but allowing flipping side, between lower and uppercase. How many elevation profile can we obtain this way? (Forgetting track overlapping and validity for the moment).
There is 21 track pieces in total, each track pieces having two sides. If we allow all combinations of on which side we put them, it gives us unique combinations.
2 097 152 potentially different profiles.
But since several pieces have the same elevation profile on both of their side, this is, once again, only an upper limit…
To be sure, I decided to write a little program to really know how many unique elevation profiles can be obtained by simply flipping pieces, while keeping the pieces ordering fixed.
Since images speak more than words, have a look:
What I learned here surprised me a bit !
For a given ordering, of the 2 097 152 possible combinations, I obtained the following number of unique profile:
And more surprising, this was the exact same number, no matter what the track pieces ordering I looked at. For each of them, I found 16 repetitions of each possible elevation profile. (And 16 * 131 072 = 2 097 152, the math checks out!).
Once the initial surprise passed, I realized the reason for this was simple, 4 of the pieces have the same (flat) elevation profile on both side, so for (16) combinations, the elevation profile will be the same with these pieces on one side, or the other!
Only the pieces that have differentiable sides will affect the overall elevation profile when turned over!!!
Elevation profile repetition between orderings
In order to see if we would see repeating elevation profile between different pieces ordering, I decided to generate random tracks, and check if I found any.
Once you remove the 16 completely flat profile available for all the pieces ordering, is there overlap? The answer is… not many!
When you look at the non-flat side of pieces, not many pieces can be interchanged to get the same elevation. There is three straight pieces that offer an elevation profile that can be replaced by 3 turn pieces of length 2, if put in the correct order.
Some turn pieces can be interchanged, because they have the same non-flat profile of 2-down or 2-up.
But aside from those cases, only the orderings which have a piece at the exact same place will produce tracks with equivalent profiles, and only when mostly all of their other track pieces are on the side showing flat ground.
Testing 1000s of randomly generated ordering for repetition among all their permutations offered at most a few hundreds similar elevation profile when adding a new race.
I’ll be sorry to disappoint, but I did not reach a final conclusion on how unique elevation profile there was in total. Maybe I’ll revisit one day, but for the moment, I refused to be side-tracked!
However, doing all this gave me a good enough understanding of the problem to provide a final answer to our original question:
How many unique races can we get if we consider shape AND elevation profile?
Converging toward a complete solution
Playing with track flipping, trying to reconcile them with the validity of non-crossing shape, I realized the following:
If you take a fixed valid track shape, you can rearrange and flip pieces sides without changing the shape. And if you can calculate unique elevation profile per unique shape, you would end up with the sum of unique races!
Some races in that count will have the same shape. Some races in that count will have the same elevation profile. But no two race track in those will have both the same shape and the same profile, giving us the real count of unique races!
So let’s calculate how many possible permutation and flipping is possible for each fixed and valid track shape…
Counting elevation profile for fixed race tracks
For this, we can consider each type of track pieces independently, and multiply them together to get our final number.
Starting and finishing pieces
We have one starting piece and one finishing piece. Their place is fixed, but they can be both flipped and show different profile. For a total of 2 times 2 different positions. So:
Straigth track pieces
For the 7 straight pieces, they all have a one side of flat ground, and the other side with different elevation changes. So we can reorder them in 7! different ways.
All can be on one side or the other without changing the track shape. So they provide a multiplication of for the elevation profiles.
There is one last adjustment to make before multiplying those number together. Because all the straight pieces have a flat side, this guarantee all the reordering will have an identical elevation profile. So we correct for this by adding a minus one to the number of flipping combination. As to remove the flat ground combination… and we add it back after we multiply the re-ordering. Which finally gives us:
or 640 081
45 degree turn pieces
For the 45-degree pieces, things get interesting. Since we are at the moment only considering a fixed race track shape, there is no real choice of which side the turn pieces are set. The permutation of the pieces in the track implicitly determine on which side they end up. So we only have to consider at most 6! (or 720) different elevation profiles…
However, because there is always a complication, there are 2 pieces with flat ground on both side, and a couple with identical elevation profile on their second side. And because the flat side is sometime on the 45-turn as a right turn, and sometimes as a left turn, the actual count of elevation profile depends on how many right turns and left turns there are in the shape !
As in everything mildly complicated, a quick program will solve that for us.
So instead of 6! which would give us 720 unique elevation profiles, we end up, depending on the direction of the turns, with the following counts for the different combination of the 6 turns:
|Nmb of Turns||Unique Elevation Profile Count|
|0 right, 6 left turns||30|
|1 right, 5 left turns||50|
|2 right, 4 left turns||73|
|3 right, 3 left turns||82|
|4 right, 2 left turns||63|
|5 right, 1 left turns||35|
|6 right, 0 left turns||15|
So between 15 and 82 different elevation profile, which is surprinsingly far less than the possible 720…
90 degree turn pieces
For the 90 degrees turns… in a mind bending twist, which this time is in our favor, they turn out to have the exact elevation profiles distribution than the 45-degrees turns.
So we don’t have to repeat this, and can simply re-use the same numbers from the last table!
Let’s put it all together
So we end up with calculating the total number of possible unique elevation profile for a fixed shape as:
4 different ways to put the starting and end piece.
640 081 ways to put the straight pieces.
Between 15 and 82 ways to put the 45 degrees turns.
And again between 15 and 82 ways to put the 90 degrees turn.
4 * 640 081 * 15 * 15 = 576 072 900
4 * 640 081 * 82 * 82 = 17 215 618 576
Limits that we must not forget to multiply each by 86 728 760 224, the total number of unique shape we found earlier…
But Wait !!!
If I just re-ran my exploration program, I would be able to know exactly how many valid shapes there are for each of the possible combination count for the 90 degrees and 45 degrees turns, and thus calculate the exact number of possible racetracks, without those pesky limits approximation!
The following table contains the counts of valid racetrack, for each possible combination of 45 and 90 degrees turns.
To be clear the column titled 1 – 90 means One 90-degree left turn in the track (And therefore five 90 degrees right turns). And the row are similarly labeled, indicating how many left 45-degrees turns.
|0 – 90||1 – 90||2 – 90||3 – 90||4 – 90||5 – 90||6 – 90|
Note that because all tracks have a corresponding mirror image track, the table itself is mirrored.
Not surprisingly, we can see that tracks with all their turns being left (or right) are quite rarer than more balanced track!
Here is a few examples:
Finally, to make good use of the above table, I built a similar table, using the results of the previous section, this time showing the 45-degrees and 90-degrees unique elevation profiles counts.
Remember that the 45 and 90 degrees turn offered the same unique elevation profile counts. So once again the table is mirrored, but in the opposite direction.
Here is the table showing the unique elevation profile count for different amount of left turns:
|0 – 90||1 – 90||2 – 90||3 – 90||4 – 90||5 – 90||6 – 90|
|0 – 45||225||525||945||1230||1095||750||450|
|1 – 45||525||1225||2205||2870||2555||1750||1050|
|2 – 45||945||2205||3969||5166||4599||3150||1890|
|3 – 45||1230||2870||5166||6724||5986||4100||2460|
|4 – 45||1095||2555||4599||5986||5329||3650||2190|
|5 – 45||750||1750||3150||4100||3650||2500||1500|
|6 – 45||450||1050||1890||2460||2190||1500||900|
So all we have to do is to multiply the two tables together, element wise (Each cell multiplying the corresponding cell of the other table), to obtain the number of variation obtained through flipping the pieces for each fixed track shape, and sum all the values together. Giving us:
420 221 311 798 054
All that is missing is to multiply by the number of straight track recombination (640 081), and the number of start and end pieces combinations (4).
For a grand total of:
1 075 902 709 908 040 809 496
0r 1.08 * 10 exp 21
Unique valid race tracks to play.
As I mentioned earlier, this is still an evaluation since there is some uncertainty when validating a race track shape. And I reserve the right to update the numbers if I find some errors. But I stand by the methodology! Feel free to try to come up to a more precise number!
One legitimate question you may ask is the following:
What was the point of doing this?
Well, there are two ways of looking at this…
First, there is the idea that since this has no practical use, this is useless. I would counter that solving a problem is interesting by itself. It forces you to consider things you would normally brush aside. As such, I’m often annoyed when learning something, and only being shown only the simplest and easiest cases.
Once you try to solve a real life situation with a bit more complexity, you are on your own. You almost always encounter issues and limitations that were not mentioned, and limit greatly the possible applications.
Second, while doing this I also got plenty of time to think about the problem, I personally learned things doing this, about all kind of stuff. I cannot count the times when a difficult problem arose in my professional programmer life, and where I ended up having a serious head start because the new problem had some aspects resembling earlier problems I solved.
I also had plenty of interesting ideas along the way!
What I did not tell you is that, while doing this, I decided to re-run my program, but this time, saving some additional information about the tracks generated.
Inevitably, this led to me working on a new post about interesting tracks, and practical track shapes to use when playing in a space challenged environment!
In the meantime, have fun and let me know if you learned anything useful, if you enjoyed some parts more than others, or if you think I missed anything!