задача на поиск оптимальной стратегии [Hearthstone]

marina1206

Интересная задача по теории вероятностей навеяна карточной игрой Hearthstone студии Blizzard.
Для решения задачи разбираться в игре не обязательно, поскольку она будет сформулирована довольно абстрактно.
Игровой валютой в Hearthstone является золото, которое, конечно же, можно покупать за реальные деньги, а можно
и зарабатывать в самой игре, в том числе, выполняя ежедневные квесты. О последних и пойдет речь в задаче.
Система ежедневных квестов выглядит следующим образом. Ровно раз в сутки, скажем, в 00:00 случайным образом
для игрока выпадает один из нескольких возможных квестов. Этот квест попадает в одну из трех свободных
ячеек. Если свободных ячеек нет, то он сгорает. Таким образом, для игрока одновременно доступно может быть
0, 1, 2 или 3 квеста. При этом квесты могут повторяться, то есть наличие в ячейках одного конкретного квеста не исключает
его повторного выпадания. Ровно один раз в сутки можно заменить любой из доступных (уже находящихся в ячейках) квестов
на новый случайным образом выбранный квест.
При выполнении квеста игрок получает на свой счет определенное количество золота, в зависимости от типа квеста.
В данной задаче мы будем считать, что выполнить любой из квестов очень просто, поэтому их игровая суть
нас здесь волновать не будет (на самом деле, их выполнить действительно просто).
Один хороший человек набрал статистику по выпадению квестов из 107 попыток. Статистика не очень большая,
но мы будем использовать именно ее в качестве априорного распределения.
В таблице приведены возможные варианты квестов (первая колонка
сумма вознаграждения за квест (вторая колонка число выпадения каждого типа квеста (третья колонка и
эмпирическая вероятность выполнения каждого типа квеста (четвертая колонка).
Фактически нас интересуют только суммарные вероятности, указанные в самом низу.

Используя указанные данные, требуется найти стратегию по получению наибольшего количества золота в день
и найти математическое ожидание этого количества. При этом можно считать, что процесс продолжается
длительное (бесконечное) время.

igor196505

У меня жена очень далека от матстата, но квесты за 40 она пытается менять, а за 60 - никогда.
PS: там ещё есть квест - посмотреть за чужой игрой, за который не дают золото, а дают колоду карт.

marina1206

У меня жена очень далека от матстата, но квесты за 40 она пытается менять, а за 60 - никогда.
ну сама стратегия, на мой взгляд, довольно очевидна)
основная задача здесь, конечно, посчитать мат ожидание

griz_a

Что-то я не понял, чего тут за сложность?
В день мы получаем, как ни крути, один квест. Если он был за 40, то мы его поменяем. Итого, имеем квест за 40 с вероятностью (1-p-r)^2, квест за 60 с вероятностью (2-p-r)r, за 100 c вероятностью (2-p-r)p, где p - 0.019, r = 0.168

marina1206

Ну это не оптимальная стратегия даже качественно ;)
После первой замены никто не заставляет квест сразу же выполнять. Он может остаться до завтра, когда
может (а может и нет) выпасть квест за 60 или за 100. А если его сразу же выполнить, то завтрашняя замена
останется не использованной, что, очевидно, приводит к понижению мат ожидания.
Ну ок, я предлагаю сначала найти мат ожидание такой стратегии, а потом найти еще более оптимальную :)

sweettydo

нужно играть аренки в плюс и не :censored: :cool:

marina1206

нужно играть аренки в плюс и не выебываться
это тоже понятно, но к задаче отношения не имеет)

griz_a

Тогда похитрее.
Рассмотрим цикл до момента обнуления слотов. Пусть длина такого цикла - сл. величина T_i, а выигрыш за него X_i, а к моменту k у нас уместилось N_k таких циклов.
E(выигрыша за N дней)/N = E(X_1+...+X_{N_k})/N + E(выигрыша за последний неполный цикл)/N.
Последнее слагаемое стремится к 0, если только ET_i конечно.
С другой стороны, N_k - момент остановки для (X_i,T_i поэтому E(X_1+...+X_{N_k}) = EX_1 EN_k.
EN_k/N сходится к 1/ET_1 по теореме восстановления.
Значит ответом будет EX_1/ET_1.
Осталось понять как устроены циклы до обнуления занятых слотов. Считаем, что стратегия такова: любые 60 и 100 мы тут же разыгрываем, а 40 меняем. Если не поменялось, то ждем дальше. Если же получилось 3 слота занятых после обмена, то придется сыграть квест за 40.
C вероятностью 1-(1-p-r)^2 T_1= 0
C вероятностью (1-p-r)^2 мы попадаем в ситауцию, когда в одном слоте болтается 40, а остальные свободны.
Из этой ситуации мы можем: с вероятностью (1-p-r)^2 перейти в ситуацию когда два слота заняты по 40, с вероятностью 2(1-p-rp+r) в ситуация с одним занятым слотом, если мы делали обмен, но из двух пришедших квестов один был за 40, c вероятностью (p+r)^2 мы очищаем слоты.
Аналогичная ситуация со случае 2 занятых слотов, только там в 3 занятых слота мы не переходим, а разыгрываем один из них.
Итого, если E0, E1, E2 - среднее время до обнуления, если в начале занято 0,1,2 слота, то
E0 = (1-p-r)^2 E1 + 1
E1 = (1-p-r)^2 E2 + 2(1-p-rp+r) E1 + 1
E2 = (1-(p+r)^2) E2 + (p+r)^2 E1+ 1
Если решить, то вроде выходит E0 = ET_1 = 1-p-r)^4 + (p+r)^2(1-p-r)^2 + (p+r)^4)/ (p+r)^4 (p+r)^4)
Теперь та же песня со средним выигрышем до обнуления числа слотов, если в начале было i слотов. Назовем их F0, F1, F2
Тогда
F0 = (1-p-r)^2 F1 + 60 (2-p-r)p + 100 (2-p-r) r
F1 = (1-p-r)^2 F2 + 2 (60 + F1) (1-p-r) p + 2(100 + F1) (1-p-r) r + 120 p^2 + 2*160 pr + 200 r^2
F2 = (40+F2) (1-p-r)^2 + (F1+ 200) r^2+ 2(F1+160) pr+ (F1+120) p^2 + 2r(1-p-r) (F2+100) + 2p(1-p-r) (F2 + 60)
Эту систему мне решать лениво, но если из нее найти F_0, то F_0/E_0 это и будет ответ

marina1206

Похоже на правду. Пока не до конца вник в решение, попозже гляну еще.
Оставить комментарий
Имя или ник:
Комментарий: