Categories
Reversing

Meet The Chomps: Part II

One last thing I wanted to do for the reverse engineering effort I did last week was get exact probability values for the different multipliers. I figured the easiest way was to generate all permutations of bite orders for “Big Chomp wins” and then use Python’s fraction library to multiply and sum out the exact odds (since all permutations are mutually exclusive). Maybe there’s a better way, but seems to have worked decently well:

from fractions import Fraction

# Get winner for a given state, if any
def evaluate(string):
    big_score = 0
    little_score = 0
    for c in string:
        if c == 'b':
            big_score += 1
        elif c == 'B':
            big_score += 2
        elif c == 'l':
            little_score += 1
        else:
            little_score += 2
    if big_score >= 6:
        return 'B'
    elif little_score >= 6:
        return 'L'
    else:
        return None

# Generate next possible permutations
def next_permutations(string):
    result = set()
    result.add(string + 'b')
    result.add(string + 'B')
    result.add(string + 'l')
    result.add(string + 'L')
    return result

# Build all possible win states
def get_permutations():
    visited = set()
    finished = set()
    candidates = next_permutations("")
    while candidates:
        current = candidates.pop()
        winner = evaluate(current)
        if winner is None:
            # Get next permutations
            next = next_permutations(current)
            for next_candidate in next:
                if next_candidate not in visited:
                    candidates.add(next_candidate)
                    visited.add(next_candidate)
        elif winner == 'B':
            finished.add(current)
    return finished

# Get odds multiplication table
one_bite_chance = Fraction(6, 10)
def get_probability_map(big_probability):
    result = {
        'b': big_probability * one_bite_chance,
        'B': big_probability * (1 - one_bite_chance),
        'l': (1 - big_probability) * one_bite_chance,
        'L': (1 - big_probability) * (1 - one_bite_chance)
    }
    return result              

# Get probability of a given state occurring
def get_probability(string, probability_map):
    result = 1
    for c in string:
        result *= probability_map[c]
    return result

# Get total probability for Big Chomp winning
permutations = get_permutations()
def get_total_probability(big_probability):
    probability_map = get_probability_map(big_probability)
    total = 0
    for string in permutations:
        total += get_probability(string, probability_map)
    return(total)

# Now get the total odds for each Big Chomp bite-chance
entries = {
    4 : Fraction(5, 10),
    8 : Fraction(6, 10),
    16 : Fraction(7, 10),
    32 : Fraction(8, 10),
    64 : Fraction(9, 10)
}
for multiplier, big_probability in entries.items():
    big_odds = get_total_probability(big_probability)
    little_odds = 1 - big_odds
    print("{}x: {} ~= {}".format(multiplier, little_odds, little_odds.numerator / little_odds.denominator * 100.0))

Which outputs some huge fractions, and the percentages are prettified as follows:

MultiplierPercentage
450.000%
829.073%
1612.799%
323.540%
640.346%

The empirical numbers were pretty close!

Leave a Reply

Your email address will not be published. Required fields are marked *