[M] Mafia Goons
[T] Vanilla Town
Calculating EV
Let X=int((T-M+1)/2); X is the number of mislynches needed for a Mafia win.
EV[0,X] = 1; EV[M,0] = 0
EV[M,X] = ( M*EV[M-1,X] + (M+2X-1)*EV[M,X-1] ) / (2M+2X-1), for M,X>0
(If M+T is even, town should no lynch day 1 to restore parity; this does not cost them a mislynch, so the X calculated above is the same.)
For a given N=M+X-1, the denominator of EV[M,X] is found in the OEIS:
A001803
For EV[1,X], the numerator is:
A173384
For EV[M,1], the numerator is:
A060818
Vanilla EV Identity
2^M * EV[M,1] = 1 - EV[1,M]
Exact EV up to 27 players (divide by first number):
Code: Select all
M 0 1 2 3 4 5 6 7 8 9 10 11 12 13
P
1 1
3 3 1
5 15 7 2
7 35 19 8 2
9 315 187 94 36 8
11 693 437 244 114 40 8
13 3,003 1,979 1,186 624 272 88 16
15 6,435 4,387 2,768 1,578 784 320 96 16
17 109,395 76,627 50,294 30,396 16,504 7,760 2,976 832 128
19 230,945 165,409 112,028 70,802 41,016 21,240 9,472 3,424 896 128
21 969,969 707,825 491,870 322,104 196,096 108,984 53,904 22,848 7,808 1,920 256
23 2,028,117 1,503,829 1,067,720 719,790 455,840 267,472 142,752 67,536 27,264 8,832 2,048 256
25 16,900,975 12,706,671 9,188,406 6,346,180 4,150,600 2,542,880 1,439,040 738,304 334,592 128,896 39,680 8,704 1,024
27 35,102,025 26,713,417 19,624,884 13,836,426 9,296,040 5,899,720 3,498,240 1,910,720 943,360 410,112 151,040 44,288 9,216 1,024
EV as percentage to 2 decimal places up to 99 players and 10 Mafia (E = T-M):
Code: Select all
M 0 1 2 3 4 5 6 7 8 9 10
E
1 100% 33.33% 13.33% 5.71% 2.54% 1.15% 0.53% 0.25% 0.12% 0.06% 0.03%
3 100% 46.67% 22.86% 11.43% 5.77% 2.93% 1.49% 0.76% 0.39% 0.20% 0.10%
5 100% 54.29% 29.84% 16.45% 9.06% 4.97% 2.72% 1.48% 0.80% 0.44% 0.23%
7 100% 59.37% 35.21% 20.78% 12.18% 7.09% 4.10% 2.36% 1.34% 0.76% 0.43%
9 100% 63.06% 39.49% 24.52% 15.09% 9.20% 5.56% 3.33% 1.98% 1.17% 0.68%
11 100% 65.90% 43.01% 27.79% 17.76% 11.24% 7.04% 4.37% 2.69% 1.64% 0.99%
13 100% 68.17% 45.97% 30.66% 20.22% 13.19% 8.51% 5.44% 3.45% 2.16% 1.35%
15 100% 70.05% 48.51% 33.21% 22.48% 15.05% 9.97% 6.53% 4.24% 2.73% 1.74%
17 100% 71.62% 50.71% 35.49% 24.56% 16.81% 11.38% 7.63% 5.07% 3.33% 2.17%
19 100% 72.97% 52.65% 37.55% 26.48% 18.48% 12.75% 8.72% 5.90% 3.96% 2.63%
21 100% 74.15% 54.37% 39.42% 28.27% 20.05% 14.08% 9.79% 6.74% 4.60% 3.11%
23 100% 75.18% 55.91% 41.12% 29.93% 21.55% 15.36% 10.84% 7.58% 5.25% 3.61%
25 100% 76.10% 57.30% 42.69% 31.47% 22.97% 16.60% 11.88% 8.42% 5.92% 4.12%
27 100% 76.93% 58.57% 44.13% 32.92% 24.31% 17.78% 12.88% 9.25% 6.58% 4.65%
29 100% 77.67% 59.72% 45.47% 34.28% 25.59% 18.93% 13.87% 10.07% 7.25% 5.18%
31 100% 78.35% 60.79% 46.71% 35.55% 26.81% 20.02% 14.83% 10.88% 7.92% 5.71%
33 100% 78.97% 61.77% 47.87% 36.75% 27.96% 21.08% 15.76% 11.68% 8.58% 6.26%
35 100% 79.53% 62.68% 48.95% 37.89% 29.06% 22.10% 16.66% 12.46% 9.24% 6.80%
37 100% 80.06% 63.53% 49.97% 38.96% 30.12% 23.08% 17.55% 13.23% 9.89% 7.34%
39 100% 80.55% 64.32% 50.93% 39.98% 31.12% 24.03% 18.40% 13.98% 10.54% 7.88%
41 100% 81.00% 65.06% 51.83% 40.95% 32.09% 24.94% 19.23% 14.72% 11.18% 8.42%
43 100% 81.42% 65.76% 52.68% 41.87% 33.01% 25.82% 20.04% 15.44% 11.80% 8.96%
45 100% 81.82% 66.41% 53.49% 42.75% 33.90% 26.67% 20.83% 16.15% 12.42% 9.49%
47 100% 82.19% 67.03% 54.26% 43.58% 34.74% 27.49% 21.59% 16.84% 13.04% 10.02%
49 100% 82.54% 67.62% 54.99% 44.38% 35.56% 28.29% 22.34% 17.51% 13.64% 10.55%
51 100% 82.87% 68.17% 55.68% 45.15% 36.35% 29.05% 23.06% 18.18% 14.23% 11.06%
53 100% 83.18% 68.70% 56.34% 45.88% 37.10% 29.80% 23.76% 18.82% 14.81% 11.58%
55 100% 83.47% 69.20% 56.97% 46.59% 37.83% 30.52% 24.45% 19.46% 15.38% 12.09%
57 100% 83.75% 69.68% 57.58% 47.26% 38.54% 31.21% 25.12% 20.08% 15.95% 12.59%
59 100% 84.02% 70.13% 58.16% 47.91% 39.22% 31.89% 25.77% 20.69% 16.50% 13.08%
61 100% 84.27% 70.57% 58.71% 48.54% 39.87% 32.55% 26.40% 21.28% 17.05% 13.57%
63 100% 84.51% 70.98% 59.25% 49.14% 40.51% 33.18% 27.02% 21.86% 17.58% 14.05%
65 100% 84.75% 71.38% 59.76% 49.72% 41.12% 33.80% 27.62% 22.43% 18.11% 14.53%
67 100% 84.97% 71.76% 60.25% 50.29% 41.72% 34.40% 28.20% 22.99% 18.62% 15.00%
69 100% 85.18% 72.13% 60.73% 50.83% 42.29% 34.99% 28.78% 23.53% 19.13% 15.47%
71 100% 85.38% 72.49% 61.19% 51.35% 42.85% 35.56% 29.33% 24.06% 19.63% 15.92%
73 100% 85.58% 72.83% 61.63% 51.86% 43.40% 36.11% 29.88% 24.59% 20.12% 16.37%
75 100% 85.76% 73.15% 62.06% 52.35% 43.92% 36.65% 30.41% 25.10% 20.60% 16.82%
77 100% 85.94% 73.47% 62.47% 52.83% 44.43% 37.17% 30.93% 25.60% 21.08% 17.26%
79 100% 86.12% 73.77% 62.87% 53.29% 44.93% 37.69% 31.44% 26.09% 21.54% 17.69%
81 100% 86.28% 74.07% 63.25% 53.74% 45.42% 38.18% 31.94% 26.57% 22.00%
83 100% 86.45% 74.35% 63.63% 54.17% 45.89% 38.67% 32.42% 27.05%
85 100% 86.60% 74.63% 63.99% 54.59% 46.35% 39.15% 32.90%
87 100% 86.75% 74.89% 64.34% 55.00% 46.79% 39.61%
89 100% 86.90% 75.15% 64.68% 55.40% 47.23%
91 100% 87.04% 75.40% 65.01% 55.79%
93 100% 87.18% 75.65% 65.34%
95 100% 87.31% 75.88%
97 100% 87.44%
Python code for memory-efficient EV calculation:
Code: Select all
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Mafia EV calculator for Vanilla
f1_2 = open('output_vanilla_1_2', 'w')
max_m = 1001
# This algorithm caches the EV for each m at the previous player count
# All current player count EV can be calculated from these
# Initialize the arrays
previous = [0.0 for i in range(max_m)]
previous[0] = 1.0
current = [0.0 for i in range(max_m)]
z = 3
flag = False
while True:
for m in range(max_m):
if ( 0 == m ):
# Town win
current[m] = 1.0
elif ( z < 2*m ):
# Mafia win
current[m] = 0.0
else:
# EV calculation for day outcome; m/z probability of lynching Mafia, etc.
current[m] = ( m*previous[m-1] + (z-m)*previous[m] )/z
# Find values on either side of EV = 1/2
if ( 1.0/2.0 <= current[m] and 1.0/2.0 >= previous[m] ):
# If both are exactly 1/2, we have reached the limit of our floating point precision
if ( 1.0/2.0 == current[m] and 1.0/2.0 == previous[m] ):
f1_2.write(str(m) + '\t' + str(z-2) + '\t' + str(previous[m]) + '\t' + str(previous[m]) + '\n')
exit()
else:
# Interpolate estimate of z if player count were continuous
estimate = z - 2.0 + ( 2.0*1.0/2.0 - 2*previous[m] )/( current[m] - previous[m] )
f1_2.write(str(m) + '\t' + str(z-2) + '\t' + str(previous[m]) + '\t' + str(estimate) + '\n')
print m
# We have reached max value of m, we're done
if ( ( max_m - 1 ) == m ):
exit()
# Cache values for z and clear values for next player count
previous = current
current = [0.0 for i in range(max_m)]
# Increment by 2 - one for lynch, one for nightkill
# Player count is always odd, even player count should always no lynch to restore parity
z += 2