看到optiver赛马问题。假如有4匹马，能力为a,b,c,d，随机分组淘汰赛。每一句胜率与能力正比，比如a和b比赛，a的胜率就是a/(a+b). 要求快速计算或估算某一匹马胜率。
想凭直觉估算，精确求解是不可能的。我们不妨简化问题：先normalize到a=1，a马的胜率和mean(b,c,d), std(b,c,d) 有何关系？
import numpy as np
import matplotlib.pyplot as plt
def calculate_analytical_prob(a, b, c, d):
P_subcase_1a = (a / (a + b)) * (c / (c + d)) * (a / (a + c))
P_subcase_1b = (a / (a + b)) * (d / (c + d)) * (a / (a + d))
P_subcase_2a = (a / (a + c)) * (b / (b + d)) * (a / (a + b))
P_subcase_2b = (a / (a + c)) * (d / (b + d)) * (a / (a + d))
P_subcase_3a = (a / (a + d)) * (b / (b + c)) * (a / (a + b))
P_subcase_3b = (a / (a + d)) * (c / (b + c)) * (a / (a + c))
return (1/3) * (P_subcase_1a + P_subcase_1b + P_subcase_2a + P_subcase_2b + P_subcase_3a + P_subcase_3b)
# Set a = 1 and simulate 10,000 random pickings of b, c, d from uniform(0,2)
a = 1
n_simulations = 10000
avg_ratios = []
square_ratios = []
std_ratios = []
winning_rates = []
for _ in range(n_simulations):
b, c, d = np.random.uniform(0, 2, 3)
avg_ratio = np.mean([b, c, d]) / a
square_ratio = np.mean([b**2,c**2,d**2])**.5
std_ratio = np.std([b, c, d]) / a
prob_a_wins = calculate_analytical_prob(a, b, c, d)
square_ratios.append(square_ratio)
avg_ratios.append(avg_ratio)
std_ratios.append(std_ratio)
winning_rates.append(prob_a_wins)
# Create a 2D histogram plot
plt.figure(figsize=(10, 6))
plt.scatter(avg_ratios, std_ratios, c=winning_rates, cmap='viridis', marker='o', s=10)
plt.colorbar(label='Winning Rate of a')
plt.xlabel('avg(b, c, d) / a')
plt.ylabel('std(b, c, d) / a')
plt.title('Winning Rate of a vs. avg(b, c, d) / a and std(b, c, d) / a')
plt.grid(True)
plt.show()
可以看到，胜率和mean(b,c,d) 非常相关，但是和std关系不大：
想一想，winning prob 大致会和mean是什么关系呢？
如果b=c=d=1,不难计算，winning rate = 1/4, 首先猜想1/(1+b+c+d)并画图
可以看到correlation非常明显，但线还不是很直。
根据mean(b+c+d)--> 0 or inf求极限，不难得到另一个猜想，并画winning prob VS 1/(1+mean）^2
这就非常直了。改变simulate时bcd的分布，可以自行总结近似公式：
当mean(b,c,d)>1时，p(a win) = 1/(1+mean)^2
当mean(b,c,d)<1时，p(a win) = 1/(1+mean)^2 * (1- 0.06*std/mean)
对于8匹马的情况，同样先写代码观察：
import itertools
def calculate_8_player_win_rate(a, *other_players):
other_players = list(other_players)
win_prob = 0
# Generate all combinations of 3 players to pair with 'a'
for subgroup in itertools.combinations(other_players, 3):
# Calculate the probability that 'a' wins in its group of 4
a_group_prob = calculate_analytical_prob(a, *subgroup)
# The remaining 4 players are in the other group
remaining_players = [p for p in other_players if p not in subgroup]
# Calculate probability that 'a' wins against each possible winner from the other group
for player in remaining_players:
# Probability that this player wins the other group
other_group_prob = calculate_analytical_prob(player, *[p for p in remaining_players if p != player])
# Probability that 'a' wins against this player
a_vs_player_prob = a / (a + player)
# Add to the total win probability for 'a'
win_prob += a_group_prob * other_group_prob * a_vs_player_prob
return win_prob / len(list(itertools.combinations(other_players, 3)))
写完记得simulate10000场游戏验证simulation和analytical计算的概率是否一致您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式 游客，您好！ 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 VIP即刻解锁阅读权限 或 查看其他获取积分的方式
b, c, d, e, f, g, h = generate_scaled_players(mean, std)
# Calculate mean and std of the scaled abilities
actual_mean = np.mean([b, c, d, e, f, g, h])
actual_std = np.std([b, c, d, e, f, g, h])
# Calculate guess
guess = 1 / (1 + actual_mean)**3
# Calculate analytical win rate
win_rate = calculate_8_player_win_rate(a, b, c, d, e, f, g, h)
# Calculate deviation
deviation = 1 - win_rate / guess
# Keep track of the values
means.append(actual_mean)
stds.append(actual_std)
guesses.append(guess)
win_rates.append(win_rate)
deviations.append(deviation)
return means, stds, guesses, win_rates, deviations
# Run the simulation
means, stds, guesses, win_rates, deviations = simulate_combination_stats()
自行总结近似公式：
当mean>1时，p(a win) = 1/(1+mean)^3
当mean<1时，p(a win) = 1/(1+mean)^3 * (1-0.15*std/mean)
|
狗仔卡
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
