We throw K dice and look for the best pair out of them.
The probability that this best pair is (i, j), when i < j, is
K * ( i ** (K-1) - (i-1) ** (K-1) ) / 6 ** K
and when i ==j,
( i ** K - (i-1) ** K - K * (i-1) ** (K-1)) / 6 ** K.
Where did this come from, you'd ask. Well, for the first part, we have K possible dice that could give a j, and then the other K-1 should be showing numbers no bigger than i, thus the i ** (K-1). But at least one has to be exactly i, thus we should remove the throws that have only smaller numbers - ie, (i-1) ** (K-1). Finally, divide by all possible throws, 6 ** K... If we are frisky and use dice with more, or less than 6 sides, we'd use that number instead. If we use a mixture of 6- and 20-sided dice,... well, let's not..
the i == j case can be derived with the same logic
trying to write it down in a common expression gives
((i<j) ? (K * i ** (K-1)) : (i ** K - (i-1) ** K ) - K * (i-1) ** (K-1)) / 6 ** K
Ugly? you bet.. but on the positive side, it's the only explicit expression we'll have to write. So let's code it up
sub n_sides {6} sub attack {3} sub defend {2} sub loss { my ($att, $def) = @_; return (($att->[0] <= $def->[0]) + ($att->[1] <= $def->[1])); } sub pair_prob { my ($K, $pair) = @_; my ($i, $j) = @{$pair}; return (((($i < $j) ? ($K * $i ** ($K-1)) : ($i ** $K - ($i-1) ** $K)) - $K * ($i-1) ** ($K-1)) / (n_sides() ** $K)); } my @pairs = map {my $j = $_; map {[$_,$j]} (1..$j) } (1..n_sides()); my @losses; foreach my $att (@pairs) { foreach my $def (@pairs) { $losses[loss($att,$def)] += pair_prob(attack(), $att) * pair_prob(defend(), $def); } } print "P(loss = $_) = ", $losses[$_], "\n" for (0..@losses-1);
This is where things become really hairy.. We need a tuple_prob function, that from number of dice, K, and an m-tuple i_1 <= i_2 <= ... <= i_m, gives the probability that this is our best m-tuple from K thrown dice.
Let's call the signature of a tuple a count of how many times each element repeats. For example, the signature of (1,1,2,2,2,5) is (2,3,1).
Now imagine that for our m-tuple, the signature is (k_1,k_2,..k_s).. Our answer, then, has a coefficient of (K choose k_2,k_3,..,k_s), which is in how many ways we can throw the non-smallest parts of the tuple, and now we have to figure out what i_1 and k_1 do.
Well, if we call that part F(i,k,K), we have that
F(i,k,K) = F(i,k-1,K-1) + (i-1) * F(i,k,K-1)
with some boundary conditions, ie, F(i,1,K) = i ** (K-m+1) - (i-1) ** (K-m+1).
Add: These are the polynomials in i that we had above, just with more terms
We can recurse this and get our tuple_prob. Should probably cache the Fs, they will repeat a lot. We can then wrap it up with a tuple iterator and have a horribly over-generalized and useless Risk calculator.
So, if you actually made it down to here, and are now wondering what the heck does all this have to do with you, Perl, or anything, rest assured, absolutely nothing.. I had time to waste and holli wrote 'Because I think there must be a "formula" approach instead of brute force.'
Pure formulae solution this is not, but we'd gain a few orders of magnitude on brute force, if we have some weirdos that play with bagfuls of dice...
In reply to Re: Dice Roll Probabilities in Risk
by ivancho
in thread Dice Roll Probabilities in Risk
by hardburn
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |