?

Log in

No account? Create an account

Previous Entry | Next Entry

Смок Беллью 21 века

Герой Джека Лондона Смок Беллью сумел победить рулетку в салуне "Олений рог". Старое колесо рассохлось, и движения шарика стали предсказуемыми. Смок выиграл сорок пять тысяч долларов, а потом владельцы игорных домов города заплатили ему тридцать тысяч за "систему" - и очень обрадовались, узнав, что "никакой системы не существует", и за другим столом Смок "не выиграл бы и кислого яблока".

Я вспомнил этот эпизод, когда сын прислал мне ссылку на статью в Wired. Герой этой статьи, Мохан Шривастава, живет в Торонто и занимается геологической статистикой. Как-то он случайно обратил внимание на билеты "мгновенной лотереи" - знаете, где нужно соскрести защитный слой и узнать размер выигрыша. Билеты лотереи в Онтарио выглядели как вариант игры в "крестики-нолики": слева были квадратные решетки с разными числами в ячейках, а справа последовательность чисел, покрытая защитным слоем - "призовые числа". Если три призовых числа окажутся идущими на решетке подряд, как крестики или нолики в игре, билет выигрывает.

Шривастава предположил, что компьютер рисует эти числа не совсем случайным образом. Его исследования показали, что это действительно так: числа, которые встречались слева реже других, имели больше шансов попасть в "призовую последовательность" справа. В статье не говорится прямо, зачем это делается - но мне кажется, что это такая попытка минимизировать выигрыш. В итоге получалось, что если на билете какие-нибудь три числа встречались слева только по одному разу, они с высокой вероятностью оказывались под защитным слоем справа. Поэтому если такие числа шли слева подряд, то билет оказывался выигрышным.

Естественно, первая мысль Шриваставы была: "Теперь я разбогатею!" Но затем он стал считать. Если покупать лотерейные билеты по магазинам и тратить на подсчет вероятности выигрыша каждого билета по 45 секунд, то ежедневный заработок составит около $600. Это не так уж плохо, но как консультант он зарабатывал больше - и работа была поинтереснее. Вместо этого Шривастава сообщил о своем открытии организаторам лотереи - в надежде, что они предложат ему работу. Кстати, достучаться до руководства оказалось непросто: они просто не отвечали на звонки и письма. В конце концов Шривастава послал им пакет с двумя пачками новеньких лотерейных билетов: отдельно кандидаты на выигрыш, отдельно на проигрыш. Он отправил его в 10 утра - и в полдень ему позвонили лотерейщики, а на следующий день все билеты "крестиков-ноликов" были изъяты из продажи: Шривастава верно предсказал 19 из 20 выигрышных билетов. В статье не сказано, сколько заплатили Шриваставе и предложили ли ему постоянную должность консультанта. Впрочем, статья в Wired, надо думать, обеспечит ему хорошую рекламу.

Шривастава заинтересовался другими типами "мгновенных лотерей" и нашел способы выиграть во многих из них. Что не удивительно: эти игры в США и Канаде разрабатывают всего несколько компаний, которые затем продают их организаторам лотерей (обычно это правительства штатов и провинций).

Интересно, что соображения Шриваставы о невыгодности бизнеса работают только для кустарной постановки дела: когда изобретатель ходит по магазинам и вручную отбирает билеты. Простенький сканер с лаптопом позволяет сильно сократить время на проверку каждого билета. Конечно, в магазине могут косо посмотреть на типа с компьютером, отбирающего лотерейные билеты - но есть способы это обойти. Например, некоторые организаторы конференций и совещаний закупают лотерейные билеты оптом на призы для участников, а потом возвращают обратно нераспроданные остатки. Вполне можно представиться таким организатором, закупить пару тысяч билетов, отобрать нужные и вернуть остаток. Ещё проще, если ты сам - владелец или работник магазина.

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

Открытие Шриваставы - подтверждение известного криптоаналитикам факта, что невозможно по-настоящему случайный процесс сделать "ещё случайнее". Вмешательство в такой процесс понижает энтропию - а значит, дает шанс тому, кто играет против него. Компания, разработавшая лотерейный билет, хотела снизить вероятность выигрыша, и для этого сделала билеты неслучайными - и тем самым повысила вероятность выигрыша.

Comments

( 29 comments — Leave a comment )
kouzdra
Feb. 4th, 2011 06:37 pm (UTC)
Мысль о том, что в Спортлото участники играют друг против друга, а потому изучивих предпочтения можно систему отэксплойтить в мое время была общим местом среди матшкольников (правда afaik никто не попробовал реализовать это на практике).

Зато история о том, как лихие восточно-европейские парни по всем правилам наказали английскую рулетку примерно на лимон фунтов imho заслуживает занесения в анналы:
http://news.bbc.co.uk/2/hi/uk_news/4069629.stm

По фактуре - ребята там меряли лазерным датчиком параметры вращения колеса и успевали рассчитать на ноуте вероятные результаты и сделать ставки до того момента, как принятие ставок закрывалось (для азарта там сколько-то секунд ставки принимались после запуска колеса)
misha_b
Feb. 4th, 2011 06:52 pm (UTC)
Была забавная книжка "Bringing Down the House" о том, как ребята из MIT выигрывали в 21. В принципе в 21 можно выиграть, если считать карты, но весьма сложно с практической точки зрения. Любопытн, что для казино выгодно, чтобы люди считали, что они могут выиграть, т.к. это привлекает клиентов. Однако, когда за дело взялись тренированные студенты-"профессионалы", то их быстро выгнали из всех казино.
ulovka22
Feb. 4th, 2011 07:10 pm (UTC)
кажется, даже фильм был такой
insead_hec
Feb. 4th, 2011 10:48 pm (UTC)
На самом деле математик Ed Thorp, который разработал систему счета в 21 потом стоял у истоков первых hedge funds:
Вот здесь он вспоминает как это было:
http://www.npr.org/templates/transcript/transcript.php?storyId=123209339
lexus_lyosha
Feb. 4th, 2011 10:53 pm (UTC)
Ну не так уж быстро - лет 15 развлекались:
http://en.wikipedia.org/wiki/MIT_Blackjack_Team
magpie73
Feb. 4th, 2011 08:01 pm (UTC)
Круто, красиво, но... слишком много надо иметь доп. оборудования - не у всех же есть лазерный сканер. А голова - потенциально - у всех. Поэтому первая история круче;-)
p_govorun
Feb. 4th, 2011 08:32 pm (UTC)
Была статья об этом в "Науке и жизни". Там утверждалось, что среди заполненных билетов нашлись заполненные с помощью штампа -- то есть, кто-то действительно покупал билеты массово (наверняка не без дохода).

(А эксплойт там простой: большинство людей ставят крестики вразброс, а не подряд.)
beth4ever
Feb. 4th, 2011 06:39 pm (UTC)
Интересно, можно ли как-то также обойти корейский рандом в онлайн-играх. Жалко, я не математик.
angerona
Feb. 4th, 2011 06:43 pm (UTC)
представляю себе картину:

Мелкий менеджер в компании-разработчика лотерей: босс, у меня гениальная идея: давай сделаем так, чтоб выигрыш был более редкий! мы даже продадим это нашим клиентам как фичу -- они будут так рады, так рады! Там же быстрее будет набираться на огромную сумму, больше будет ажиотажа.

Большой менеджер: а что, отличная идея. Внедрить, продать и отрапортовать.

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

большой менеджер: давно пора Стива выгнать. А работу эту дай Полу -- он напишет.
lelia_br
Feb. 4th, 2011 07:27 pm (UTC)
LOL! Зачет!
a_konst
Feb. 4th, 2011 08:21 pm (UTC)
Ага, а на самом деле мелкий менеджер прислушался к тому, что говорит Стив, и взял его в долю.
А выгнал, чтоб не заподозрили.
angerona
Feb. 4th, 2011 08:24 pm (UTC)
тоже отлично!
magpie73
Feb. 4th, 2011 07:56 pm (UTC)
;-))) круто! И, действительно, Смока напоминает. Наблюдательность!
chance_gardener
Feb. 4th, 2011 07:58 pm (UTC)
Странно(
Обычно так делают, чтобы. Выигрышная комбинация вообще не встречалась.
scholar_vit
Feb. 4th, 2011 08:17 pm (UTC)
По закону выигрыши должны составлять не менее определенного процента стоимости билетов (конкретная доля зависит от штата или провинции). Поэтому совсем без выигрышей нельзя. А вот если выигрыши встречаются реже, то каждый выигрыш можно сделать больше - без ущерба для прибыли. Как объясняет выше angerona, это привлекает покупателей, и поэтому организаторам лотерей нравится.
chance_gardener
Feb. 4th, 2011 09:13 pm (UTC)
Ваш @angerona хочет присвоить себе половину основ современной теории финансов ?)))
люди всегда думают больше про выигрышь, чем про вероятность ))) Санкт-Петербургский парадокс открыт Бернулли века назад, это читать надо, а не надо объяснять )))

а потом, не понятно как устроена лицензия на лотерею - то ли надо заявить выигрышный фонд, то ли его реально выплатить. думаю там тоже нашли как это все "оптимизировать".
dmpogo
Feb. 5th, 2011 05:42 am (UTC)
Речь шла о лотереях на которую не нужна лицензия - это все государственные лотереи (провинции и штатов).

Но будучи государственными, их правила как раз доступны

ppl
Feb. 4th, 2011 09:27 pm (UTC)
Была вроде бы история про то, как люди организовывали пул и скупали лотерейные билеты - там, где выигрыш падает на номер, как я понимаю. Вроде бы получалась хорошая прибыль (но нужна была довольно четкая организация процесса).
scholar_vit
Feb. 4th, 2011 09:34 pm (UTC)
Ну да - собственно, письмо сына начиналось так: "Помнишь историю про людей, которые печатали лотерейные билеты, когда мат-ожидание было положительное? Мужик смог взломать scratchers". Первую историю мы когда-то подробно обсуждали
0_5
Feb. 5th, 2011 11:52 am (UTC)
Лично знаком с человеком, который на подобном "обмане лотерей" зарабатывал. Правда, не на стираемых билетах, а на чем-то типа спортлото, где выигрывает номер, выпавший на розыгрыше.
faceted_jacinth
Feb. 6th, 2011 05:05 pm (UTC)
> невозможно по-настоящему случайный процесс сделать "ещё случайнее". Вмешательство в такой процесс понижает энтропию - а значит, дает шанс тому, кто играет против него.

Вовсе не обязательно, и автор статьи (повторяя хитроумного геолога) тоже неправ, когда говорит что-то в этом духе.

Тут как я понимаю проблема была вообще не в том, что лотерейщики хотели понизить процент выигрыша зачем-то, а в том, что они хотели получить фиксированный процент -- и сделали это неправильно. Их программа грубо говоря имела две функции: сделать выигрышный билет и сделать проигрышный билет, ну и они вызывали их в нужном соотношении.

Как минимум одна из этих функций производила результат, содержащий отчётливый паттерн. Типа одна генерила случайный билет но с хитрым трюком, позволяющим гарантировать, что в нём нет выигрышных комбинаций, ну, там, как-то разбивая все цифры на группы и расставляя в квадратики цифры из разных групп, например. А вторая брала такой билет и вставляла в него одинаковые цифры, тоже из отдельной группы, чтобы не получить лишних совпадений. Соответственно результат отличался от истинно случайного по статистике встречаемости цифр -- это вмешательство было заметно.

Потому что писал это двоечник.

А если б писал например я, я бы генерил истинно случайные комбинации (может быть даже с использованием хардверного RNG!), смотрел, сколько из них выигрывает/проигрывает, и выкидывал лишние. Никаких паттернов в сами билеты это не вносило бы, и поломать это было бы совершенно невозможно. Хотя энтропию потока это понижало бы, конечно, только радости от этого никому не было. Ну, как если б я сделал рулетку с дополнительным сектором зеро.
gegmopo4
Feb. 9th, 2011 04:28 pm (UTC)
Это не важно, главное, что есть корреляция между наблюдаемым признаком билета и вероятностью выигрыша.

Допустим выпускаются билеты двух видов -- синие и зелёные. Среди зелёных выигрышных намного больше. Если выбрасывать "лишние" выигрышные билеты, то чаще выбрасываться будут именно зелёные. Ну и что? Тот, кто знает этот секрет и умеет отличить зелёный от синего, будет скупать только зелёные билеты (хоть их стало и меньше) и будет выигрывать чаще среднего.
faceted_jacinth
Feb. 9th, 2011 05:29 pm (UTC)
> Допустим выпускаются билеты двух видов -- синие и зелёные. Среди зелёных выигрышных намного больше.

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

Уменьшение процента выигрышных билетов не вносит в никаких изменений в шансы, возьмите сами пример со скажем 100 синих билетов (из которых 10 выигрышных) и 50 зелёных (из которых 30 выигрышных). Ну выкинем 9/10 выигрышных билетов не глядя на цвет. Шансы из 1/10 и 3/5 превратились в 1/100 и 3/50 соответственно. И чё?
gegmopo4
Feb. 9th, 2011 06:12 pm (UTC)
Так дело в том, что остальные не различают синий и зелёный и не догадываются, что есть зависимость с вероятностью выигрыша. А статистик догадался.

И чё? И то, что выбросили 9 синих и 27 зелёных, но вероятность выиграть, если брать зелёный (3/23), всё равно выше средней вероятности (6/96).
faceted_jacinth
Feb. 9th, 2011 08:05 pm (UTC)
Ё. Смотрите, идея в том что изначально мы генерим билеты рандомно. Если генерить билеты рандомно, то довольно просто гарантировать, что никаких внешних признаков, отличающих выигрышные от невыигрышных, нет. Ну, взяли и гарантированно случайно раскидали цифры по полям для крестиков-ноликов, потом так же случайно выбрали секретные цифры. Там не может быть закономерностей по определению.

Всё равно можно какую-нибудь фигню сделать неподумав, конечно. Типа, может оказаться, что выигрышных билетов слишком много или слишком мало, и возникнет соблазн генерить публичную часть случайно, а секретную -- хитроумно подбирать. Так делать нельзя, но и не нужно -- в задаче вполне достаточно свободных параметров (хоть само количество допустимых чисел) чтобы подобрать дающие приблизительно нужный процент. Или допустим может оказаться, что разным публичным частям соответствуют разные количества секретных частей, делающих их выигрышными. Ну, никто не обещал, что дуракам жить на свете должно быть легко.

Тем не менее после того как мы получили генератор билетов, дающий приблизительно нужный процент статистически неопределимых выигрышных (ну, там, с точностью до пары порядков), применение к результатам олгоритма "нагенерить достаточно, выкинуть лишнее до получения точного процента" никаких дополнительных закономерностей не вносит. Более того, он устойчив в том смысле, что даже если там есть какие-то закономерности, он их гарантированно не усиливает.

Вот я и говорю, что утверждение scholar_vit насчёт того, что любые попытки поиграться с результатами случайного потока уменьшают его энтропию, хотя формально и верно, но в данном случае не применимо, так как грамотный олгоритм хоть и уменьшает энтропию потока, но не уменьшает энтропию отдельных билетов так, чтобы можно было статистически отличать выигрышные.
scholar_vit
Feb. 9th, 2011 08:09 pm (UTC)
Ну, взяли и гарантированно случайно раскидали цифры по полям для крестиков-ноликов, потом так же случайно выбрали секретные цифры. Там не может быть закономерностей по определению.

Это утверждение неверно.

Задача: даны числа в "крестиках-ноликах". Найти вероятность выигрыша при произвольном наборе призовых чисел. Зависит ли ответ от чисел, если они могут повторяться?
faceted_jacinth
Feb. 9th, 2011 08:12 pm (UTC)
> Или допустим может оказаться, что разным публичным частям соответствуют разные количества секретных частей, делающих их выигрышными. Ну, никто не обещал, что дуракам жить на свете должно быть легко.

Я предусмотрительный ^^
gegmopo4
Feb. 9th, 2011 08:44 pm (UTC)
Ну вы сами произнесли слова, которые хотел сказать я -- разным публичным частям соответствуют разные количества секретных частей, делающих их выигрышными. Именно так и есть в данном случае. Произошло ли это потому, что изначально так было в схеме (автор был слаб в ТВ) или позже некий Левша решил "улучшить" рандом -- другой вопрос.

Просто выкидывать выигрышные билеты не получится, если нужно гарантировать определённый процент по закону. А вот подстроиться под человеческую психологию так, чтобы количество выигрышных билетов осталось тем же, но выигрывали в массе меньше -- можно. Вот только теперь некто может играть против толпы и подбирать редковыбираемые, но частовыигрываемые билеты.
chloegr
Mar. 17th, 2011 02:55 pm (UTC)
Вот блин засмотрелсяяяяя%))))
( 29 comments — Leave a comment )

Profile

knot
scholar_vit
scholar_vit

Latest Month

August 2018
S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek