Recommend
3 
 Thumb up
 Hide
6 Posts

Kingdom Death: Monster» Forums » Strategy

Subject: Herb gathering strategy - did some maths on it rss

Your Tags: Add tags
Popular Tags: [View All]
michael H.
msg tools
Hi folks,

I was wondering, what the best strategy would be like if you wanted to maximize on herbs and/or going down the swamp.
What is the expected mean outcome depending on how many dice you roll etc.

So I did some maths and wrote up a short matlab script to calculate the mean expected outcome for each "dice strategy" and wanted to share the results with you:

Spoiler (click to reveal)

Quick and simple:
Rolling with exactly 3 d10's every time will grant you the highest average(!) outcome

4 survivors rolling:
If you are looking for the 2 acanthus and vermin it's also your best bet to roll with 3 dice as it has the highest chance (~54%) of succeeding before overwhelming darkness.
After OD its better to switch to 2 dice (~70%), if you don't want to go down the swamp, as I understand you must add 10 to your result.

If you want to go down the swamp, you want to switch to 4 dice:
before OD you then have a chance of ~10% getting there, after OD your chance will be ~21%.
Going with only 3 dice here will lead to a reduced chance:
4% before OD and 16% after OD respectively.

Less than 4 survivors rolling:
Of course the chances and strategy with less survivors will change, but its rather unlikely you get to this point. You can simply adjust the number in the matlab script accordingly.



Matlab source code (v2015b):

Spoiler (click to reveal)


% Input
sides = 10; % sides on each die
n_s = 4; % number of survivors that get to roll

n_mc = 20000; % monte carlo runs

%% Analytical

n_dice = [1:sides]; % dice to get rolled for each survivor
% probability function for no double pips per survivor roll: (1-1/10)*(1-2/10)*(1-3/10)*...(1-n/10)
f_x = @(x) prod([1-([1: (x-1)]./(ones(1,x-1)*sides))]);
% probability values for no doubles
P_noDoubles = arrayfun(f_x,n_dice);
% average pip sum per roll with n dice
mean_pip_sum = sum(1:sides)/sides*n_dice;

k_over_n = @(k) nchoosek(n_s,k);
nhit =[1:n_s];
binoms=arrayfun(k_over_n,nhit);
mean_pips_a = zeros(size(n_dice));
for i_dice=n_dice
% bernoulli probability for each hit/miss distribution
P_bernoulli = binoms.*(P_noDoubles(i_dice).^nhit).*((1-P_noDoubles(i_dice)).^(n_s-nhit));
mean_pips_a(i_dice) = sum(P_bernoulli.*nhit*mean_pip_sum(i_dice));
fprintf('Rolling %.f dice:\nAll survivors score with an average outcome of %.f pips and a probability of %.3f %%\n',i_dice,mean_pip_sum(i_dice+1-n_dice(1))*n_s,100*P_noDoubles(i_dice+1-n_dice(1))^(n_s));
fprintf('mean expected pips on average %.1f\n',mean_pips_a(i_dice));
end

%% Monte Carlo Simulation
pipsResult = zeros(length(n_dice),n_mc);
fprintf('Monte Carlo run started:\n');
fprintf('0%% ... ');
for i_mc=1:n_mc
if diff([(round((i_mc-1)/n_mc*10)/10),(round(i_mc/n_mc*10)/10)])>0
fprintf('%.f%% ... ',round(i_mc/n_mc*10)*10);
end
for i_roll=1:n_s
thisRoll = floor(abs((rand(1,length(n_dice))*sides)-1e-9))+1;
for i_d=n_dice
if length(unique(thisRoll(1:i_d)))==i_d
pipsResult(i_d,i_mc) = pipsResult(i_d,i_mc)+sum(thisRoll(1:i_d));
end
end
end
end
fprintf('\n');
mean_pips_mc = (sum(pipsResult,2)/n_mc)';

% how likely is it to get 2acanthus/vermin or go down the swamp (after OD or before OD)
P_2ac_bOD = 100*sum((pipsResult>=45).*(pipsResult<75),2)/n_mc;
[thisMax,IDX]=max(P_2ac_bOD);
fprintf('highest chance of getting 2 fresh acanthus before OD with %.f dice: %.2f %%\n',IDX,thisMax);
P_2ac_aOD = 100*sum((pipsResult>=35).*(pipsResult<65),2)/n_mc;
[thisMax,IDX]=max(P_2ac_aOD);
fprintf('highest chance of getting 2 fresh acanthus after OD with %.f dice: %.2f %%\n',IDX,thisMax);
P_swamp_bOD = 100*sum(pipsResult>=75,2)/n_mc;
[thisMax,IDX]=max(P_swamp_bOD);
fprintf('highest chance of going down swamp before OD with %.f dice: %.2f %%\n',IDX,thisMax);
P_swamp_aOD = 100*sum(pipsResult>=65,2)/n_mc;
[thisMax,IDX]=max(P_swamp_aOD);
fprintf('highest chance of going down swamp after OD with %.f dice: %.2f %%\n',IDX,thisMax);

14 
 Thumb up
1.25
 tip
 Hide
  • [+] Dice rolls
Brian Church

Seattle
Washington
msg tools
mbmb
I love this
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sum
United States
Columbus
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Hmm, I do not get the same answer as you do. I'm a physicist and I don't deal with statistics, so I am not familiar the idea behind your calculation.

However, if you want to calculate the expectation value, I think it should be...

(10^(n-1)*(n)-(n-1)(10))/10^n * 4 * 5.5 * n

This says that 5 dice would give an expectation value of 55 and would be the best choice for 4 survivors. It's interesting that our calculation agrees for n=1,2,3 but differs for the rest. Maybe I have made a mistake, I haven't had all my coffee yet.

Also, I did not run your Monte Carlo code, but I am confused what it does. This is an analytical problem with an analytical solution, so why would you need a Monte Carlo? Not meant as criticism, just genuinely interested. Again, this is out of my expertise.

edit: Also, thanks for presenting this. I do love mixing math with board games
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
michael H.
msg tools
Hey Sum,

I don't understand how you derive your formula, sorry.

My approach was to first determine what the sweet spot in terms of number of dice is, the second part (monte carlo run) was meant to
A) see if my approach was correct
B) determine the chance of surpassing any given threshold (calculating this analytically takes a bit more effort)

So the upper part of the code only returns the expected mean outcome using bernoulli trial:

There are 4 possible outcomes, either 1, 2, 3, or all 4 survivor rolls will count towards the total sum.
The probability "P(n)" that the roll result of any survivor counts is:
(1-1/10)*(1-2/10)*...*(1-(n-1)/10)
OR
10!/(10-n)!/10^n
You can get the binomial coefficient "b(i)" with nchoosek
The mean expected pips is then
SUM_(i=1:4) { b(i)*P^(i)*(1-P)^(4-i)*5.5*i }


The Monte Carlo run is pretty much just a randomizer (rolls ten d10 x*4 times) and counting the pips (if there are no doubles). The matrix "pipsResult" stores the total roll result.
x1 direction is the run#,
x2 direction is the number of dice used for each survivor roll - starting from 1 (top) to 10 (bottom)

Maybe it's quicker to do the randomizer in one step, I will have to see.


edit: I think the correct terminus is "binomial experiment"
edit2: Your formula says, that if you roll with 11 dice, your expected outcome is 266. Shouldn't it be more like ... zero?
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sum
United States
Columbus
Ohio
flag msg tools
badge
Avatar
mbmbmbmbmb
Hmm, yeah I seem to have some error. I am over-counting states somehow.

Anyway, I wrote a script to check with brute force and I get the same result as you! 3 dice is the best.

edit: Maybe I'll try and re-derive tomorrow at lunch and see if I can come up with your result, thanks!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
michael H.
msg tools
Hey Sum,

thats nice to hear you get the same result. Yeah, the most straight forward approach is to let the cpu run some numbers
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.