16 нояб. 2008 г.

Зачем изучать математику?

Что может быть проще, чем тасовать колоду кард? С этим справится любой!

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

Коротко перескажу суть, чтобы стало ясно, как там всё сладко изложено:
1. Мы не можем пока вести речи о генераторе случайных чисел - работать приходится с различными псевдослучайными генераторами. Это значит, что если хорошо подумать, то можно предсказывать будущее, определяемое таким генератором. И это можно применить, например, играя в онлайн-казино.
2. Тасовать карты можно разными способами: если делать то, что первое в голову придёт, то вероятности различных раскладов могут быть неодинаковыми. Соответственно, игрок, понимающий это, может пользоваться такой особенностью.
3. Часто генераторы псевдослучайных чисел устроены так, что следующее число, которое они предложат, зависит от состояния 32-ух бит в памяти (т.е. всего 4*109 вариантов). А различных состояний колоды карт может быть 52! - это примерно 8*1067 (разница - 58 порядков!). Это означает, что если колоду карт тасует компьютер, то мы можем заранее знать, какие состояния он точно не сформирует.
4. Упомянутые только что 32 бита часто зависят от текущего времени (таким образом создатели генераторов псевдослучайных чисел старались добавить случайности в результаты). Если мы это знаем, то можем ещё сильнее сузить количество возможных состояний колоды карт. Авторы статьи решили, что двухсот тысяч возможностей им хватит :) Поэтому, увидев первые 5 карт в онлайн-казино, они уже могли мгновенным перебором (благо, компьютеры сейчас быстрые) вычислить всю колоду (то есть узнать, какие карты у соперников). Легко догадаться, что после этого дух игры пропадал, уступая место банальному зарабатыванию денег.

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

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

Кстати, если ребёнку понравится эта статья, то, возможно, стоит предложить ему разбор парадокса Монти Холла - здесь как раз рассматривается очень красивая проблема с интуицией.

14 комментариев:

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

    ОтветитьУдалить
  2. Вообще, крайне интересная заметка. Тут сразу три принципиальные проблемы:
    1. Если посмотреть на число раскладов:
    - Всего карт в колоде 52 - итого 52! комбинаций, это очень много (8e67).
    - Комбинация кодируется 32-битным числом, их всего 4.3e9 << 8e67
    - хуже того! 32-битное число не может быть больше числа миллисекунд в сутках, а их всего 8.64e7 << 4.3e9
    Мы еще не использовали того факта, что random seed - на самом деле число миллисекунд, прошедших в текущих сутках. Мы рассмотрели только само число возможных вариантов. То есть: уже сама по себе неграмотная реализация может сильнейшим образом искажать на первый взгляд совершенно прозрачную процедуру тасования карт.
    2. Вторая проблема в самой идее использования псевдослучайной последовательности для генерации последовательности карт. Так как псевдослучайная последовательность детерминирована своим seed'ом (и имеет со случайной последовательностью лишь то сходство, что оба равномерно распределены), то для получения действительно случайной колоды seed должен принимать не меньше значений, чем всего раскладов. Так что 64-битный seed - тоже не спасёт положение, так как 2^32 = 1.8e19 все еще чудовищно меньше, чем 52!
    3. И наконец, мы сталкиваемся с полным непониманием того, что использование для random seed'а системного времени годится исключительнопри эпизодической (!) интерактивной (!!!) работе - в этом и только в этом случае случайность "добавляется", так как пользователь именно в случайный момент нажимает на кнопку "тасовать колоду". Если же функция randomize вызывается регулярно, то на быстрых процессорах это может вообще приводить к забавным эффектам: например, в течение целой миллисекунды (куча времени!) будет получаться одна и та же колода (начинаем 2 игры одновременно, на одну смотрим... далее понятно).

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

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

    ОтветитьУдалить
  4. "Параметры окружения" благополучно поддаются предсказанию, если скорость их изменения хотя бы на пару порядков меньше, чем характерное время между геренацией случайных чисел. Использование же для генерации "параметров окружения", поддающихся влиянию извне (ну вот хотя бы температуры и траффика) вообще опасно возможными уязвимостями по side channel'ам (простой пример: пингуем сервер с переменной сноростью и "подстраиваем" изменением траффика наш генератор на нужную последовательность). Да, это труднореализуемо, но это то, что приходит в голову в течение первых 10 секунд. А если (как в случае с Кащеем) подумать побольше? Например, задаться вопросом, с какой точностью изменяется температура процессора (едва ли точнее одной десятой градуса)? Получается, что температура дает нам 100-500 возможных значений (!!!!!) - куда годится такой параметр окружения?

    ОтветитьУдалить
  5. >"Параметры окружения" благополучно поддаются предсказанию, если скорость их изменения хотя бы на пару порядков меньше, чем характерное время между геренацией случайных чисел.

    Если брать хотя бы даже эзернет траффит, то оно уже на пару порядков больше (хотя, конечно, надо энтропию оценивать, т.к в траффике-то явно есть некоторые закономерности).

    >Использование же для генерации "параметров окружения", поддающихся влиянию извне (ну вот хотя бы температуры и траффика) вообще опасно возможными уязвимостями по side channel'ам (простой пример: пингуем сервер с переменной сноростью и "подстраиваем" изменением траффика наш генератор на нужную последовательность).

    Ты учти, что кроме тебя этот траффик генерируется из-за кучи других факторов (общение с БД, общение с другими клиентами).

    Плюс учти ещё задержки в сети, которые тоже сложно поддаются предсказанию. То есть тебе мало того, что надо «угадать» чужой траффик, так еще и с перестановками пакетами побаловаться (то ли твой пинг пришел раньше запроса к БД, то ли чуть позже, то ли на миллисекунду позже, то ли на 5).

    >Да, это труднореализуемо, но это то, что приходит в голову в течение первых 10 секунд. А если (как в случае с Кащеем) подумать побольше? Например, задаться вопросом, с какой точностью изменяется температура процессора (едва ли точнее одной десятой градуса)? Получается, что температура дает нам 100-500 возможных значений (!!!!!) - куда годится такой параметр окружения?


    В общем, имея все необходимое для решения этой задачи, смысла зарабатывать в онлайн казино — нет :)

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

    Вот даже RFC есть: http://tools.ietf.org/html/rfc4086

    ОтветитьУдалить
  6. Ещё одна статья о неправильном использовании псевдослучайных чисел - http://www.xakep.ru/post/46797/default.asp

    ОтветитьУдалить
  7. Анонимный06.09.2009, 11:44

    Очевидно же, что человеку, который не понимает, зачем нужна математика, объяснить это невозможно. А тому, кто понимает, не надо объяснять :-)
    За этим и нужна математика :-)

    ОтветитьУдалить
  8. Простейшими генераторами типа перемножение-с-переносом (mwc - multiply-with-carry) мало кто пользуется. Либо увеличивают разрядность, либо пользуются другими генераторами.
    Например, вихрь мерсенна (mersenne twister) имеет период ((2^19937)-1) что примерно 10^6000. И дает равномерно распределенные коррдинаты точек в 600-мерном пространстве. Значения корреляции не помню. Таких чисел за глаза хватит для любых приложений.

    ОтветитьУдалить
  9. Vladimir, спасибо за содержательное дополнение!

    ОтветитьУдалить
  10. Я хотел бы заметить, что ребятам удалось взломать покер только потому что они знали о нём всё, что надо было.

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

    Они знали механизм генерации случайных чисел, которых тоже много. Стоит хотя бы взять их алгоритм и грамотно поменять в нём магические числа и это уже другой генератор. Но они почему-то предпочли стандартный.

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

    ОтветитьУдалить
  11. Zefick, да, всё верно.
    Но сколько ещё людей использует стандартные генераторы? Тысячи их! :)

    ОтветитьУдалить
  12. Кстати, о покере - оказывается эта "проблема" взлома стоит уже давно и покеррумы очень обеспокоены "качеством" случайных чисел. Например здесь http://www.pokerstars.com/ru/poker/room/features/security/ написано, что используются аппаратные генераторы случайных чисел и "данные, получаемые от пользователей, включая данные о передвижениях мыши и времени выполнения различных действий, которые передаются клиентскими программами". Забавно, но ссылка [2] с этой страницы покеррума - ссылка на статью, о которой написал Илья. :) Так что, может с нее (1999 год) все и началось :)

    ОтветитьУдалить
  13. Анонимный31.03.2010, 22:07

    Интересный ответ на вопрос "Зачем изучать математику?" дает Пол Локхард, в своем эссе «Плач математика» о преподавании математики в средней школе http://nbspace.ru/math/ .

    ОтветитьУдалить
  14. Уважаемый аноним, спасибо, что напомнили об этой чудесной статье. Мы как раз говорили о ней через полторы недели после текущей заметки.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний