Much more multiplayer madness

So, in the last post we found the probability of at least one player out of p players finishing the game in exactly n moves, which we called Pa~n, to be 1 - (1 - Pn)^p, where Pn is the probability of one player finishing the game in n moves. However, to determine the probability of a game with p players finishing in n moves, we must still find the probability that nobody finishes the game in fewer than n moves.

We know that the probability that one player finishes in fewer than n moves is given by: P1 + P2 + ... + P(n-1). The probability that one player does not finish in fewer than n moves is therefore (1 - P1 + P2 + ... + P(n-1)). Let us suppose that only one player wins (under the definition of "number of moves" I'm using, it is possible for more than one player to "win"), meaning that one and only one player finishes the game in exactly n moves. This makes it impossible for that one player to win in fewer than n moves, but it's still fair game for the remaining p-1 players. That means the probability that nobody finishes the game in fewer than n moves is: (1 - P1 + P2 + ... + P(n-1))^(p-1)

Pa~n * Pb~n, or the probability that a game with p players finishes with exactly n moves, is therefore given by the expression:

(1 - (1 - (Pn)^p) * ((1 - P1 + P2 + ... + P(n-1))^(p-1)

Knowing this, we can estimate the expected number of moves as follows:

Expected number of moves ~= (1)*(Pa~1 * Pa~1) + (2)*(Pa~2 * Pa~2) + ... + (n)*(Pa~n * Pa~n)

Where n is some large number.

(See the post "Great Expectations" for an explanation of why this works).

I already found Pn with a program for n up to about 250 (which is sufficiently large for our purposes), so here's the estimated expected number of moves for the first few values of p:


p = 1 --> 39.2
p = 2 --> 26.5
p = 3 --> 21.9
p = 4 --> 19.5


Just to make sure I didn't make a mistake (not a rare occurrence), I decided to instead modify the simulation program I wrote to allow for more than one player and calculated the expected number of moves based on the average of a large number of games. Here are the fist few results from that:

p = 1 --> 39.2
p = 2 -- > 26.3
p = 3 --> 21.7
p = 4 --> 19.3

They're close, but there's still clearly a slight error. I'll look into this more, but I suspect it has something to do with the assumption that only one player wins.

Here's an Excl graph showing the results (number of players on the horizontal axis, expected of number of moves on the vertical axis):

As more and more players are added, the expected number of moves of the winner gets closer and closer to 7, since 7 is the smallest possible number of moves.

Now that this approach was done, is the Markov strategy worth considering again? I think the only way that could be done would be to build a transition matrix around the moves of the winning player (for example, the winning player is probably more likely to spin larger numbers and land on big ladders), but this seems to be more trouble than it's really worth.