双游戏角色对战获胜概率计算技术问询

Alright, let's break down how to calculate Character 1's win probability in this turn-based battle scenario. First, let's clarify the exact win condition: Character 1 wins only if Character 2's HP drops to ≤0 while Character 1's HP remains >0. If both characters die in the same round, that's a tie and doesn't count as a win for Character 1.

We'll use a DP state to represent the win probability from any given HP state of the two characters. Here's the breakdown:

State Definition #

Let dp[a][b] = the probability that Character 1 wins when Character 1 has a HP remaining and Character 2 has b HP remaining.

Boundary Conditions #

• If a ≤ 0: Character 1 is already dead, so dp[a][b] = 0.0 (no chance to win)
• If b ≤ 0: Character 2 is already dead, so dp[a][b] = 1.0 (Character 1 has already won)

State Transition #

For each state (a, b) where both characters are alive:

1. Calculate the total number of possible attack combinations: total = (max1 + 1) * (max2 + 1) (since each character can deal 0 to their max damage, inclusive). Each combination has an equal probability of 1/total.
2. Iterate over all possible attack values (hit1 for Character 1, hit2 for Character 2):
   • Compute the new HP values: new_a = a - hit2, new_b = b - hit1
   • If new_b ≤ 0 and new_a > 0: This combination results in a win for Character 1, so add 1.0 to the total win probability sum.
   • If new_a > 0 and new_b > 0: This leads to a new state (new_a, new_b), so add dp[new_a][new_b] to the sum (we'll reuse the precomputed probability for that state).
   • All other cases (Character 1 dies, or both die) contribute 0 to the sum.
3. Divide the total sum by total to get dp[a][b].

Let's take a simple example:

• Character 1: max1=1, hp1=2
• Character 2: max2=1, hp2=2

Total attack combinations: (1+1)*(1+1) = 4.
For state (2,2):

• Hit1=0, Hit2=0: New state (2,2) → add dp[2][2]
• Hit1=0, Hit2=1: New state (1,2) → add dp[1][2]
• Hit1=1, Hit2=0: New state (2,1) → add dp[2][1]
• Hit1=1, Hit2=1: Both new HP are 1 → add dp[1][1]

Calculating sub-states leads to dp[2][2] = 4/9 ≈ 0.444—which matches the output of the code below.

We'll use memoization to avoid recalculating the same states multiple times:

from functools import lru_cache

def calculate_char1_win_probability(max1, hp1, max2, hp2):
    @lru_cache(maxsize=None)
    def dp(current_hp1, current_hp2):
        # Base cases
        if current_hp1 <= 0:
            return 0.0
        if current_hp2 <= 0:
            return 1.0
        
        total_combinations = (max1 + 1) * (max2 + 1)
        win_prob_sum = 0.0
        
        # Iterate all possible attack values
        for hit1 in range(max1 + 1):
            for hit2 in range(max2 + 1):
                new_hp1 = current_hp1 - hit2
                new_hp2 = current_hp2 - hit1
                
                if new_hp2 <= 0 and new_hp1 > 0:
                    # Character 1 wins this round
                    win_prob_sum += 1.0
                elif new_hp1 > 0 and new_hp2 > 0:
                    # Battle continues, add the probability from the new state
                    win_prob_sum += dp(new_hp1, new_hp2)
                # Else: either Character 1 dies or both die, add 0
        
        return win_prob_sum / total_combinations
    
    return dp(hp1, hp2)

# Test the example above
print(calculate_char1_win_probability(1, 2, 1, 2))  # Output: ~0.4444444444444444

For large values of HP or max damage, the nested loops can be slow. Here are a couple of optimizations:

1. Prefix Sum Calculation: Instead of iterating every possible hit value, calculate ranges of hits that result in an immediate win, then use prefix sums to compute the sum of sub-state probabilities faster.
2. Iterative DP Table: For very large HP values, a recursive approach might hit stack limits. Instead, build a 2D table iteratively, starting from states with low HP and working up to the target state.

内容的提问来源于stack exchange，提问作者edward lami