Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 125
Спасибо за статью. Занятная математика)
> зануда mode on
К 16 неугаданным картам, выигрыш будет равен 32768 (2^15), потому что с 1 неугаданной картой выигрыш разводчика будет равен 1 (2^0).
> зануда mode off
> зануда mode on
К 16 неугаданным картам, выигрыш будет равен 65536 (2^16).
К 16 неугаданным картам, выигрыш будет равен 32768 (2^15), потому что с 1 неугаданной картой выигрыш разводчика будет равен 1 (2^0).
> зануда mode off
Последнюю карту и так можно вычислить с точностью 100%.
Так что шансы не увеличатся.
Так что шансы не увеличатся.
Но зная последнюю, можно предсказать предпоследнюю со 100% исходом, верно?
точно)) не подумал
Но зная последние две, можно предсказать третью с конца со 100% исходом, верно? :)
Ага, жаль третью раньше второй нельзя назвать ;)
А вообще, напомнило Парадокс неожиданной казни, в котором заключенный так же рассчитывал с конца недели :)
А вообще, напомнило Парадокс неожиданной казни, в котором заключенный так же рассчитывал с конца недели :)
Нет. Для 100% вычисления последней уже нужно знать все выбывшие карты. Для предпоследней вероятность будет 50% (будет видно какие 2 карты отсутствуют).
Неверно. Последнюю можно предсказать со 100% только _зная_ предпоследнюю… соответственно — если осталось только 2 карты — предпоследнюю можно предсказать с 50% ну итд.
Не совсем. Насколько я понял, речь о том, что бы подсмотреть последнюю карту (т.е. знать не только значение, но и то, что она — последняя), тогда появится реальная возможность вычислить пред-последнюю. К тому же, поскольку важен только цвет, то есть вероятность, что пред-последняя и пред-пред-последняя (а при очень большой удаче и пред-пред-пред-последняя, т.е. 3 подряд, ну и т.д.) карты будут одного цвета, что так же даёт возможность это угадать. Это в теории…
Зачем что-то программировать?
Если взять количество побед за x, то выигрыш игрока будет расти как
Получаем уравнение:
(кликабельно)
На графике видно, как будет расти выигрыш игрока (синяя линяя) и выигрыш ведущего (красная линия).
Из графика видно, что игрок имеет преимущество при количестве побед между 0 и 14.
Это хорошо согласуется с вашими данными. Поскольку шансы на победу и проигрыш равны, то количество попыток получается равным удвоенному количеству побед. Таким образом, начиная с 29-й попытки, игрок оказывается в крайне невыгодной для себя ситуации: минимальный проигрыш составит 2384 рубля, а еще через пару попыток проигрыш будет равен уже 17768 рублей.
Если взять количество побед за x, то выигрыш игрока будет расти как
1000*x, а выигрыш ведущего — как 2^x.Получаем уравнение:
1000*x = 2^x.(кликабельно)
На графике видно, как будет расти выигрыш игрока (синяя линяя) и выигрыш ведущего (красная линия).
Из графика видно, что игрок имеет преимущество при количестве побед между 0 и 14.
Это хорошо согласуется с вашими данными. Поскольку шансы на победу и проигрыш равны, то количество попыток получается равным удвоенному количеству побед. Таким образом, начиная с 29-й попытки, игрок оказывается в крайне невыгодной для себя ситуации: минимальный проигрыш составит 2384 рубля, а еще через пару попыток проигрыш будет равен уже 17768 рублей.
Согласен, график очень наглядный. Добавлю его в топик.
График показывает лишь выигрыши, но ведь интересно еще и шанс выигрыша, как увеличить шанс выигрыша, насколько увеличивается шанс, если рассчитывать, какие карты остались в колоде и.т.д. Статья лишь с графиком выглядела бы голой, а за график большое спасибо.
График показывает лишь выигрыши, но ведь интересно еще и шанс выигрыша, как увеличить шанс выигрыша, насколько увеличивается шанс, если рассчитывать, какие карты остались в колоде и.т.д. Статья лишь с графиком выглядела бы голой, а за график большое спасибо.
Шансы на победу и проигрыш не равны. Шанс угадать карту = 1/(кол-во оставшихся карт) на каждом отдельно взятом шаге игры.
+ есть еще вариант с отслеживанием мастей, упомянутый автором.
+ есть еще вариант с отслеживанием мастей, упомянутый автором.
Что-то я не пойму. Правило «Проигрывающий может остановить игру». Выигрыш разводчика достигнет 1000 только к десятой неугаданной карте.
Допустим:
я не угадал 3 карты, отдал 2 + 4 + 8 = 14 рублей.
потом одну угадал, получил 1000 рублей
потом одну не угадал, отдал еще 16 рублей и остановил игру.
Итого у меня 1000 у разводчика — 30 рублей. Получается нужно забрать деньги на первой не угаданной карте после угаданной и не позде 10й не угаданной (случай когда мы подряд не угадали 10 карт, тогда мы уже не отыграемся).
Видимо остановить игру может только тот кто проигрывает в общем счете, а не в текущем ходу, то мне кажется, это нужно отдельно уточнить. Надо будет провести эксперимент на моих друзьях, хотя думаю те, кто в детстве читал Перельмана могут прикинуть в чью пользу будет исход за несколько секунд.
Допустим:
я не угадал 3 карты, отдал 2 + 4 + 8 = 14 рублей.
потом одну угадал, получил 1000 рублей
потом одну не угадал, отдал еще 16 рублей и остановил игру.
Итого у меня 1000 у разводчика — 30 рублей. Получается нужно забрать деньги на первой не угаданной карте после угаданной и не позде 10й не угаданной (случай когда мы подряд не угадали 10 карт, тогда мы уже не отыграемся).
Видимо остановить игру может только тот кто проигрывает в общем счете, а не в текущем ходу, то мне кажется, это нужно отдельно уточнить. Надо будет провести эксперимент на моих друзьях, хотя думаю те, кто в детстве читал Перельмана могут прикинуть в чью пользу будет исход за несколько секунд.
Имеется ввиду, что остановить игру может тот, у кого выигрыш меньше. Таким образом разводчик продолжает игру до тех пор, пока его удвоение выигрыша не покроет выигрыш игрока, а это обязательно случится. А там уже на выбор: Игрок может продолжить играть (что крайне глупо) или прекратить игру, заплатив разводчику разницу в выигрышах.
Да, и по поводу счета разводчика: не прибавляется сумма, а «докидывается», то есть 2, 2+2=4, 4+4=8 и.т.д. Иначе бы его выигрыш рос слишком, слишком быстро.
Добавлю в топик уточнение по поводу общего счета, спасибо.
Да, и по поводу счета разводчика: не прибавляется сумма, а «докидывается», то есть 2, 2+2=4, 4+4=8 и.т.д. Иначе бы его выигрыш рос слишком, слишком быстро.
Добавлю в топик уточнение по поводу общего счета, спасибо.
начал читать, увидел php, закрыл страницу.
Нам тут в хабах «математика» и «алгоритмы», безусловно, важно знать ваше мнение о php. Продолжайте держать нас в курсе.
$cards = array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
это такой алгоритм?
Не болит голова у дятла?
это такой алгоритм?
Не болит голова у дятла?
Я мог заполнить массив циклом, но зачем?
Когда данные статичны, я предпочитаю их записывать, как есть, а не создавать «на лету», пусть даже такое решение более красивое.
Когда данные статичны, я предпочитаю их записывать, как есть, а не создавать «на лету», пусть даже такое решение более красивое.
Да ладно не полнуйся меня уже 7 поклонников языка заминусовало ты должен быть рад ) тем более мне предстоит скоро писать статью (чтобы вернуть карму) там ты отыграешься )
я просто оставлю это здесь.
www.php.net/manual/en/function.array-fill.php
www.php.net/manual/en/function.array-fill.php
Спасибо, не знал об этой функции.
Теперь возникает вопрос: Двухмерные массивы, карты и другую статичную информацию лучше хранить в виде переменной или заполнять функцией? Сейчас попробую сделать тест на время.
Теперь возникает вопрос: Двухмерные массивы, карты и другую статичную информацию лучше хранить в виде переменной или заполнять функцией? Сейчас попробую сделать тест на время.
Простите, не могу ответить на Ваш вопрос. Спросите у тех кто меня минусует, они явно смыслят в php больше моего (это был сарказм, по крайней мере они умеют нажимать кнопку «вниз»). Но я бы предложил объект — колоду, хеш (в вашем случае php — ассоциативный массив) карт как статичный элемент объекта. Хотя можно и экземпляра, тогда можно будет запускать несколько «игр» сразу или одну за одной без реинициализации.
Тестировать на время вряд ли надо, это не критично в нашем случае. Но мне тоже стало интересно, я покажу потом Вам в ЛС исходник на другом языке этой модели.
Тестировать на время вряд ли надо, это не критично в нашем случае. Но мне тоже стало интересно, я покажу потом Вам в ЛС исходник на другом языке этой модели.
Давайте не на долго представим, что автор статьи решил сделать все по фен-шую, создал объекты, применил паттерны проектирования (ну например адаптер, т.к. он решил использовать уже оттестированный код колоды карт, который так удобно кто-то распространял по BSD лицензии, а так же разработку другого автора чтобы перемешивать колоду), дальше наш автор решил сделать красивый вывод и подключил еще библиотеку вывода, чтобы красиво выводить, ну и до кучи всё покрыл юнит-тестами.
Теперь напрашивается вопрос: Зачем он это всё сделал?
Ему всего-лишь на практике нужно было доказать свой тезис, что успешно сделал его скрипт. Большинству пользователей не составит его прочесть и прокрутить у себя в голове (хотя автор мог написать на асме, бейнфаке или вайтспейсе (гипотетически)). Лишние библиотеки, объекты, паттерны проектирования будут лишь отвлекать от сути и отнимать время.
Теперь напрашивается вопрос: Зачем он это всё сделал?
Ему всего-лишь на практике нужно было доказать свой тезис, что успешно сделал его скрипт. Большинству пользователей не составит его прочесть и прокрутить у себя в голове (хотя автор мог написать на асме, бейнфаке или вайтспейсе (гипотетически)). Лишние библиотеки, объекты, паттерны проектирования будут лишь отвлекать от сути и отнимать время.
Вам человек объяснил, почему он это не сделал на лету. Данные статичны, их проще понимать в виде массива.
Давайте так. Во первых лично я плюсанул вам карму. Я всегда плюсую карму тем, кого видно, что будут сливать. Просто верю, что человек может быть ошибся или не в настроении или еще что.
Во вторых поясню почему вас сливают. Ваше замечание совершенно не относится к теме статьи. Это все равно, что вы бы пришли бы в театр и начали обсуждать бы говорить, что спектакль плохой, потому что режиссер вчера напился и устроил драку в баре. Он может и неправильно поступил, и пить то в общем то плохо, но какое это, позвольте, отношение имеет к спектаклю?
Во вторых поясню почему вас сливают. Ваше замечание совершенно не относится к теме статьи. Это все равно, что вы бы пришли бы в театр и начали обсуждать бы говорить, что спектакль плохой, потому что режиссер вчера напился и устроил драку в баре. Он может и неправильно поступил, и пить то в общем то плохо, но какое это, позвольте, отношение имеет к спектаклю?
Ну, Ваш плюс безусловно ценен, но он увы затерялся где-то среди минусов, впрочем это лирика.
Автору статьи я выслал 2 листинга на Ruby той же ситуации какую он на php моделировал.
Однако у меня получается при «осознанном» выборе если 100000 раз перебирать, числа такие:
Мы угадали масть 3003936 раз.
Мы угадали масть 3004260 раз.
Мы угадали масть 3003173 раз.
Мы угадали масть 3002872 раз.
Мы угадали масть 3004776 раз.
Мы угадали масть 3004491 раз.
Мы угадали масть 3004710 раз.
Мы угадали масть 3003391 раз.
Мы угадали масть 3003141 раз.
Мы угадали масть 3003876 раз.
То есть постоянно 30 раз угадывает если делить на число попыток перебора колоды ( 100 тысяч) и никогда-29. А у автора выходило такое число. Возможно я что-то сделал неправильно, или дело в другом.
Автору статьи я выслал 2 листинга на Ruby той же ситуации какую он на php моделировал.
Однако у меня получается при «осознанном» выборе если 100000 раз перебирать, числа такие:
Мы угадали масть 3003936 раз.
Мы угадали масть 3004260 раз.
Мы угадали масть 3003173 раз.
Мы угадали масть 3002872 раз.
Мы угадали масть 3004776 раз.
Мы угадали масть 3004491 раз.
Мы угадали масть 3004710 раз.
Мы угадали масть 3003391 раз.
Мы угадали масть 3003141 раз.
Мы угадали масть 3003876 раз.
То есть постоянно 30 раз угадывает если делить на число попыток перебора колоды ( 100 тысяч) и никогда-29. А у автора выходило такое число. Возможно я что-то сделал неправильно, или дело в другом.
Минусовщикам отдельный респект, я уже послал техсаппорту просьбу об удалении моего аккаунта. Потому что это не честно когда мне могут ставить минусы а я — нет.
Хочу напоследок сказать следующее всем минусовавшим:
Идиомы, какие
Для школьников
И
Такж
Е
Нердов малолетних,
А еще для
Хакеров со стажем 3 оператора php (к автору статьи не относится)
У меня вызывают неприязнь и вообще мне сложно придумать что-то на и краткое то есть
Йети конечно есть слово но оно тут как-то не в тему.
Хочу напоследок сказать следующее всем минусовавшим:
Идиомы, какие
Для школьников
И
Такж
Е
Нердов малолетних,
А еще для
Хакеров со стажем 3 оператора php (к автору статьи не относится)
У меня вызывают неприязнь и вообще мне сложно придумать что-то на и краткое то есть
Йети конечно есть слово но оно тут как-то не в тему.
У меня только один вопрос, зачем вы снова открыли страницу?)
Хабрасуицид прям, с просьбой об удалении аккаунта…
Та я снова живой, понял что был не прав. Лучше не влезать в холивары даже в шутку. Себе дороже.
Похвально. Только вот вспомнилась фраза «уходя — уходи».
По сабжу: Попробовал на практике такую «угадай-ку». В Латвии, к примеру, в такую игру очень сложно играть всерьез, даже начиная с 1 сантима (курс к евро — 1 евро стоит 0,70 лат = 70 сантим). Так вот на практике, даже начиная с 1 сантима и при этом отдавая по 100 лат за угаданную карту, получаются баснословные суммы (последний выйгрыш был над моей же девушкой, с неугаданными 32 картами). В итоге, она мне «задолжала» 21 лям за вечер :)
Автору — я попробовал реализовать разные алгоритмы, лучший средний результат был 31-33 карты из 10000 раз. Последний вариант, на котором я остановился, это:
1) если осталась одна карта, берем ту масть, которой не хватает (тут 100%)
2) далее смотрим каких карт меньше выпало и пытаемся выбрать именну ту масть, но! с вероятностью в (а — меньше выпало, б — больше) а/б
Очень интересно что вы думаете по этому поводу
По сабжу: Попробовал на практике такую «угадай-ку». В Латвии, к примеру, в такую игру очень сложно играть всерьез, даже начиная с 1 сантима (курс к евро — 1 евро стоит 0,70 лат = 70 сантим). Так вот на практике, даже начиная с 1 сантима и при этом отдавая по 100 лат за угаданную карту, получаются баснословные суммы (последний выйгрыш был над моей же девушкой, с неугаданными 32 картами). В итоге, она мне «задолжала» 21 лям за вечер :)
Автору — я попробовал реализовать разные алгоритмы, лучший средний результат был 31-33 карты из 10000 раз. Последний вариант, на котором я остановился, это:
1) если осталась одна карта, берем ту масть, которой не хватает (тут 100%)
2) далее смотрим каких карт меньше выпало и пытаемся выбрать именну ту масть, но! с вероятностью в (а — меньше выпало, б — больше) а/б
Очень интересно что вы думаете по этому поводу
п.с. а и б это количество оставшихся черных и красных карт
Этот вариант рассматривали выше в комментариях. Странно, но он набирал меньше, чем простой алгоритм выбора карты, которых больше в колоде. Думаю, необходимо проверить на каком-нибудь большом тесте в миллионы итераций.
Я тоже думал в сторону алгоритма с шансом выбора из оставшихся карт. Он интересен, что может случайно вытащить 1 последнюю черную из «почти всех» красных карт, но может и зря тратить попытки.
Я тоже думал в сторону алгоритма с шансом выбора из оставшихся карт. Он интересен, что может случайно вытащить 1 последнюю черную из «почти всех» красных карт, но может и зря тратить попытки.
знаете что парадоксально (или не совсем)? то, что если применить алгоритм приведенный мной, то в отличии от програмных тестов, в реальности он гораздо лучше себя показывает. Может вручную карты как-то иначе делаятся? :)
Я тоже сначала проводил все вручную. Из-за случайности, вручную может попасться вариант, когда подойдут аж 40 карт, хоть и маловероятно. Тесты же уравнивают огромное количество таких «аномалий» выводя среднее значение.
Когда я пытался сам пытался угадывать цвет карты, у меня выходило максимум 35 карт, если не ошибаюсь. Больше, чем средний результат, но недостаточный для победы.
Когда я пытался сам пытался угадывать цвет карты, у меня выходило максимум 35 карт, если не ошибаюсь. Больше, чем средний результат, но недостаточный для победы.
В комментариях до вас рассматривали выбор с вероятностями b/(a+b) и a/(a+b). У вас, если я правильно поняла, вероятности (a-b)/a и b/a. У меня получается, что точное значение среднего числа карт при таком выборе 18108755632747595237/687343086666072144 = 26.34602134… Если у вас получается 31-33 карты, хотелось бы видеть код.
31-33 карты были при подборе разных, не подкрепленных математически алгоритмов. Приведенный алгоритм выше, как я уже написал позже, очень интересно использовать в реале, так как цифры отличаются. Возможно мои тесты в реале просто попали в ряд удачных, допускаю такую оплошность. Вечером попробую еще раз.
Возможна модификация правил:
Разводила получает за первую неугаданную карту 1 рубль, за вторую — 2 рубля, за третью — 4 и т.д.
Это дает сумму выигрыша за n неугаданных карт как 2^n — 1, что приводит к точно такому же исходу (один рубль роли не играет).
Интересен вариант если разводила предлагает начать с 1 копейки.
Тогда его выигрыш при 22 неугаданных картах составит 4194303 копеек или 41943 рублей. Выигрыш игрока 30000 рублей, то есть статистически игрок все равно проигрывает.
Можно рассчитать какую сумму в этих условиях должен требовать игрок за угаданную карту, предполагая что будет угадана половина карт (26):
(2^26-1)/26 = 2581110 копеек или 25811,10 рублей. Но даже в этом случае разводила статистически выиграет больше т.к. в случае победы игрока с перевесом в 1 карту он проиграет меньше чем в случае своей победы с перевесом в 1 карту (а эти события — победа или поражение с перевесом в 1 карту — равновероятны).
Игрок за 27 угаданных карт получит:
25811,10*27=696899,70 рублей, разводила (2^25 — 1) / 100 = 335544,31 рублей. Выигрыш игрока 361355,39 рублей.
При 25 угаданных картах игрок получит:
25811,10*25=645277,50 рублей, разводила (2^27 — 1) / 100 = 1342177, 27 рублей. Проигрыш игрока 696899,77 — почти в два раза больше выигрыша. Если рассмотреть случай с плюс-минус 2 карты, то разница будет еще больше.
Вывод: не играйте в азартные игры :)
Разводила получает за первую неугаданную карту 1 рубль, за вторую — 2 рубля, за третью — 4 и т.д.
Это дает сумму выигрыша за n неугаданных карт как 2^n — 1, что приводит к точно такому же исходу (один рубль роли не играет).
Интересен вариант если разводила предлагает начать с 1 копейки.
Тогда его выигрыш при 22 неугаданных картах составит 4194303 копеек или 41943 рублей. Выигрыш игрока 30000 рублей, то есть статистически игрок все равно проигрывает.
Можно рассчитать какую сумму в этих условиях должен требовать игрок за угаданную карту, предполагая что будет угадана половина карт (26):
(2^26-1)/26 = 2581110 копеек или 25811,10 рублей. Но даже в этом случае разводила статистически выиграет больше т.к. в случае победы игрока с перевесом в 1 карту он проиграет меньше чем в случае своей победы с перевесом в 1 карту (а эти события — победа или поражение с перевесом в 1 карту — равновероятны).
Игрок за 27 угаданных карт получит:
25811,10*27=696899,70 рублей, разводила (2^25 — 1) / 100 = 335544,31 рублей. Выигрыш игрока 361355,39 рублей.
При 25 угаданных картах игрок получит:
25811,10*25=645277,50 рублей, разводила (2^27 — 1) / 100 = 1342177, 27 рублей. Проигрыш игрока 696899,77 — почти в два раза больше выигрыша. Если рассмотреть случай с плюс-минус 2 карты, то разница будет еще больше.
Вывод: не играйте в азартные игры :)
Сначала в топике писал о втором способе выиграть разводчика: увеличить шаг арифметической прогрессии. Но число вышло уж слишком большим, поэтому посчитал ненужным писать об этом, но спасибо, что дополнили статью, действительно, в изменениях правил как раз весь интерес!
С математической точки зрения было бы интересно рассчитать такое соотношение ставок, чтобы математическое ожидание выигрыша было равно 0, то есть игра была честной с математической точки зрения. Но навскидку я такую выкладку не сделаю, а считать подробно сейчас времени нет. Может быть немного позже.
Объясните, а в чём тут развод?
Ключевая фраза «И чтобы было честно — остановить игру может лишь тот, кто проигрывает.».
Я это понял так, что я (тот, кто согласился на игру) могу остановить игру на каждом шаге на котором я не угадал карту?
… или речь идёт про абсолютный проигрыш?
Но тогда надо точнее формулировать условия. Иначе может получиться так, что вся компания понимает условие также как и я и разводила делится деньгами под угрозой получить по лицу :)
Ключевая фраза «И чтобы было честно — остановить игру может лишь тот, кто проигрывает.».
Я это понял так, что я (тот, кто согласился на игру) могу остановить игру на каждом шаге на котором я не угадал карту?
… или речь идёт про абсолютный проигрыш?
Но тогда надо точнее формулировать условия. Иначе может получиться так, что вся компания понимает условие также как и я и разводила делится деньгами под угрозой получить по лицу :)
Пока читал в голове вертелась мысль предлагать меньше 1000 рублей за угаданную карту.
В описанных топикстартером условиях можно предлагать и 10000 — на исход это почти не повлияет.
Особенно эффектно должно выглядеть предложение: я тебе 10000 рублей за угаданную карту, а ты мне — 1 копейку, 2 копейки, 4 копейки и т.д. И ведь выгодно!
Точно также как в истории о шахе, мудреце и шахматах.
Особенно эффектно должно выглядеть предложение: я тебе 10000 рублей за угаданную карту, а ты мне — 1 копейку, 2 копейки, 4 копейки и т.д. И ведь выгодно!
Точно также как в истории о шахе, мудреце и шахматах.
>>я тебе 10000 рублей за угаданную карту, а ты мне — 1 копейку, 2 копейки, 4
Я бы с вами сыграл. Скажем 36 карты.
Наши шансы ~17-20 угадать.(точно не считал)
берём 19. Я не угадал 17.
Мой выигрыш 19000руб.
Ваш 2 в 17 копеек =131072копеек.=13 тысяч рублей.
Но если брать 52, то получиться 83 тысячи против 29.
Всё зависит от условий.
Я бы с вами сыграл. Скажем 36 карты.
Наши шансы ~17-20 угадать.(точно не считал)
берём 19. Я не угадал 17.
Мой выигрыш 19000руб.
Ваш 2 в 17 копеек =131072копеек.=13 тысяч рублей.
Но если брать 52, то получиться 83 тысячи против 29.
Всё зависит от условий.
>Естественно, игрок может высказать сомнение по поводу колоды (а вдруг там карты меняются как-нибудь?!) и предложить сыграть с новой колодой из магазина (36 карт)
Игрок, скрывая довольную улыбку, тащит разводилу в магазин, и… видит там только колоды из 52 карт…
Игрок, скрывая довольную улыбку, тащит разводилу в магазин, и… видит там только колоды из 52 карт…
Неужели есть такие, кому это было не очевидно после дочитывания условий разводчика? Элементарно же. Играют на математической неграмотности и «неинтуитивности» роста экспоненты. Хотя любому, закончившему хотя бы 9 классов, вроде уже должно быть понятно, как растёт экспонента.
Несколько замечаний по поводу алгоритма: всё таки интересно получить более менее реальное «среднее» значение угаданных карт. И да — реальное != максимальное, т.е. не надо пытаться максимизировать эту цифру. У вас совершенно необоснованный критерий со счётчиком, который вряд ли адекватно оценивает вероятность выбора.
Мне видится такой алгоритм: изначально есть множество, состоящее из 52 карт. Будем на каждом шаге извлекать некую случайную карту из множества (в множестве только те карты, которые остались). Можно, например, извлекать всегда первую карту, предварительно случайно переставляя карты (нетрудно понять, что от этого ничего не измениться). Так мы получим равномерное распределение выбора цвета карты. Чтобы было проще написать алгоритм, лучше перейти к эквивалентной задаче — будем идти с конца, каждый раз генерируя равномерную случайную перестановку на префиксе. Будем считать, что последний элемент на префиксе (обозначим его номером K) мы выбираем. Посчитаем, сколько карт мы угадали, сравнивая, что стоит K-ой позиции колоды (колоду, естественно, тоже нужно предварительно перемешать). Получился лаконичный и красивый алгоритм:
1. Перемешиваем множество из 52 карт случайным образом — назовём это «колодой».
2. Создаём новое множество, состоящее из 52 карт — назовём это «множество A».
3. Делаем цикл по элементам множества A (массиву, фактически). Пусть мы на I-том шаге. Нам нужно, чтобы на префиксе A[0..I] была случайная перестановка. Это элементарно делается алгоритмом Фишера-Йетса. Скажем, что мы вибираем карту номер I (нетрудно заметить, что она будет случайной). Сравниваем цвет I-ого элемента из A и из «колоды».
И последнее: для таких задач лучше не пользоваться стандартными функциями вроде shuffle. Вполне вероятно, что там хороший алгоритм, а что если нет? Это ведь может сказаться на результате. Я бы не стал доверять shuffle, и реализовал метод Фишера-Йетса, благо пишется он в 3 строчки.
Несколько замечаний по поводу алгоритма: всё таки интересно получить более менее реальное «среднее» значение угаданных карт. И да — реальное != максимальное, т.е. не надо пытаться максимизировать эту цифру. У вас совершенно необоснованный критерий со счётчиком, который вряд ли адекватно оценивает вероятность выбора.
Мне видится такой алгоритм: изначально есть множество, состоящее из 52 карт. Будем на каждом шаге извлекать некую случайную карту из множества (в множестве только те карты, которые остались). Можно, например, извлекать всегда первую карту, предварительно случайно переставляя карты (нетрудно понять, что от этого ничего не измениться). Так мы получим равномерное распределение выбора цвета карты. Чтобы было проще написать алгоритм, лучше перейти к эквивалентной задаче — будем идти с конца, каждый раз генерируя равномерную случайную перестановку на префиксе. Будем считать, что последний элемент на префиксе (обозначим его номером K) мы выбираем. Посчитаем, сколько карт мы угадали, сравнивая, что стоит K-ой позиции колоды (колоду, естественно, тоже нужно предварительно перемешать). Получился лаконичный и красивый алгоритм:
1. Перемешиваем множество из 52 карт случайным образом — назовём это «колодой».
2. Создаём новое множество, состоящее из 52 карт — назовём это «множество A».
3. Делаем цикл по элементам множества A (массиву, фактически). Пусть мы на I-том шаге. Нам нужно, чтобы на префиксе A[0..I] была случайная перестановка. Это элементарно делается алгоритмом Фишера-Йетса. Скажем, что мы вибираем карту номер I (нетрудно заметить, что она будет случайной). Сравниваем цвет I-ого элемента из A и из «колоды».
И последнее: для таких задач лучше не пользоваться стандартными функциями вроде shuffle. Вполне вероятно, что там хороший алгоритм, а что если нет? Это ведь может сказаться на результате. Я бы не стал доверять shuffle, и реализовал метод Фишера-Йетса, благо пишется он в 3 строчки.
Спасибо за конструктивное замечание.
Но перемешивать колоду нет смысла, так как цвет карты выбирается случайно. Независимо от того, как карты расположены в колоде, шанс угадать будет одинаковый для алгоритма. Это мы, люди, можем заметить, что уже 6 карт подряд красные и выбрать красную, рассчитывая, что красные продолжатся, как в оригинале массива до перемешивания.
Более-менее среднее значение угаданных карт выявилось после сотни тысяч «тестов», вышло так, как и можно ожидать по теории вероятностей: 26 карт из 52. Или 50%. Во втором же алгоритме, где карты выбираются по принципу «каких осталось больше в колоде», случайного выбора нет вовсе.
Буду откровенен, я не понимаю, к чему вы привели алгоритм случайного перемешивания «карт» — элементов массива. В конкретно этом случае, это нисколько не важно.
Но перемешивать колоду нет смысла, так как цвет карты выбирается случайно. Независимо от того, как карты расположены в колоде, шанс угадать будет одинаковый для алгоритма. Это мы, люди, можем заметить, что уже 6 карт подряд красные и выбрать красную, рассчитывая, что красные продолжатся, как в оригинале массива до перемешивания.
Более-менее среднее значение угаданных карт выявилось после сотни тысяч «тестов», вышло так, как и можно ожидать по теории вероятностей: 26 карт из 52. Или 50%. Во втором же алгоритме, где карты выбираются по принципу «каких осталось больше в колоде», случайного выбора нет вовсе.
Буду откровенен, я не понимаю, к чему вы привели алгоритм случайного перемешивания «карт» — элементов массива. В конкретно этом случае, это нисколько не важно.
Возможно я не понял ваш алгоритм. Вот смотрите: допустим вы уже 5-й раз подряд выбрали красную карту. В колоде осталось 5 красных и 1 белая. Какова в вашем случае вероятность выбрать белую, и влияет ли как-то на это тот факт, что до этого 5 раз была красная?
Мой алгоритм не искусственный интеллект, я не делал попыток находить закономерности и следовать им. Мой алгоритм этого не учитывает, каюсь. Буду признателен, если поможете мне, написав такой алгоритм.
Кстати, не белая, а черная. Но это не важно.
Кстати, не белая, а черная. Но это не важно.
Я описал алгоритм, который на каждом шаге учитывает, какие карты остались в колоде. Т.е., если остались 2 чёрных и 5 красных, то вероятности выбрать чёрную и красную соответственно: 2/7 и 5/7. А не 50%, как происходит у вас. Я не уверен, но мне кажется, что это более приближённый алгоритм к реальному человеку.
Во втором листинге алгоритм при таких же условиях не церемонясь выберет красную. Если выпадет черная, он все равно выберет красную и так до тех пор, пока не останутся красные. И он их всех угадает.
Я очень хочу посмотреть на ваш алгоритм, думаю, что он может «угадать» больше 30 карт, как угадывает мой алгоритм. Можете написать его?
Я очень хочу посмотреть на ваш алгоритм, думаю, что он может «угадать» больше 30 карт, как угадывает мой алгоритм. Можете написать его?
Я немного переборщил с алгоритмом. У нас ведь всего два вида карт, поэтому там достаточно просто хранить количество оставшихся красных и чёрных. И тогда не нужны никакие перестановки на префиксе и вообще второй массив не нужен.
Ради интереса написал свой и оба ваших алгоритма на C++. Прогнал 10000 раз тесты. Мой вывел 28.112, а ваш (второй) ровно 31 (первый, понятно, примерно 26 всегда выводит). Запускал несколько раз, ваш всегда больше угадывает (примерно 29-34, у меня стабильно 28-29). Ещё у меня вызвало подозрение то, что хотя я и считаю всё в double-ах, ваш алгоритм всегда почему-то даёт целое число. Это очень странный эффект.
UPD: Попробовал после каждого прогона мешать колоду, теперь выводит дробное, стабильно 30.0-30.5.
Вот код: мой вариант, ваш.
Ради интереса написал свой и оба ваших алгоритма на C++. Прогнал 10000 раз тесты. Мой вывел 28.112, а ваш (второй) ровно 31 (первый, понятно, примерно 26 всегда выводит). Запускал несколько раз, ваш всегда больше угадывает (примерно 29-34, у меня стабильно 28-29). Ещё у меня вызвало подозрение то, что хотя я и считаю всё в double-ах, ваш алгоритм всегда почему-то даёт целое число. Это очень странный эффект.
UPD: Попробовал после каждого прогона мешать колоду, теперь выводит дробное, стабильно 30.0-30.5.
Вот код: мой вариант, ваш.
Разгадка — я почти полностью скопировал ваш код на PHP, а он на каждом прогоне одно и то же число вычисляет. В итоге в ответе это самое число и есть. Непонятно, зачем вы $times раз одно и то же считаете.
Я мюслю в том же направлении. Написал чуть выше habrahabr.ru/post/179319/#comment_6240049
я не понимаю, к чему вы привели алгоритм случайного перемешивания «карт»
Этот алгоритм в процессе работы генерирует случайные перестановки на префиксе, что нам и надо. В конце получается случайная перестановка на префиксе A[0..N] (N — размер массива), т.е. на всём массиве.
По поводу вашего алгоритма — если я что-то не так понял, поправьте, пожалуйста.
И ещё:
тут я имел в виду, что мы будем не извлекать карты из множества, а наоборот, добавлять.
И ещё:
будем идти с конца, каждый раз генерируя равномерную случайную перестановку на префиксе
тут я имел в виду, что мы будем не извлекать карты из множества, а наоборот, добавлять.
В моем алгоритме все происходит элементарно, я старался ничего не усложнять.
Выбираем случайный цвет, сравниваем с текущей картой в колоде. Угадали — записываем, иначе идем дальше.
Вот и весь алгоритм. Он показывает именно тот результат, который действительно верный: 50%.
Приведите полный пример вашего алгоритма, потому что сейчас — я вас не понимаю :)
Выбираем случайный цвет, сравниваем с текущей картой в колоде. Угадали — записываем, иначе идем дальше.
Вот и весь алгоритм. Он показывает именно тот результат, который действительно верный: 50%.
Приведите полный пример вашего алгоритма, потому что сейчас — я вас не понимаю :)
Ваш алгоритм верен, но он не соответствует реальному поведению человека в этой ситуации. Я же хотел найти реальную цифру, т.е. если бы играл человек, который осознанно делает выбор. Допустим, если кто-то вытащил 26 подряд чёрных, он знает, что осталось 26 красных, и далее выбирать чёрные уже смысла нет. А в вашем случае он всё равно продолжает выбирать с вероятностью 50% чёрные.
Ваш алгоритм верен, но я не понимаю, что он призван продемонстрировать. Ведь довольно очивидно, что получится примерно 26, т.е. 50%, если выбирать всегда с равной вероятностью.
Ваш алгоритм верен, но я не понимаю, что он призван продемонстрировать. Ведь довольно очивидно, что получится примерно 26, т.е. 50%, если выбирать всегда с равной вероятностью.
Смотрите на второй алгоритм. Он выбирает более-менее обдуманно. Если выпало 26 черных, он будет выбирать 26 раз красных.
При условии «неподглядывания» и действительно случайного расположения карт в колоде (тщательно перемешанные) второй алгоритм является идеальным и даже теоретически не улучшается. Так что не беспокойтесь.
Очень интересно увидеть доказательство этого факта. Этот алгоритм имеет название? После тестов выяснилось, что он угадывает чуть лучше, чем мой алгоритм. Правда я хотел смоделировать реального человека, а не максимизировать количество угаданных карт.
Как поступит реальный человек мы не знаем (с большой вероятностью даст в морду лохотронщику :)
Доказательство простое. В колоде x карт. Из них y — черные и z красные. Вероятность вытянуть черную карту — y/x, вероятность вытянуть красную z/x. Перед каждым выбором нам известные x, y и z. Предложенный автором алгоритм просто сравнивает что больше — y/x или z/x и называет тот цвет, вероятность выпадения которого больше. Перемешивать колоду каждый раз совершенно не обязательно так как и после первого перемешивания колода расположена в случайном порядке.
Доказательство простое. В колоде x карт. Из них y — черные и z красные. Вероятность вытянуть черную карту — y/x, вероятность вытянуть красную z/x. Перед каждым выбором нам известные x, y и z. Предложенный автором алгоритм просто сравнивает что больше — y/x или z/x и называет тот цвет, вероятность выпадения которого больше. Перемешивать колоду каждый раз совершенно не обязательно так как и после первого перемешивания колода расположена в случайном порядке.
Это не доказательство. Вы утверждаете, что не существует алгоритма, который угадает больше. Мне не очевидно, почему в результате достигается оптимальная стратегия. Также не очевидно, почему жадная стратегия работает, вы это никак не обосновали.
Ок, хорошо.
Дано:
1. Колода карт со случайным порядком расположения черных и красных карт
2. На любом шаге нам известно количество черных и красных карт оставшихся в колоде.
3. Оптимальный алгоритм — алгоритм, который с наибольшей вероятностью угадывает цвет карты.
Доказательство:
Для любого такта игры верны следующие утверждения:
1. В колоде x карт.
2. Из них y — черные и z красные.
3. Вероятность вытянуть черную карту — y/x, вероятность вытянуть красную z/x. (надеюсь этот пункт доказывать не надо?)
4. Если y > z то y/x > z/x (вспоминаем 6 класс)
5. Если y < z то y/x < z/x (аналогично)
6. Если y = z то y/x = z/x (мы рассмортрели все варианты соотношений y и z)
7. Таким образом, выбирая тот цвет, которого в колоде осталось больше, алгоритм всегда выбирает наиболее вероятный цвет карты.
8. То есть является оптимальным алгоритмом. Что и следовало доказать
Дано:
1. Колода карт со случайным порядком расположения черных и красных карт
2. На любом шаге нам известно количество черных и красных карт оставшихся в колоде.
3. Оптимальный алгоритм — алгоритм, который с наибольшей вероятностью угадывает цвет карты.
Доказательство:
Для любого такта игры верны следующие утверждения:
1. В колоде x карт.
2. Из них y — черные и z красные.
3. Вероятность вытянуть черную карту — y/x, вероятность вытянуть красную z/x. (надеюсь этот пункт доказывать не надо?)
4. Если y > z то y/x > z/x (вспоминаем 6 класс)
5. Если y < z то y/x < z/x (аналогично)
6. Если y = z то y/x = z/x (мы рассмортрели все варианты соотношений y и z)
7. Таким образом, выбирая тот цвет, которого в колоде осталось больше, алгоритм всегда выбирает наиболее вероятный цвет карты.
8. То есть является оптимальным алгоритмом. Что и следовало доказать
Не обязательно было это расписывать, проблема не в этом :)
Вы же понимаете разницу между этими двумя определениями?
Так вот, чтобы завершить доказательство, вы должны доказать, что эти 2 утверждения эквивалентны. Вы доказали для первого, но ведь нам-то нужен второй, так ведь?
Представьте себе такую задачу: в матрице N*N выбрать N элементов так, чтобы никакие 2 не лежали на одной строке или столбце и их сумма была максимальна. Можно в каждой строке просто выбирать максимальный элемент, это будет простейший жадный алгоритм. Но можно привести множество примеров, когда этот алгоритм находит ответ неверно и можно другим набором выбрать сумму больше. Так что жадная стратегия требует обоснования.
Более подробно про задачу — http://habrahabr.ru/post/63982/, http://ru.wikipedia.org/wiki/Венгерский_алгоритм
Вы же понимаете разницу между этими двумя определениями?
Оптимальный алгоритм — алгоритм, который с наибольшей вероятностью угадывает цвет карты на каждом шаге (шаги рассматриваются независимо).
Оптимальный алгоритм — алгоритм, который угадывает максимальное количество карт на всех шагах в сумме.
Так вот, чтобы завершить доказательство, вы должны доказать, что эти 2 утверждения эквивалентны. Вы доказали для первого, но ведь нам-то нужен второй, так ведь?
Представьте себе такую задачу: в матрице N*N выбрать N элементов так, чтобы никакие 2 не лежали на одной строке или столбце и их сумма была максимальна. Можно в каждой строке просто выбирать максимальный элемент, это будет простейший жадный алгоритм. Но можно привести множество примеров, когда этот алгоритм находит ответ неверно и можно другим набором выбрать сумму больше. Так что жадная стратегия требует обоснования.
Более подробно про задачу — http://habrahabr.ru/post/63982/, http://ru.wikipedia.org/wiki/Венгерский_алгоритм
Если немного приблизиться к терверу, то проблема в том, что вы рассматриваете каждый шаг как независимое событие, а на самом деле они таковыми не являются, ибо выборка без возврата (если с возвратом — тогда можно было бы). Т.е., ваш инвариант
нарушается сразу же после извлечения первой карты из колоды и далее ничего уже утверждать нельзя. А вы пытаетесь повторить то же самое для неслучайной колоды.
1. Колода карт со случайным порядком расположения черных и красных карт
нарушается сразу же после извлечения первой карты из колоды и далее ничего уже утверждать нельзя. А вы пытаетесь повторить то же самое для неслучайной колоды.
Не нарушается.
Колода остается такой же абсолютно случайной колодой из 51 карты в которой не хватает карты цвета Х. Ваше заблуждение из той же серии, что и «какая вероятность того, что монетка выпадет 12 раз орлом кверху?» Ответ — ровно такая же, что и вероятность того, что она будет выпадать сначала орлом, а потом решкой строго попеременно.
Извините что вмешиваюсь.
Колода остается такой же абсолютно случайной колодой из 51 карты в которой не хватает карты цвета Х. Ваше заблуждение из той же серии, что и «какая вероятность того, что монетка выпадет 12 раз орлом кверху?» Ответ — ровно такая же, что и вероятность того, что она будет выпадать сначала орлом, а потом решкой строго попеременно.
Извините что вмешиваюсь.
В вашем примере понятно: любая последовательность равновероятна, а всего возможных последовательностей 2^12. Сумма вероятностей 1, значит вероятность всех последовательностей 1/2^12. «Из той же серии» — не понятно. Почему при удалении первого элемента случайной последовательности мы получаем случайную последовательность? Докажите.
>Почему?
По определению. Хотя бы и потому, что вытаскивая карты, мы никак не влияем на карты, которые остались, а значит они остаются случайными. Мы также можем как угодно разбивать нашу колоду на любые части, и в любой из этих частей будут случайные карты. Даже если мы откроем все красные карты, то у нас останется 26 случайных карт, которые являются черными с вероятностью 1.
По определению. Хотя бы и потому, что вытаскивая карты, мы никак не влияем на карты, которые остались, а значит они остаются случайными. Мы также можем как угодно разбивать нашу колоду на любые части, и в любой из этих частей будут случайные карты. Даже если мы откроем все красные карты, то у нас останется 26 случайных карт, которые являются черными с вероятностью 1.
Нарушается!
В задачах по теории вероятностей одна из основных сложностей — определение равновероятных ситуаций. Например: ru.wikipedia.org/wiki/Парадокс_Монти_Холла
А проблематику фокусов с картами и мастями хорошо описал Гарднер, например:
есть 2 карты красного цвета и 2 карты чёрного, случайно выбираем любые две — какова вероятность что они будут одного цвета?
Вы все ещё настаиваете на равновероятности выпадения красной или чёрной масти после уменьшения количества карт в колоде? ))))
В задачах по теории вероятностей одна из основных сложностей — определение равновероятных ситуаций. Например: ru.wikipedia.org/wiki/Парадокс_Монти_Холла
А проблематику фокусов с картами и мастями хорошо описал Гарднер, например:
есть 2 карты красного цвета и 2 карты чёрного, случайно выбираем любые две — какова вероятность что они будут одного цвета?
Вы все ещё настаиваете на равновероятности выпадения красной или чёрной масти после уменьшения количества карт в колоде? ))))
Не понятно, почему взвешенная выборка проигрывает такому методу. При взвешенной выборке мы делаем выбор в пользу красного с вероятностью z/x, чёрного — y/x. И ещё непонятка: почему, если y=z, мы всегда выбираем один и тот же цвет? Нужно показать, что это не влияет на результат (или влияет?).
А мне картинка с веером сломала мозг
Ибо нельзя сделать веер в правой руке так, что-бы были видны индексы. Следующая мысль — картинка просто отражена зеркально по вертикале, но нет, надписи все сделаны правильно. И тут я понял, что это — какие-то странные Bicicle Rider Back, у которых индексы не там, где должны быть:
.
Сейчас проверил на своих bicycle — действительно, на правой нельзя сделать веер с индексами.
Это специальная колода для левшей, скорее всего. Они такие выпускают.
Это специальная колода для левшей, скорее всего. Они такие выпускают.
Я сам левша. Но мне такие карты кажутся дико неправильными, вызывают чувство дискомфорта. Даже gaff с красными spears не выглядят так дико. Да и делать что-то не основной рукой очень полезно.
www.my-magicshop.com/lefty-bicycle-playing-card-deck.html
Я топик не читал, но вообще, заглавная картинка как -бы намекает нам, что из всех изображений вееров автор выбрал крайне левшу, да и еще с очень редкой колодой.
www.my-magicshop.com/lefty-bicycle-playing-card-deck.html
Я топик не читал, но вообще, заглавная картинка как -бы намекает нам, что из всех изображений вееров автор выбрал крайне левшу, да и еще с очень редкой колодой.
Объяснил бы ещё кто как уйти живым с дегьгами, когда выиграл 65536. Думается мне даже дебил очень быстро поймёт тему и в лучшем случае посмеётся и ничего не отдаст, а может ещё и морду начистят.
В девяностых такая схема была очень частой в барах. И тогда думали совсем о другом: как же отдать 65536? ;)
А вообще: все основывается на психологии людей. Когда споришь с человеком из компании, он пытается предстать честным, хорошим, последовательным человеком, которые, если проиграл, всегда отдаст выигрыш. Неудобно перед компанией, когда договорились о споре просто отказаться выплачивать деньги, это менее благородно, чем достойной проиграть)
А вообще: все основывается на психологии людей. Когда споришь с человеком из компании, он пытается предстать честным, хорошим, последовательным человеком, которые, если проиграл, всегда отдаст выигрыш. Неудобно перед компанией, когда договорились о споре просто отказаться выплачивать деньги, это менее благородно, чем достойной проиграть)
Реально людей раздевали наперстками или в 3 листика/3 карты Монте. Там и азарта больше, и контроль над ситуацией больше, и важно, что у человека всегда есть шанс отыграться, тем самым затягивая его дальше и дальше.
В девяностых такая схема была очень частой в барах. И тогда думали совсем о другом: как же отдать 65536? ;)
Думаю это по тому, что боялись братков, которые работали с разводилой. А когда скромный патсанчик с Хабра разведёт пачку дубоголовых мажоров, лучше ему предварительно потренероваться в беге на скорость, так, на всякий случай. Ну или таки взять в долю ребят по крепче. Ну, мне так кажется.
Мне кажется, даже совсем недалекий человек, слыша такие «сложные»(слишком много мелочей в правилах для игры «за стойкой бара») правила игры должен заподозрить что это разводка и даже не понимая в чем конкретно она заключается отказаться от игры.В наперстки/очко и т.п. гораздо проще развести на игру по моему.
А, вот еще что: я пролистал колоду — встретил всего две длинные очереди 4 карты и 5 карт одного цвета вподряд. А в основном — 2 или 3. Если добавить этот фактор, например после n карт одного цвета растет шанс другого цвета?
На самом деле это совсем неконтролируемо. Совершенно справедливо и обратное: пары цветов встречаются порой чаще, чем пары разных цветов. Думаю, алгоритм максимального угадывания нужно вести не в эту сторону, а в сторону оставшихся карт в колоде.
С нетерпением жду от вас алгоритма, возможно, он будет действительно лучше, а я не прав.
С нетерпением жду от вас алгоритма, возможно, он будет действительно лучше, а я не прав.
Черт, даже на психологическом факультете в рамках очень куцего курса тервера дают понимание, что у событий нет «памяти». То есть первое выбор карты ничем не отличается от всех последющих. Каждый раз когда вы вытягиваете карту из хорошо перемешанной колоды вероятность равна «количество карт данного цвета к количеству карт оставшихся в колоде».
А на психологическом факультете в курсе тервера разве не объясняли разницу между случайными событиями, когда достаем элементы из наборов «с возвратом» и «без возврата»? Вот тут случай «без возврата», т.ч. при каждом новом извлечении карты из колоды будет своя вероятность достать следующую карту красной масти зависящая от мастей ранее извлеченных карт…
Это понятно :) Но вероятность выпадения черной или красной карты зависит только от их текущего соотношения в колоде и вообще никак не зависит от того, что вы вытягивали раньше. Я свой удивленный комментарий написал в ответ на: «пары цветов встречаются порой чаще, чем пары разных цветов.»
Но вероятность выпадения черной или красной карты зависит только от их текущего соотношения в колоде и вообще никак не зависит от того, что вы вытягивали раньше.
А текущее соотношение никак не зависит от того, что достали раньше?)
Соотношение зависит. Почитайте комментарии до моего:
«вот еще что: я пролистал колоду — встретил всего две длинные очереди 4 карты и 5 карт одного цвета вподряд. А в основном — 2 или 3. Если добавить этот фактор, например после n карт одного цвета растет шанс другого цвета?»
и следующий про пары.
То есть люди искренне верят, что если 10 раз подряд выпал орел, то на 11 выпадет решка. И мой комментарий об этом.
«вот еще что: я пролистал колоду — встретил всего две длинные очереди 4 карты и 5 карт одного цвета вподряд. А в основном — 2 или 3. Если добавить этот фактор, например после n карт одного цвета растет шанс другого цвета?»
и следующий про пары.
То есть люди искренне верят, что если 10 раз подряд выпал орел, то на 11 выпадет решка. И мой комментарий об этом.
Действительно, я, наверно, неправильно выразился.
Я имел ввиду, что в частных случаях, в расположении колоды бывают моменты, когда пар одинакового цвета карт больше.
Также бывает и наоборот, когда идут последовательности из 4-5 карт одного цвета, а порой и вообще без единого повторения.
Я знаю про ошибку игрока и понимаю, что предыдущие выборы не влияют на последующие. Но это скорее справедливо для случаев с монеткой. Тут же на основе «вышедших» карт можно увеличить шансы на победу, так как количество красных и черных карт статично.
«На самом деле это совсем неконтролируемо. Совершенно справедливо и обратное: пары цветов встречаются порой чаще, чем пары разных цветов. Думаю, алгоритм максимального угадывания нужно вести не в эту сторону, а в сторону оставшихся карт в колоде.»
Я имел ввиду, что в частных случаях, в расположении колоды бывают моменты, когда пар одинакового цвета карт больше.
Также бывает и наоборот, когда идут последовательности из 4-5 карт одного цвета, а порой и вообще без единого повторения.
Я знаю про ошибку игрока и понимаю, что предыдущие выборы не влияют на последующие. Но это скорее справедливо для случаев с монеткой. Тут же на основе «вышедших» карт можно увеличить шансы на победу, так как количество красных и черных карт статично.
Если игра ведется в несколько партий одной колодой, с перетасовкой её между партиями(вероятно мошенник соберет толпу, и несколько человек с ним будут играть за которыми можно понаблюдать), то можно применить контекстное моделирование. Предположим, что при тасовке колоды более вероятно изменение положения целой последовательности карт внутри колоды, чем одной карты(что вполне справедливо для мошенника со средним уровнем владения колодой и слегка засаленных карт). Также положим что длинна такой последовательности вряд-ли превышает 2-3 карты(считаем что все-таки тасовка достаточно неплохая). тогда можно завести счетчики под все возможные контексты из 3(для определенности) карт и считать для них вероятности выпадения следующей карты красной/черной масти. А потом эту вероятность смешивать с вероятностью полученной от простого контекстного предиктора основанного на уже вышедших из игры картах(просто два счетчика как описано в статье).
Это предполагает, что перед перемешиванием колода была разложена в правильном порядке. Что довольно необычно для колод БУ. Если же говорим про новую колоду, то она не засалена и после минуты перемешивания сведет прогнозтическую ценность контекста к нулю
Нет не предполагает, начальная комбинация карт в колоде может быть произвольной — не суть важно. Тут сложность практического применения заключается больше в недостатке статистики и её неустойчивости(т.к. нужно очень много партий для вычисления хоть сколько-то адекватных вероятностей да и рандом от партии к партии делает свое дело). Но как дополнительный параметр в условиях неопределенности может помочь.
www.pokertyrnir.com/how-shuffle/standart-shuffle.html
После стандартного покерного перемешивания — у вас карты будут в порядке близком к случайному. Вклад закономерности в расположении карт будет стремиться к нулю.
После стандартного покерного перемешивания — у вас карты будут в порядке близком к случайному. Вклад закономерности в расположении карт будет стремиться к нулю.
Есть такой фокус, у меня в сборнике он значится как «Out of this world». (Многие фокусы могут иметь одно название или разные для одного трюка)
Суть в чём: двум людям дают просмотреть быстро пролистываемую колоду и уверяют, что «Вы 100% запомнили, какие там карты в каком порядке!»
Далее сдаются по одной карте и спрашивается на каждой карте у первого: «Если кажется, что карта чёрная — говорите!» и кучкуются в одну кучку — выбранные, во вторую — остальные.
Потом примерно на середине колоды переходят ко второму и процесс аналогичен, но наоборот — говорить зритель должен, если карта по его мнению — красная.
Итог: в одной кучке — сначала идут красные, а потом — чёрные, а во второй — сначала чёрные, а потом красные…
Теория вероятности нервно курит в сторонке! ;)
Суть в чём: двум людям дают просмотреть быстро пролистываемую колоду и уверяют, что «Вы 100% запомнили, какие там карты в каком порядке!»
Далее сдаются по одной карте и спрашивается на каждой карте у первого: «Если кажется, что карта чёрная — говорите!» и кучкуются в одну кучку — выбранные, во вторую — остальные.
Потом примерно на середине колоды переходят ко второму и процесс аналогичен, но наоборот — говорить зритель должен, если карта по его мнению — красная.
Итог: в одной кучке — сначала идут красные, а потом — чёрные, а во второй — сначала чёрные, а потом красные…
Теория вероятности нервно курит в сторонке! ;)
Офигенная статья, мне очень понравилось.
Эта игра выигрывается тупо и примитивно — в условиях нигде не говорится про геометрическую погрессию, а только намекается. При четвёртом неугадывании платишь разводчику опять 8 рублей и он заканчивает игру.
Не понял почему вероятность угадать хотя бы 37 карт равна 1 / 2 ^ 37.
Написал дп, считал, что перемешивающий выбирает сочетание 26 из 52 и угадывающий тоже, должно совпасть хотя бы 37.
В итоге получилось 243131038402150256183986608 / 245935191321399712625557194816 = 0.0009885980005375284.
Написал дп, считал, что перемешивающий выбирает сочетание 26 из 52 и угадывающий тоже, должно совпасть хотя бы 37.
В итоге получилось 243131038402150256183986608 / 245935191321399712625557194816 = 0.0009885980005375284.
По поводу подсмотренной нижней карты, вероятность:
89431042161903922060736652 / 61483797830349928156389298704 = 0.001454546487330985
код
89431042161903922060736652 / 61483797830349928156389298704 = 0.001454546487330985
код
Упс, в последнем коде был баг, но он сработал правильно, потому что по четности нельзя было угадать 37. Исправленный код.
Среднее число угаданных карт легко посчитать точно, без метода Монте-Карло. Если на каждом ходу называть масть наугад равновероятно, то, очевидно, в среднем за каждый ход будет угадано 1/2 карты, в сумме за 52 хода — ровно 26 карт.
Если на каждом ходу называть ту масть, которой осталось больше, то вычисления чуть сложнее. Обозначим f(m,n) = среднее число угаданных карт, если начинать с колоды из m красных и n чёрных карт, равновероятно выбираемой из всех (m+n)! вариантов. Ясно, что f(m,n) = f(n,m), и что f(m,0) = f(0,m) = m. Если теперь m >= n > 0, то мы на первом ходу назовём красную масть. Для первой карты есть m+n вариантов, в m из них мы угадываем цвет и в колоде остаётся m-1 красных и n чёрных карт (любая перестановка которых равновероятна), в n оставшихся мы не угадываем и в колоде остаётся m красных и n-1 чёрных карт (любая перестановка которых опять же равновероятна). В обоих случаях ситуация после хода совершенно идентична ситуации до хода с изменёнными параметрами, поэтому мы можем вычислить среднее число карт, угаданных после первого хода, рекуррентно: f(m,n) = (f(m-1,n)+1)m/(m+n) + f(m,n-1)n/(m+n) при m >= n > 0.
Для 52 карт получается f(26,26) = 3724430600965475/123979633237026 = 30.04066477..., что довольно близко к 30, но не равно в точности.
Для 36 карт получается f(18,18) = 96587303059/4537567650 = 21.28614061…
Если на каждом ходу называть ту масть, которой осталось больше, то вычисления чуть сложнее. Обозначим f(m,n) = среднее число угаданных карт, если начинать с колоды из m красных и n чёрных карт, равновероятно выбираемой из всех (m+n)! вариантов. Ясно, что f(m,n) = f(n,m), и что f(m,0) = f(0,m) = m. Если теперь m >= n > 0, то мы на первом ходу назовём красную масть. Для первой карты есть m+n вариантов, в m из них мы угадываем цвет и в колоде остаётся m-1 красных и n чёрных карт (любая перестановка которых равновероятна), в n оставшихся мы не угадываем и в колоде остаётся m красных и n-1 чёрных карт (любая перестановка которых опять же равновероятна). В обоих случаях ситуация после хода совершенно идентична ситуации до хода с изменёнными параметрами, поэтому мы можем вычислить среднее число карт, угаданных после первого хода, рекуррентно: f(m,n) = (f(m-1,n)+1)m/(m+n) + f(m,n-1)n/(m+n) при m >= n > 0.
Для 52 карт получается f(26,26) = 3724430600965475/123979633237026 = 30.04066477..., что довольно близко к 30, но не равно в точности.
Для 36 карт получается f(18,18) = 96587303059/4537567650 = 21.28614061…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор «лохотрона» на игральных картах