Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Deterministic DP solution in Speedy category for Battle Dice by Renelvon
def analyze_die(die):
"""
Translate each face of the die in a (|numOfAtkIcons|, |numOfDefIcons|)
tuple. Count the maximum number of attack and defence icons that can
appear on a single face.
"""
tdie = tuple((face.count('A'), face.count('D')) for face in die)
maxatk = max(a for a, _ in tdie)
maxdef = max(d for _, d in tdie)
return tdie, maxatk, maxdef
def calc_prolls(tdice, maxatk, maxdef, maxunits):
"""
Create a 'prolls' matrix, where prolls[i][j][k] is the probability
of rolling j attack icons and k defence icons when rolling
i dice. Calculate using DP.
"""
prolls = [[[0 for _ in range(maxdef*maxunits + 1)]
for _ in range(maxatk*maxunits + 1)]
for _ in range(maxunits + 1)]
prolls[0][0][0] = 1.0
p = 1 / len(tdice)
for dice in range(1, maxunits + 1):
for i in range(maxatk*dice + 1):
for j in range(maxdef*dice + 1):
for a, d in tdice:
prolls[dice][i][j] += prolls[dice-1][i-a][j-d] * p
return prolls
def calc_states(units1, units2, proll, maxatk, maxdef):
"""
Calculate the probability of some state (u1, u2) occuring
at some point during the game. DP.
"""
# For each state, calculate the probability that the state
# won't change after a dice roll. Skip calculations for endgame states.
sameprob = [[0 for _ in range(units2 + 1)] for _ in range(units1 + 1)]
for u1 in range(units1, 0, -1):
for u2 in range(units2, 0, -1):
for atk1 in range(u1*maxatk + 1):
for def1 in range(u1*maxdef + 1):
if proll[u1][atk1][def1]:
for atk2 in range(u2*maxatk + 1):
for def2 in range(u2*maxdef + 1):
if proll[u2][atk2][def2]:
nu1 = max(0, min(u1, def1 - atk2 + u1))
nu2 = max(0, min(u2, def2 - atk1 + u2))
if (nu1, nu2) == (u1, u2): # Next == current
p1 = proll[u1][atk1][def1]
p2 = proll[u2][atk2][def2]
sameprob[nu1][nu2] += p1 * p2
# Calculate transitions: For each known state, calculate the probability
# of that state happening anytime during the game.
# Skip calculations for endgame states.
stateprob = [[0 for _ in range(units2 + 1)] for _ in range(units1 + 1)]
stateprob[units1][units2] = 1 # initial
for u1 in range(units1, 0, -1):
for u2 in range(units2, 0, -1):
for atk1 in range(u1*maxatk + 1):
for def1 in range(u1*maxdef + 1):
if proll[u1][atk1][def1]:
for atk2 in range(u2*maxatk + 1):
for def2 in range(u2*maxdef + 1):
if proll[u2][atk2][def2]:
nu1 = max(0, min(u1, def1 - atk2 + u1))
nu2 = max(0, min(u2, def2 - atk1 + u2))
if (nu1, nu2) != (u1, u2): # Next != current
pprev = stateprob[u1][u2]
p1 = proll[u1][atk1][def1]
p2 = proll[u2][atk2][def2]
pnotsame = 1 - sameprob[u1][u2]
stateprob[nu1][nu2] += pprev * p1 * p2 / pnotsame
return stateprob
def checkio(die, units1, units2):
tdie, maxatk, maxdef = analyze_die(die)
prolls = calc_prolls(tdie, maxatk, maxdef, max(units1, units2))
stateprob = calc_states(units1, units2, prolls, maxatk, maxdef)
# Player 1 doesn't win the game if he/she ends with 0 units.
return 1 - sum(stateprob[0])
if __name__ == '__main__':
#These are only used for self-checking and are not necessary for auto-testing
def almost_equal(checked, correct, significant_digits=4):
precision = 0.1 ** significant_digits
return correct - precision < checked < correct + precision
assert(almost_equal(checkio(['A', 'D'], 3, 3), 0.0000)) # It's not immediately obvious, but each player will always lose the same number of units
assert(almost_equal(checkio(['A', 'D'], 4, 3), 1.0000))
assert(almost_equal(checkio(['AA', 'A', 'D', 'DD'], 3, 4), 0.0186))
assert(almost_equal(checkio(['AA', 'A', 'D', 'DD'], 4, 4), 0.4079))
assert(almost_equal(checkio(['AA', 'A', 'D', 'DD'], 5, 4), 0.9073))
June 26, 2014
Comments:
