Здравствуйте, SEH, Вы писали:
SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше. SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат. SEH>Какова наиболее выигрышная стратегия?
А вот и подтверждение моим опасением на счет алгоритма "Бери, если больше 0.5"!
Оказывается, если бросать не 10, а 20 раз, то этот алгоритм уже не оптимальный.
Выигрыш при 20 бросках при алгоритме "Бери, если больше 0.5" равен 0.763351. А можно получать в среднем 0.763413.
Стратегия такая же, за исключением:
* При 7, если выпало 4, продолжаем играть.
* При 9, если выпало 5, продолжаем играть.
* При 11, если выпало 6, продолжаем играть.
Здесь сказывается именно тот эффект, который я предсказал вот тут
. А именно, иногда может оказаться, что текущий выигрыш чуть больше 0.5, но близок к 0.5, и тогда положительный эффект от стратегии при продолжении игры может оказаться выше отрицательного эффекта от уменьшения мат.ожидания!
Если сравнить ситуации, когда после 2n+1 бросков получилось n решек, то с увеличением n происходят две вещи. Во-первых, n/(2n+1) становится меньше, т.е. возникает желание продолжить. С другой стороны, времени до конца бросков остается все меньше. Близко к финишу положительный эффект от стратегии уже не успеет себя проявить.
Поэтому, 2/3 мы берем (слишком большое, чтобы не брать), 4/7 не берем (уже не такое большое, а времени до финиша еще много), а 7/13 уже берем (времени до финиша осталось мало), хотя 7/13 меньше, чем 4/7.
P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.
А вот зайца кому, зайца-выбегайца?!
Re[2]: Подбросить монетку или нет (стратегия): не брать боль
V>Оказывается, если бросать не 10, а 20 раз, то этот алгоритм уже не оптимальный. V>Выигрыш при 20 бросках при алгоритме "Бери, если больше 0.5" равен 0.763351. А можно получать в среднем 0.763413. V>Стратегия такая же, за исключением: V>* При 7, если выпало 4, продолжаем играть. V>* При 9, если выпало 5, продолжаем играть. V>* При 11, если выпало 6, продолжаем играть.
V>Здесь сказывается именно тот эффект, который я предсказал вот тут
. А именно, иногда может оказаться, что текущий выигрыш чуть больше 0.5, но близок к 0.5, и тогда положительный эффект от стратегии при продолжении игры может оказаться выше отрицательного эффекта от уменьшения мат.ожидания!
V>Если сравнить ситуации, когда после 2n+1 бросков получилось n решек, то с увеличением n происходят две вещи. Во-первых, n/(2n+1) становится меньше, т.е. возникает желание продолжить. С другой стороны, времени до конца бросков остается все меньше. Близко к финишу положительный эффект от стратегии уже не успеет себя проявить.
V>P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.
D>находит это решение:
>>>> print(foo(0., 0., 20)) D>0.763412800336
D>Это брутфорс, но он работает несколько секунд. Плюс еще можно ускорить (если добавить мемоизацию, то экспонента превратится в N^3).
Это сообщение я как-то пропустил. Это не просто брутфорс, а динамическое программирование. Другой вариант. По сути оптимальное решение ищется с хвоста. Пожтому и работает быстро. Значит идея о том, что брать всегда больше 0.5 неправильно, подтвердилась. Супер.
А вот зайца кому, зайца-выбегайца?!
Re[4]: Подбросить монетку или нет (стратегия): не брать боль
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, vadimcher, Вы писали:
V>>Значит идея о том, что брать всегда больше 0.5 неправильно, подтвердилась. Супер.
N>Похоже, что связано со случайным блужданием и матожиданием максимального отклонения...
Похоже на то.
Идея о том, что стратегия "бери больше 0.5" не всегда оптимальная родилась на самом деле из того, что... она оптимальная в поставленной задаче. Если сравнить две стратегии А:"бери больше 0.5" и Б:"бери больше или равно 0.5", то выясняется, что первая лучше второй. Хотя казалось бы, если текущий выигрыш 0.5, то мат.ожидание будущего выигрыша тоже 0.5 для любого числа ходов. Но возможность остановиться в любой момент делает мат.ожидание больше 0.5, если продолжить (просто для тех траекторий, которые идут сначала хорошо, т.е. выигрыш растет, а затем плохо, т.е. выигрыш падает, мы во время останавливаемся, а для остальных -- играем до конца). Именно этот положительный эффект делает стратегию А лучше стратегии Б.
Ну а дальше стало не очевидно, почему этот положительный эффект должен всегда быть меньше отклонения от 0.5. Если текущий выигрыш меньше 0.5, то оба эффекта (от изменения мат.ожидания и стратегии остановки) идут в плюс, т.е. продолжать надо. Если ровно 0.5, то первый нулевой, а второй положительный. Если же больше 0.5, то один отрицательный, а другой положительный. И подумалось, что если игра достаточно долгая, то отклонение при большом числе бросков может быть маленьким, а играть еще долго, тогда может и при текущем выигрыше больше 0.5 стоит продолжать.
А вот зайца кому, зайца-выбегайца?!
Re[2]: Подбросить монетку или нет (стратегия): не брать боль
Здравствуйте, vadimcher, Вы писали:
V>P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.
Вопрос сколько раз можно играть в игру?
Если заходов сколь угодно много, то играем по следующей стратегии.
Каждый ход — новая игра.
Если выпала решка — завершаем игру и забираем бакс.
Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.
Если заход ровно 1.
Больше 1$ не выйграем. Так что устанавливаем свой желаемый порог выйгрыша в диапазоне от 0 до 1 и ждем.
Когда-нибудь да выпадет достаточное кол-во решек пордряд и мы выйграем необходимую сумму. Возможно ждать придется долго, но когда-нибудь дождемся.
SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше. SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат. SEH>Какова наиболее выигрышная стратегия?
G>Если заходов сколь угодно много, то играем по следующей стратегии. G>Каждый ход — новая игра. G>Если выпала решка — завершаем игру и забираем бакс. G>Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.
За каждую игру ты должен отбить максимальный баблос.
То есть ты играешь много игр, и в среднем тебе нужно максимизировать отношение отбитый баблос/кол-во игр.
Стратегия "Если выпал орел — завершаем игру с 0" не удовлетворяет этой цели -- ты взял ноль, в то время как у тебя был шанс отбить еще денег.
G>Каждый ход — новая игра. G>Если выпала решка — завершаем игру и забираем бакс. G>Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.
то есть ты максимизируешь отношение заработанные деньги/кол-во бросков кубика. А нужно максимизировать отношение заработанные деньги/кол-во игр, потому что тебе предъявят счет за кол-во игр, а не за кол-во бросков.
D>Стратегия "Если выпал орел — завершаем игру с 0" не удовлетворяет этой цели -- ты взял ноль, в то время как у тебя был шанс отбить еще денег.
Не понятно, почему ты нормируешь деньги на игры, а не на что-то пропорциональное времени, на броски, например
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>Не понятно, почему ты нормируешь деньги на игры, а не на что-то пропорциональное времени, на броски, например
видимо, потому что в описании задачи вопрос звучит "What is the fair price of this game?"
То есть "сколько можно отбить денег на этой игре". Игра -- это серия бросков.
