Здравствуйте, 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 смен поколений! Если кому интересно будет, опишу, как устроен.
