PuzzlOR Fighters

PuzzlOR FIghters¶

http://puzzlor.com/2014-10_Fighters.html

In [1]:

from math import factorial

key = {0:'A',1:'B',2:'C',3:'D'}
attack = [4,3,2,1]
startinghealth = [10,12,16,18]

# Memoization dictionary was pre-loaded with a few values
# for testing purposes.  
#   Key: (Health Values tuple)
#   Value: List of resulting probabilities
memo = {(1,0,0,0):[1,0,0,0],
        (0,1,0,0):[0,1,0,0],
        (0,0,1,0):[0,0,1,0],
        (0,0,0,1):[0,0,0,1]}

In [2]:

# main recursive function

def fight(health,sumlevelprobs):
    
    # count living fighters 
    countlive = 0
    for x in range(4):
        if health[x] > 0:
            countlive += 1
            sumlevelprobs[x]=1
            
    # if only one fighter alive, return list of probabilities
    # with all zeros except the remaining fighter set to one.
    if countlive <= 1:
        return sumlevelprobs

    # probabilities from all branches below this level will be summed
    sumlevelprobs = [0,0,0,0]
    
    # number of equally-likely branches (possible matchups) 
    # is inverted to form the probability of selecting a particular branch 
    branchprob = factorial(countlive-2)/factorial(countlive)
    
    for f1 in range(4):
        for f2 in range(4):
            # consider all possible matchups of living fighters
            # not allowing fighters to fight themselves
            if ( f1!=f2 and health[f1]>0 and health[f2]>0 ):
                # print(key[f1], " attacks ", key[f2])
                tempprobs=[0,0,0,0]
                health[f2]-=attack[f1]  # reduce health of victim for this branch
                # build key to check memoization dictionary
                keylist = [max(0,i) for i in health]
                keytup = tuple(keylist)
                # if key found in memo, use the stored probabilities
                # otherwise do recursive call and store returned probabilities
                if keytup in memo:
                    tempprobs = memo[keytup]
                else:
                    tempprobs=fight(health,tempprobs)
                    memo[keytup]=tempprobs
                health[f2]+=attack[f1]  # reset the victim health 
                # multiply branchprob into returned probabilities
                tempprobs = [i*branchprob for i in tempprobs]
                # then add the scaled probabilities to the total for this level 
                for i in range(4):
                    sumlevelprobs[i]+=tempprobs[i]
                              
    return sumlevelprobs

In [3]:

finalprobs = [0,0,0,0] 
finalprobs = fight(startinghealth,finalprobs)
print("finalprobs ",finalprobs)

finalprobs  [0.2532256631847715, 0.2621288160658021, 0.3210407555816303, 0.1636047651677952]

Charles has the highest probability of winning: 32%