Consider a game where you can toss a fair coin up to 10 times. The payoff you get is the number of heads obtained divided by the number of tosses you've taken. After any toss you've got the choice of stopping there and then, taking your payoff, or to continue going. For example, If you've tossed the coin 5 times of which 3 were heads, if you decided to stop the game there and then you'd received 3/5 = $0.60 ... or you could keep going and hope for a higher value.
What is the fair price of this game?

Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
Какова наиболее выигрышная стратегия?

Здравствуйте, hexamino, Вы писали:

H>Здравствуйте, SEH, Вы писали:

H>Маленькая поправка: heads — это орлы, а решки — это tails.
H>fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

Маленькая поправка. Heads -- это не орел... и не решка. Происхождение этих названий настолько разное, что однозначного перевода просто нет.

У всех монет есть лицевая сторона и обратная (вне зависимости от страны и времени выпуска). Со времен Петра в России было принято на одной стороне рисовать двуглавого орла, а с другой -- либо чье-то лицо (ряха), либо всякие данные о том, кто, когда и зачем эту деньгу напечатал (решетка). Отсюда и пошло "орел" и "решка". Причем, орлом могла быть как лицевая (главная) сторона монеты, если на обратной были данные, так и обратная сторона монеты, если на другой было лицо.

На Западе со средних веков (и, может, даже раньше) было принято рисовать голову правящего монарха, а на обратной -- все, что угодно. Поэтому лицевая сторона монеты тождественно называлась Head(s) (голова), а обратная Tail(s) (хвост).

Если монету с императором на одной стороне и орлом на другой показать кому-то на Западе, то орла они обзовут Tails, т.к. с другой стороны лицо (Heads). Если же монете будет Орел и черти-чего с другой стороны, то Орла обзовут Heads, а всякую статистику с обратной стороны -- Tails.

>>>>> print(foo(0., 0., 10)
SEH>У меня заработало при мелком фиксе выше.

жесть, это я планировал ознакомиться с новым языком, написал первую программу,
и оказалось что 2 реализации (windows и linux) интерпретируют простейший код по разному.
Это даже хуже перла..

> Fair price это, как я понимаю, мат ожидание?

я тоже так понял

D>>действительно, очень похоже, что это выигрышная стратегия, правда чтобы строго доказать нужно повглядываться в неравенства.

А>Не могу понять в какие неравенства. Может, хинт на тему как должно выглядеть строгое доказательство?

выигрыш это доля выпавших решек.
нам нужно доказать, что если доля превысила на 0.5 то матожидание изменения доли если мы продолжим игру будет отрицательно.
Это как бы и означает, что продолжать игру нет смысла.
Вот это надо доказать.


D>>А для вычисления fair price просто рекурсивную функцию написать.
D>>

>>>>> def foo(a, b, n):
>>> skipped
D>>

А>Почему ?

Та функция подсчитывала матожидание выигрыша, при условии что оптимальная стратегия уже доказана.
Сейчас напишу функцию, которая посчитает матожидание выигрыша, не зная оптимальной стратегии заранее.

foo(a, b, n) возвращает матожидание выигрыша, если уже сделано b ходов, из них было a решек, и осталось еще n возможных ходов.
Если n == 0, то она просто возвращает a/b потому что выигрыш уже определен.
Если n > 0, то есть 2 опции -- прекратить игру (тогда мы получим a/b), либо продолжить (тогда матожидание выигрыша равно 0.5*foo(a+1, b+1, n-1) + 0.5*foo(a, b+1, n-1)).
Нужно сравнить эти 2 величины и выбрать ту опцию, которая дает более высокое матожидание. Потому что этот выбор во власти игрока.
Волшебным образом получится, что мы будем всегда выбирать "прекратить игру", если a/b > 0.5

>>> def foo(a, b, n):
...     if (n == 0):
...         return(a/b)
...     cont_opt = 0.5 * foo(a+1, b+1, n-1) + 0.5 * foo(a, b+1, n-1)
...     if (b == 0):
...         return(cont_opt)
...     stop_opt = a/b
...     return max(cont_opt, stop_opt)
... 
>>> print(foo(0., 0., 10))
0.743697296627

Здравствуйте, SEH, Вы писали:

SEH>Какова наиболее выигрышная стратегия?

Остановиться как только текущий выигрыш будет больше 0.5
Если первой выпала решка, то соответственно больше и не кидать

А>Остановиться как только текущий выигрыш будет больше 0.5
А>Если первой выпала решка, то соответственно больше и не кидать

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

А для вычисления fair price просто рекурсивную функцию написать.

Код на Писуне:

>>> def foo(a, b, n):
...    if (b == 0):
...      frac = 0.5
...    else:
...      frac = a/b
...      if (frac > 0.5):
...        return(frac)
...    if (n == 0):
...      return(frac)
...    return(0.5*foo(a, b+1, n-1) + 0.5*foo(a+1, b+1, n-1))
...
>>> print(foo(0, 0, 10))
0.743697296627

Здравствуйте, SEH, Вы писали:

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

В общем так, у меня есть плохая новость и хорошая. Начну с плохой.

Я там где-то доказал, что как только получили хотя бы 0.5, надо брать... Это неверно. Простая иллюстрация, которая прояснит немного суть происходящего. Допустим, что у нас 4 решки при 8 бросках. Это верно, что если бросать еще один раз, то ожидание будет все равно $0.5, или даже если бросать 2 раза. Это даже, как бы, очевидно... Весь фокус в том, что стратегия может при это давать положительную отдачу за счет того, что можно остановиться, если все хорошо, а если плохо, то играть до конца. Действительно, всего четыре возможных продолжения.
РР: 5 из 9, 6 из 10.
РО: 5 из 9, 5 из 10.
ОР: 4 из 9, 5 из 10.
ОО: 4 из 9, 4 из 10.
Мы можем, если все хорошо, т.е. сначала выпала решка, и стало 5 из 9, остановиться. Если выпала сразу решка, то отношение решек к числу бросков подскочило, чтобы потом упасть (в среднем, если бросать дальше). Т.е. если мы не остановимся, то ожидание после этого будет меньше. Если же выпал орел, то мы продолжаем, т.е. в этой подветке при таком развитии событий мат.ожидание не меняется. Таким образом наша остановка в хорошем случае (первая решка) увеличивает мат.ожидание в той подветке, а тот факт, что мы продолжаем в случае первого орла -- его в этой подветке не изменяет. В целом это приводит к тому, что изначальное мат.ожидание увеличивается, т.е. становится больше 0.5. А значит, в случае 4 решек при 8 бросках нам останавливаться не надо. Это очень похоже на опционы. Если все хорошо, мы его реализуем, получаем прибыль. Если плохо, то не реализуем, а живем как есть. Такая своеобразная страховка дает положительное ожидание прибыли, а потому опционы обычно не бесплатные.

Стратегия остановки при хорошем развитии событий дает положительное мат.ожидание результата в случае, когда решек ровно половина. Т.е. в этом случае, очевидно, надо продолжать. В случае, если решек сейчас меньше половины, то, тем более, так как даже если сразу сказать, что бросаем до конца, мат. ожидание результата будет положительным, а уж со стратегией "стоп, если все ОК" тем более. Остается неясность, как быть со случаем, когда сейчас решек больше половины. С одной стороны, если продолжить, то мат.ожидание само по себе падает. С другой стороны, стратегия остановки в благоприятных случаях увеличивает его. Может так оказаться (при большем, чем 10 бросках), что для некоторых текущих значений выигрыша, которые на чуть-чуть больше 1/2, например, 11/20, окажется, что надо продолжать играть, так как положительный результат от стратегии будет больше отрицательного от изменения мат.ожидания выигрыша. Как показать, что это не так, я не знаю. Т.е. доказательства оптимальности нет.

Хорошая новость. Брут-форс подтвердил, что алгоритм "стоп, если БОЛЬШЕ, чем $0.5" (предложенный ранее) является единственным оптимальным. Стоимость: $0.743697. Я написал еще генетический алгоритм, который тоже находит эту стратегию. Генетический код игрока -- его стратегия, которая генерится для новых случайным образом. При скрещивании игрок, который играет лучше, имеет преимущество. Алгоритм можно будет попробовать на большем числе бросков, когда брут-форс загнется, на предмет, может ли быть что-то лучше стратегии "бери, если больше 0.5" при другом числе бросков.

Здравствуйте, 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, продолжаем играть.

Здесь сказывается именно тот эффект, который я предсказал вот тут

Автор: vadimcher
Дата: 25.03.10

. А именно, иногда может оказаться, что текущий выигрыш чуть больше 0.5, но близок к 0.5, и тогда положительный эффект от стратегии при продолжении игры может оказаться выше отрицательного эффекта от уменьшения мат.ожидания!

Если сравнить ситуации, когда после 2n+1 бросков получилось n решек, то с увеличением n происходят две вещи. Во-первых, n/(2n+1) становится меньше, т.е. возникает желание продолжить. С другой стороны, времени до конца бросков остается все меньше. Близко к финишу положительный эффект от стратегии уже не успеет себя проявить.

Поэтому, 2/3 мы берем (слишком большое, чтобы не брать), 4/7 не берем (уже не такое большое, а времени до финиша еще много), а 7/13 уже берем (времени до финиша осталось мало), хотя 7/13 меньше, чем 4/7.

P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.

Здравствуйте, SEH, Вы писали:

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

У меня получилось так:

Математическое ожидание выигрыша при правильной игре = 0.7436972966269841

Стратегия такая. Если уже было сделано k ходов, то остановимся в том случае, если ранее монеты выпадала нужным образом (решкой?) чаще, чем k/2.
Например, выпало 3 раза из 4 ходов — останавливаемся (3 > 4/2). Выпало 3 из 7 — играем дальше (3 <= 7/2).

G>Если заходов сколь угодно много, то играем по следующей стратегии.
G>Каждый ход — новая игра.
G>Если выпала решка — завершаем игру и забираем бакс.
G>Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.

За каждую игру ты должен отбить максимальный баблос.
То есть ты играешь много игр, и в среднем тебе нужно максимизировать отношение отбитый баблос/кол-во игр.
Стратегия "Если выпал орел — завершаем игру с 0" не удовлетворяет этой цели -- ты взял ноль, в то время как у тебя был шанс отбить еще денег.

Здравствуйте, SEH, Вы писали:

Маленькая поправка: heads — это орлы, а решки — это tails.
fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

Здравствуйте, hexamino, Вы писали:

H>fair price — это не выигрышная стратегия, а справедливая цена (за участие в игре).

И в самом деле
Перевод исказил задачу...

Здравствуйте, dilmah, Вы писали:

D>А для вычисления fair price просто рекурсивную функцию написать.
...
>>>> print(foo(0., 0., 10)

У меня заработало при мелком фиксе выше. Fair price это, как я понимаю, мат ожидание?

Здравствуйте, dilmah, Вы писали:


D>действительно, очень похоже, что это выигрышная стратегия, правда чтобы строго доказать нужно повглядываться в неравенства.

Не могу понять в какие неравенства. Может, хинт на тему как должно выглядеть строгое доказательство?

D>А для вычисления fair price просто рекурсивную функцию написать.
D>

>>>> def foo(a, b, n):
>> skipped
D>

Почему ?

Здравствуйте, dilmah, Вы писали:

D>жесть, это я планировал ознакомиться с новым языком, написал первую программу,
D>и оказалось что 2 реализации (windows и linux) интерпретируют простейший код по разному.
D>Это даже хуже перла..

Можно чуть подробнее?
Под какой версией/реализацией/ОС сработал вариант с foo ( 0, 0, 10 ) (целочисленными нулями)?

AF>Под какой версией/реализацией/ОС сработал вариант с foo ( 0, 0, 10 ) (целочисленными нулями)?

Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> print(1/2)
0.5

ну, собственно, на сайте так и написано "the new backwards-incompatible series of Python"..

Здравствуйте, Alexey F, Вы писали:

AF>Здравствуйте, dilmah, Вы писали:

D>>Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on
D>>win32
D>>Type "help", "copyright", "credits" or "license" for more information.
>>>>> print(1/2)
D>>0.5

D>>ну, собственно, на сайте так и написано "the new backwards-incompatible series of Python"..
А, фух, всё в порядке
'/' (используемое в "frac = a/b") в Python с версий 3.* означает деление с плавающей запятой, а '//' — целочисленное

Сам пользуюсь линейкой 2.6.*, поэтому сильно удивился

Здравствуйте, Буравчик, Вы писали:


Б>Математическое ожидание выигрыша при правильной игре = 0.7436972966269841

Я не могу понять как его посчитать правильно?

Здравствуйте, SEH, Вы писали:

SEH>

Consider a game where you can toss a fair coin up to 10 times. The payoff you get is the number of heads obtained divided by the number of tosses you've taken. After any toss you've got the choice of stopping there and then, taking your payoff, or to continue going. For example, If you've tossed the coin 5 times of which 3 were heads, if you decided to stop the game there and then you'd received 3/5 = $0.60 ... or you could keep going and hope for a higher value.
SEH>What is the fair price of this game?

SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

Пусть мы сделали k ходов и сейчас выпало m решек. Рассмотрим любой вариант, который может выпасть в будущем за s ходов. Пусть это РООРР... Ему соответствует другой вариант ОРРОО..., в результате которого выпадет столько решек, сколько орлов при первом варианте. Значит, если один добавит x решек, то другой -- s-x решек. В первом случае будем иметь m+x решек, во втором -- m+s-x решек. Вероятности обоих вариантов одинаковые. В среднем оба варианта дадут m+s/2 решек. Т.е. продолжать имеет смысл, если (m+s/2)/(k+s)>m/k или m/k<1/2. Заметим, что эта граница НЕ зависит от s, т.е. при m/k>=1/2 если мы продолжим, то при любом числе ходов после этого мы в среднем получим меньше, т.е. любая стратегия после этого в среднем даст меньше.

Сколько в среднем получится выиграть? Очень интересный вопрос! Рассмотрим первый ход. Если решка -- берем $1, если орел -- кидаем дальше. Каждой решке припишем +1, а орлу -- -1. Нам надо набрать максимум за 9 ходов в сумме +1. Тогда мы выиграем ровно $0.5. В каком случае это не получится? Для этого нужно, чтобы за 9 ходов сумма полученных +1 и -1 всегда была неположительной. Сколько таких вариантов? Будем считать по количеству плюсиков (решек, выпавших за последующие 9 бросков):
0: все минусы, порядок, очевидно, не важен, 1 вариант, выигрыш 0.
1: один плюсик, должен быть не первым (иначе, при втором решка и получаем 1 решку за два броска), т.е. 8 вариантов, выигрыш 0.1.
2: два плюсика, первый должен быть не первым, если он второй, то второй должен быть не третьим, ну а если первый не первый и не второй, то они где угодно (надеюсь, понятно, что сказал). Варианты: -+-* --*, итого 6 + C(7,2) = 27, получит 0.2.
3: три плюсика, варианты: ---* --+-* --++-* -+--* -+-+-*, итого C(6,3)+C(5,2)+4+C(5,2)+4=48, получит 0.3.
4: четыре плюсика, варианты: если срели первых 5 нет плюсов, то дальше все минусы, годится (1), если среди первых 5 один плюс, то он должен быть не первый, а дальше еще три плюса как угодно (4*4=16), если среди первых 5 два плюса, то для них 5 вариантов, а далее среди 4 оставшихся еще два плюса как угодно, но только не два сразу, т.е. (5*5=25), итого 42, получит 0.4.

В среднем получается: (0.0 * 1 + 0.1 * 8 + 0.2 * 27 + 0.3 * 48 + 0.4 * 42) / 512 + 1 * 1 / 2 + 0.5 * (1 — 1/2 — 126/512) = (37.4 + 256 + 65) / 512 = 358.4 / 512, т.е. средний выигрыш при такой стратегии равен 1792 / 2560 = 7 / 10 = 0.7.

Т.е. при такой стратегии ровно 0.7, если нигде не ошибся в расчетах.

V>Здравствуйте, vadimcher, Вы писали:
V>если (m+s/2)/(k+s)>m/k или m/k<1/2

Не получается так... Или я где-то ошибаюсь?

Здравствуйте, SEH, Вы писали:

V>>Здравствуйте, vadimcher, Вы писали:
V>>если (m+s/2)/(k+s)>m/k или m/k<1/2

SEH>Не получается так... Или я где-то ошибаюсь?

Эти два выражения вроде бы эквивалентны. Другое дело, что я там где-то в вычислениях дальше наплел, т.к. ответ вроде должен быть больше, чем 0.7. Да и на счет стратегии надо бы еще разок подумать...

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, SEH, Вы писали:
[]
SEH>>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>>Какова наиболее выигрышная стратегия?
[]
V>Сколько в среднем получится выиграть? Очень интересный вопрос! Рассмотрим первый ход. Если решка -- берем $1, если орел -- кидаем дальше. Каждой решке припишем +1, а орлу -- -1. Нам надо набрать максимум за 9 ходов в сумме +1. Тогда мы выиграем ровно $0.5. В каком случае это не получится? Для этого нужно, чтобы за 9 ходов сумма полученных +1 и -1 всегда была неположительной. Сколько таких вариантов? Будем считать по количеству плюсиков (решек, выпавших за последующие 9 бросков):
[]
V>В среднем получается: (0.0 * 1 + 0.1 * 8 + 0.2 * 27 + 0.3 * 48 + 0.4 * 42) / 512 + 1 * 1 / 2 + 0.5 * (1 — 1/2 — 126/512) = (37.4 + 256 + 65) / 512 = 358.4 / 512, т.е. средний выигрыш при такой стратегии равен 1792 / 2560 = 7 / 10 = 0.7.

V>Т.е. при такой стратегии ровно 0.7, если нигде не ошибся в расчетах.

Разумеется, ошибся. Вероятность каждой рассмотренной траектории в случае, когда первый орел, 1/1024, а не 1/512. И выигрыш будет больше, чем 0.7, около 0.725. Впрочем, это не самая грустная новость. Мое доказательство того, что это оптимальная стратегия ложное. Все, ушел в себя...

V>Оказывается, если бросать не 10, а 20 раз, то этот алгоритм уже не оптимальный.
V>Выигрыш при 20 бросках при алгоритме "Бери, если больше 0.5" равен 0.763351. А можно получать в среднем 0.763413.
V>Стратегия такая же, за исключением:
V>* При 7, если выпало 4, продолжаем играть.
V>* При 9, если выпало 5, продолжаем играть.
V>* При 11, если выпало 6, продолжаем играть.

V>Здесь сказывается именно тот эффект, который я предсказал вот тут

Автор: vadimcher
Дата: 25.03.10

. А именно, иногда может оказаться, что текущий выигрыш чуть больше 0.5, но близок к 0.5, и тогда положительный эффект от стратегии при продолжении игры может оказаться выше отрицательного эффекта от уменьшения мат.ожидания!

V>Если сравнить ситуации, когда после 2n+1 бросков получилось n решек, то с увеличением n происходят две вещи. Во-первых, n/(2n+1) становится меньше, т.е. возникает желание продолжить. С другой стороны, времени до конца бросков остается все меньше. Близко к финишу положительный эффект от стратегии уже не успеет себя проявить.

V>P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.

функция из http://www.rsdn.ru/forum/etude/3745954.1.aspx

Автор: dilmah
Дата: 23.03.10

находит это решение:

>>> print(foo(0., 0., 20))
0.763412800336

Это брутфорс, но он работает несколько секунд. Плюс еще можно ускорить (если добавить мемоизацию, то экспонента превратится в N^3).

Здравствуйте, dilmah, Вы писали:

[]
D>функция из http://www.rsdn.ru/forum/etude/3745954.1.aspx

Автор: dilmah
Дата: 23.03.10

D>находит это решение:

>>>> print(foo(0., 0., 20))
D>0.763412800336

D>Это брутфорс, но он работает несколько секунд. Плюс еще можно ускорить (если добавить мемоизацию, то экспонента превратится в N^3).

Это сообщение я как-то пропустил. Это не просто брутфорс, а динамическое программирование. Другой вариант. По сути оптимальное решение ищется с хвоста. Пожтому и работает быстро. Значит идея о том, что брать всегда больше 0.5 неправильно, подтвердилась. Супер.

Здравствуйте, vadimcher, Вы писали:

V>Значит идея о том, что брать всегда больше 0.5 неправильно, подтвердилась. Супер.

Похоже, что связано со случайным блужданием и матожиданием максимального отклонения...

Здравствуйте, 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 стоит продолжать.

Здравствуйте, vadimcher, Вы писали:

V>P.S. ИНТЕРЕСНО, что брут форс ковырял это целый час, а написанный для этой задачи генетический алгоритм нашел эту стратегию за секунды (или доли секунд, я даже не заметил)!!! Не знаю, может повезло, но оптимальное решение было найдено после всего 7 смен поколений! Если кому интересно будет, опишу, как устроен.

Пиши, интересно!

You will always get what you always got
  If you always do  what you always did

Здравствуйте, vadimcher, Вы писали:

>>Если кому интересно будет, опишу, как устроен.

Опишите, очень интересно. Хотя в генетических алгоритмах я не силен, вовсе...

Здравствуйте, SEH, Вы писали:

Вопрос сколько раз можно играть в игру?
Если заходов сколь угодно много, то играем по следующей стратегии.
Каждый ход — новая игра.
Если выпала решка — завершаем игру и забираем бакс.
Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.

Если заход ровно 1.
Больше 1$ не выйграем. Так что устанавливаем свой желаемый порог выйгрыша в диапазоне от 0 до 1 и ждем.
Когда-нибудь да выпадет достаточное кол-во решек пордряд и мы выйграем необходимую сумму. Возможно ждать придется долго, но когда-нибудь дождемся.


SEH>Предположим, что играем в игру в которой дается возможность подбросить монету до 10 раз. Сумма денег, которую получим как результат — количество выпаших решек, деленное на количество бросков. После каждого броска дается возможность остановиться и забрать деньги, или продолжить дальше.
SEH>В качестве примера: подбросив монету 5 раз, из которых 3 раза выпала решка мы можем остановиться и получить 3/5=0.60$, а можем продолжить, надеясь на более высокий результат.
SEH>Какова наиболее выигрышная стратегия?

G>Каждый ход — новая игра.
G>Если выпала решка — завершаем игру и забираем бакс.
G>Если выпал орел — завершаем игру с 0. ибо иначе этот 0 будет портить жизнь в дальнейшем.

то есть ты максимизируешь отношение заработанные деньги/кол-во бросков кубика. А нужно максимизировать отношение заработанные деньги/кол-во игр, потому что тебе предъявят счет за кол-во игр, а не за кол-во бросков.

Здравствуйте, dilmah, Вы писали:


D>Стратегия "Если выпал орел — завершаем игру с 0" не удовлетворяет этой цели -- ты взял ноль, в то время как у тебя был шанс отбить еще денег.

Не понятно, почему ты нормируешь деньги на игры, а не на что-то пропорциональное времени, на броски, например

E>Не понятно, почему ты нормируешь деньги на игры, а не на что-то пропорциональное времени, на броски, например

видимо, потому что в описании задачи вопрос звучит "What is the fair price of this game?"
То есть "сколько можно отбить денег на этой игре". Игра -- это серия бросков.