Условие
Разработчик Сеня вовсю трудится над своей первой RPG-игрой. Чтобы база данных не ложилась от наплыва игроков, он арендовал надежное облако, настроил серверы и приступил к самому интересному — программированию дропа. Сейчас Сеня трудится над механикой выпадения легендарного меча из финального босса. Шанс получить заветный лут составляет ровно 10% при каждом убийстве.
Он решает добавить в игру bad luck protection — защиту от невезения, чтобы игроки не удаляли шедевр Сени после тридцатого бесплодного рейда. Если геймеру долго не везет, на определенном шаге меч должен упасть гарантированно. Чтобы понять, на каком этапе включать костыли помощи, Сене нужно провести расчеты. Начиная с какого по счету убийства босса вероятность того, что игрок хотя бы один раз выбьет меч, превысит 50%? Его мнение: шанс 1 к 10 (то есть 10%), то за 5 попыток суммарный шанс доползет до 50%.
Задача
Вы — чуть более дотошный коллега Сени по геймдеву. Заглянули в его монитор и нашли один важный недочет. Объясните Сене, в чем проблема. Решить задачу можно как через код, так и математическим путем.
Решение
На первый взгляд логика Сени кажется разумной. Если одна попытка дает 10%, то пять попыток должны дать 50%. Но вероятности независимых событий складываются не так;
- Представим, что игрок убил босса один раз. Вероятность не получить меч составляет: 1 − 0.1 = 0.9.
- После двух убийств вероятность не получить меч ни разу будет: 0.9 × 0.9 = 0.9².
- После трёх: 0.9³. И так далее.
- Для N убийств вероятность ни разу не получить меч равна: 0.9ᴺ.
Но нас интересует противоположное событие — получить меч хотя бы один раз. Поэтому воспользуемся правилом дополнения:
P = 1 − 0.9ᴺ
Теперь осталось найти минимальное значение N, при котором вероятность станет больше 50%. Посчитаем несколько первых значений:
| Убийств босса | Вероятность получить меч хотя бы раз |
| 1 | 10% |
| 2 | 19% |
| 3 | 27.1% |
| 4 | 34.39% |
| 5 | 40.95% |
| 6 | 46.86% |
| 7 | 52.17% |
Получается, после пяти попыток шанс вовсе не равен 50%. Он составляет примерно 41%. Впервые вероятность превышает половину только на седьмом убийстве босса.
Пишем код
Чтобы не считать степени вручную и наглядно показать Сене динамику, напишем краткий код на Python. Будем симулировать попытки в цикле, пока не перешагнем порог в 50%.
n = 1
while True:
probability = 1 - 0.9 ** n
if probability > 0.5:
print(n)
break
n += 1
Здесь мы видим точный результат: только на 7-й попытке суммарная вероятность выбить легендарку хотя бы один раз превысит половину и составит 52.17%. Можно написать более интересный и такой же эффективный код:
drop_chance = 0.10 # Шанс дропа 10%
target_probability = 0.50 # Нужный нам порог в 50%
current_fail_chance = 1.0 # Изначально шанс неудачи 100%
attempts = 0
print("Попытка | Шанс выбить хотя бы раз")
print("-" * 33)
while True:
attempts += 1
# Умножаем шанс неудачи на вероятность промаха в текущей попытке
current_fail_chance *= (1 - drop_chance)
# Шанс успеха — это 1 минус общий шанс неудачи
success_chance = 1 - current_fail_chance
print(f"{attempts:^7} | {success_chance:.2%}")
if success_chance > target_probability:
break
print("-" * 33)
print(f"Итог: Шанс превысит 50% на {attempts}-й попытке!")
Алгоритм запускается на микроскопической сложности — O(K), где K — число попыток до достижения цели.
Заключение
Сеня посмотрел на ваши расчеты, почесал затылок, осознал силу геометрического распределения вероятностей и пошел переписывать конфиги дропа на сервере. Заодно он настроил bad luck protection именно на седьмую попытку.
В знак благодарности Сеня угостил вас пиццей, а вы скинули ему ссылку на Академию знаний Selectel. Теперь он точно знает, где читать материалы про алгоритмы, разработку и архитектуру облачных решений, чтобы его RPG не лагала, а код всегда был математически точен 🙂
