B Death Rally: an intricate probability problem?

[FranzS]

TL;DR Summary

A 1996 PC game and its random choices.

Hi PF,
I'm really struggling with an intricate probability problem that I'm investingating just for fun and I don't know how to approach it correctly.

So, there's this 1996 arcade car racing PC game called Death Rally that works like this:

• 20 racers are competing in a car racing championship.
• There are 6 car types (from car #1, the fastest, to car #6, the slowest) and each racer is assigned a fixed car type for the whole championship: 3 racers drive car #1, 5 racers drive car #2, 3 racers drive car #3, 4 racers drive car #4, 3 racers drive car #5 and 2 racers drive car #6.
• The championship consists in many rounds. Each round ("race day") consists in 3 different races: Hard race, Medium race, Easy race.
• Racers driving car #1 can compete in Hard races only. Racers driving car #2 or car #3 can compete in both Hard races and Medium Races. Racers driving car #4 can compete in both Medium and Easy races. Racers driving car #5 or car #6 can compete in Easy races only.
• 4 racers are competing in each race. As a racer can only compete in a single race, in a given round there will be 4 x 3 = 12 different racers competing (the remaining 8 will not participate in that round).
• In a given round, the racers are selected to take part in the 3 races at random (but always respecting the above rules).
• In a given race, a faster car will always rank above a slower car. Equal cars will rank randomly among each other.
• Hard race awards 10 points to the winner, 7 pts to the runner-up, 4 pts to third placement and 0 pts to fourth (last) placement. Similarly, Medium race awards 5/3/1/0 pts and Easy race awards 3/2/1/0 pts.
• Round after round, racers accumulate the points earned and are ranked in a general classification.

That's all as for the rules.
Now, I would like to (know how to) calculate the following values:

• Let's suppose that a Championship Season ends when a racer first hits or surpasses 1000 pts, after $x$ rounds. What is the expected number $x$ of rounds in a Season?
• What is the expected ranking and overall number of points for each racer in the final classification?
• What is the expected number of participated rounds for each racer?
• What is the expected number of participations to Hard races / Medium races / Easy races, separately, for each racer?
• What is the expected average points earned by each racer, separately for each type of race (Hard/Medium/Easy)?
• What is the expected number of races (or probability) for a given specific "arrangement" (for instance, how many Hard races with no. 3 cars #1 and no. 1 car #2)?
• If I were to simulate an entire Season with an Excel macro, would it make any difference, when selecting the racers for each race in a round, if I randomly selected the racer first or the race type first? I will try such simulations, but I'm more interested in what the theory could say about this.
• If I were instead to do an in-game simulation, I would have to choose for myself, me being the player, one among the 20 racers, but I would have to never participate to any races in order to not mess up the results of the other 19 A.I.-controlled racers. So, how would the above expected numbers/probabilities change in case one racer never participates to any race, depending on its car type?

With all the restrictions and rules explained at the beginning, I cannot get my round about these problems.
Of course I'm not expecting anyone to answer all the questions above, just a specific calculation or any insights will be appreciated!
Thanks a lot for your attention.

 

[andrewkirk]

The problem specification is complete except in one point:

TL;DR Summary: A 1996 PC game and its random choices.

In a given round, the racers are selected to take part in the 3 races at random (but always respecting the above rules).

This is incomplete. It needs to specify how the randomness operates, and what the probabilities are.
Here are two different examples, that will give different outcomes:

1. for a round there will be a defined set of valid allocations of racers to races. For each round, one of those is selected, using equal probabilities for each valid allocation.

2. Starting with the Easy race and working through to the hard race, select participants for each.
For each of those races, select four racers from those eligible to participate, giving equal probability weight of selection to each racer. Note that racers already selected for a race in this round are not eligible. This is a "selection without replacement".

My instinct says the calcs would be easier for the second approach than the first. But that may be wrong.

 

[FactChecker]

I recommend using a language other than Excel to simulate this problem that can easily run thousands of simulations. I don't know how well Excel lends itself to Monte Carlo simulations of any complexity, but several computer languages can handle it. And you should not be involved at all in the simulation since it would require tens (hundreds?) of thousands of simulations to get any accuracy in the results.
IMO, you should have already selected a racer before you select the race, since the type of car changes how many race-types it can be in.

 

[FranzS]

The problem specification is complete except in one point:

This is incomplete. It needs to specify how the randomness operates, and what the probabilities are.
Here are two different examples, that will give different outcomes:

1. for a round there will be a defined set of valid allocations of racers to races. For each round, one of those is selected, using equal probabilities for each valid allocation.

2. Starting with the Easy race and working through to the hard race, select participants for each.
For each of those races, select four racers from those eligible to participate, giving equal probability weight of selection to each racer. Note that racers already selected for a race in this round are not eligible. This is a "selection without replacement".

My instinct says the calcs would be easier for the second approach than the first. But that may be wrong.

I recommend using a language other than Excel to simulate this problem that can easily run thousands of simulations. I don't know how well Excel lends itself to Monte Carlo simulations of any complexity, but several computer languages can handle it. And you should not be involved at all in the simulation since it would require tens (hundreds?) of thousands of simulations to get any accuracy in the results.
IMO, you should have already selected a racer before you select the race, since the type of car changes how many race-types it can be in.

Thank you guys. Indeed, the issue you pointed out was the doubt I expressed in my second-to-last question.
I don't know how the racers' selection is actually automated into the PC game's script, but I can tell you how it is displayed on screen: when signing in for each new racing round, you enter a screen where three empty boxes corresponding to the Easy, Medium and Hard races are shown. Slowly, the names of some racers (your competitors) will pop up, one by one, inside the boxes (i.e. they signed in for that race), with no particular order. If you wait too much, all spots will be occupied and you (the player) will miss the round.

 

[andrewkirk]

Thank you guys. Indeed, the issue you pointed out was the doubt I expressed in my second-to-last question.
I don't know how the racers' selection is actually automated into the PC game's script, but I can tell you how it is displayed on screen: when signing in for each new racing round, you enter a screen where three empty boxes corresponding to the Easy, Medium and Hard races are shown. Slowly, the names of some racers (your competitors) will pop up, one by one, inside the boxes (i.e. they signed in for that race), with no particular order. If you wait too much, all spots will be occupied and you (the player) will miss the round.

Unfortunately that observation doesn't tell us anything about how the game selects racers. The actual selection will occur in a tiny fraction of a second and has nothing to do with the slow appearance of names on the screen. The slow appearance would be designed to simulate the feeling of real people slowly deliberating whether to sign up, making decisions and then getting around to putting their registration in.
There are countless different ways it could select racers, and no way to know which one it uses unless you have access to designer documentation, or somebody that works at the designer.
I mentioned two different selection methods above. Here's a third that's more complex but perhaps more like what might happen in real life.
Loop through racers rather than races, in order of decreasing number of rounds since their last race. Where there's a tie, break it by counting back to the race before that. Keep doing that until either all ties are broken or you've hit the beginning of the tournament. Break any remaining ties by randomly assigning priorities to the still-tied racers.
While working on the highest-priority racer that has not yet been allocated a race, allocate them to their home race (Hard if car 1-2, medium if 3-4, easy if 5-6) if a slot is available, otherwise to their other available race if they have one.
Continue until all slots are filled.
This approach minimises the random component. In the first few rounds randomness will drive most selections but after a while nearly all selections will be determined solely by past history.

 

[FranzS]

Unfortunately that observation doesn't tell us anything about how the game selects racers. The actual selection will occur in a tiny fraction of a second and has nothing to do with the slow appearance of names on the screen. The slow appearance would be designed to simulate the feeling of real people slowly deliberating whether to sign up, making decisions and then getting around to putting their registration in.
There are countless different ways it could select racers, and no way to know which one it uses unless you have access to designer documentation, or somebody that works at the designer.
I mentioned two different selection methods above. Here's a third that's more complex but perhaps more like what might happen in real life.
Loop through racers rather than races, in order of decreasing number of rounds since their last race. Where there's a tie, break it by counting back to the race before that. Keep doing that until either all ties are broken or you've hit the beginning of the tournament. Break any remaining ties by randomly assigning priorities to the still-tied racers.
While working on the highest-priority racer that has not yet been allocated a race, allocate them to their home race (Hard if car 1-2, medium if 3-4, easy if 5-6) if a slot is available, otherwise to their other available race if they have one.
Continue until all slots are filled.
This approach minimises the random component. In the first few rounds randomness will drive most selections but after a while nearly all selections will be determined solely by past history.

Thanks for suggesting such an example. I'll have to re-read it more carefully because it's not completely clear to me yet, but I guess that's not how the PC game is programmed, as the racers selection seems totally random: even after many races (100+) it often occurs that a particular racer (despite being ahead in the overall ranking) is selected to race for several consecutive rounds instead for example of other racers driving the same car type.
I'm pretty convinced one of the two initial ideas (random selection of a race first or random selection of a racer first, although the second might offer subtle variations) must be the one implemented in the game. I'll run some simulations and see. But, after that, I would really be curious to find out a way to tackle the probability problem in an exact analytic way. See you in a few days maybe, and thanks again to you all!

 

[.Scott]

What makes this problem easy is that once a round is over, the point assignment are the only things left behind - one round never effects the next round.
What makes it difficult is that, in each round, all 20 racers share the same pool of 36 points. The arithmetic would be easier if you were sampling 20 racers that were each running in their own championship.

But, as mentioned in posts above, the first step is in resolving the ambiguities in the rules.
When assigning cars to races, you cannot start by randomly selecting the 8 cars that will not participate because you can't sideline all 8 among car types 1 to 3 or all 8 among car types 4 to 6 and still populate all 3 races.
My suggestion is that each of the 50-million-or-so valid assignments combinations be considered with equal weighting - then randomly pick one of them.

With that done, you can determine the number of points expected of each car in each round.

For example, each of the #1 cars will have some chance of not racing (say 36%), and thus getting 0 points.
If they do race, they will definitely get some points, because they will be racing against 0, 1, or 2 other #1 cars.
Based on the race assignment criteria, you can calculate their point assignments for each situation.
Continue for each of the 6 car types, and you have fully characterized the probabilistic results for each round.

I'm sure car of type #1 will tend to reach the 1000 mark before other types - somewhere around day 140. In order for a type #6 car to end the season, it would have to always make it into a race against only a single type 3 or 4 car; always come in second place (thus winning 2 points per round and ending the season on day 500); and the remaining 34 points in each round would have to be evenly distributed among the other 19 players so that none average more that 2 points per round.

 

[FranzS]

@.Scott thanks a lot for chiming in.

I'm still studying this "problem" and I plan to post again here when I have relevant results.

Anyway, after running some simulations it became clear that the possible configurations of the racers during a race day don't have the same probability.
Instead, it seems to work like this:

• Step 1A: a random race type is picked (Hard/Medium/Easy). Specific example: H (hard) is picked. Probability P = 1/3. Cumulative probability CP = 1/3 (so far).
• Step 1B: a random racer among the eligible ones (the ones that can participate in race H for this specific example) is picked. Eligible racers: 3 racers driving car #1 + 5 racers driving car #2 + 3 racers driving car #3 (total = 11). Specific example: a racer driving car #2 is picked. Thus, P = 5/11. And, so far, CP = (1/3)*(5/11) = 5/33.
• Step 2A: same procedure as with step 1A. Specific example: M is picked. P = 1/3. So far, CP = (5/33)*(1/3) = 5/99.
• Step 2B: same procedure as with step 1B. Eligible racers: 4 racers driving car #2 (they are five in total but one was already picked in step 1B !) + 3 racers driving car #3 + 4 racers driving car #4 (total = 11). Specific example: a racer driving car #3 picked. P = 3/11. So far, CP = (5/99)*(3/11) = 15/1089.
• ... and on and on like this, considering that not only racers but also race types will run out of availability (when they are full with 4 racers)...
• Step 12A: last race type is picked and, as it is a forced pick (no other possibility), P = 1. CP = (incredibly small number resulting from previous steps) = ...
• Step 12B: last racer (12th racer to be picked for this particular race day, whereas the remaining 8 racers will be excluded) is picked. P = ... (depending on remaining racers driving eligible cars for the race type forcedly picked at step 12A). Final CP = ... is in the end the probability of this particular configuration of the race day.

Upper bound for total number of race day configurations $N_c$: as there are 3 race types and for each of them there are 3 different car types eligible, we have:
$$
N_c < 3^{24} = 282 \ 429 \ 536 \ 481 \approx 3 \times 10^{11}
$$

This of course doesn't consider race types running out of availability (after they reach 4 participants) nor car types possibly running out of availability (as all racers driving a particular car type might be already picked in earlier steps). I guess the true number of possible configurations might sit around $N_c \approx 10^{10}$.

 

[FranzS]

Justification for believing that $N_c \approx 10^{10}$: a more proper (exact?) estimate of the possible combinations for race categories $N_r$ would be...
$$
N_r =
\frac{
12!
}
{
4! \times 4! \times 4!
}
= 34 \ 650
$$

... because all steps A (see post above) will generate a sequence consisting in twelve elements, namely four H (Hard race), four M (Medium race) and four E (Easy race). Every possible permutation without repetition (i.e. we don't care distinguishing one E from another E in the sequence, for example) has to be considered.
Therefore it seems like the upper bound of all the possible race day configurations can be lowered to...
$$
N_c < 34\ 650 \times 3^{12} = 18 \ 414 \ 430 \ 650 \approx 2 \times 10^{10}
$$
It's instead not easy to come up with a lower upper bound for the $3^{12}$ term that describes the car types configurations.