Рандомизация коммерческого уровня для игры в покер
Мне нужен совет о том, как решать алгоритмическую проблему (т.е. не программировать как таковую). Ниже приведены мои потребности и то, как я пытался их удовлетворить. Любые комментарии по улучшению будут приветствоваться.
Позвольте мне сначала начать с объяснения моей цели. Я хотел бы сыграть в покер около миллиарда раз. Может быть, я пытаюсь создать следующий PokerStars.net, может, я просто сумасшедший.
Я хотел бы создать программу, которая может производить лучшие рандомизированные колоды карт, чем обычная программа, вызывающая random(). Это должны быть качественные колоды, созданные из случайных чисел высокого качества. Я слышал, что покерные серверы коммерческого уровня используют 64-битные векторы для каждой карты, что обеспечивает случайность для всех миллионов покерных игр, в которые играют ежедневно.
Я бы хотел, чтобы все, что я пишу, было простым. Для этого программе нужно только один вклад для достижения поставленной цели. Я решил, что всякий раз, когда программа начинается, она будет записывать текущее время и использовать его в качестве отправной точки. Я понимаю, что такой подход не будет осуществим для коммерческих сред, но пока он может выдержать несколько миллиардов игр, лучше, чем более простые альтернативы, я буду счастлив.
Я начал писать псевдокод, чтобы решить эту проблему, но столкнулся с острой проблемой. Это понятно для меня, но может и не для вас, поэтому, пожалуйста, дайте мне знать.
Псевдо-код ниже:
Start by noting the system time.
Hash the current time (with MD5) around ten times (I chose the ten arbitrarily).
Take the resulting hash, and use it as the seed to the language-dependent random() function.
Call random() 52 times and store the results.
Take the values produced by random() and hash them.
Any hash function that produces at least 64-bits of output will do for this.
Truncate (if the hash is too big) so the hashes will fit inside a 64-bit double.
Find a way to map the 52 doubles (which should be random now, according to my calculations) into 52 different cards, so we can play some poker.
Моя проблема с последним шагом. Я не могу придумать, как правильно сопоставить каждое 64-битное значение с соответствующей картой, не беспокоясь о том, что два числа совпадают (маловероятно) или не теряют случайности (вероятно).
Моей первой идеей было разбить 0x0000000000000000 - 0xFFFFFFFFFFFFFFFF на четыре четных секции (для представления мастей). Но нет никакой гарантии, что мы найдем ровно тринадцать карт на раздел, что было бы плохо.
Теперь, когда вы знаете, где я застрял, как бы вы преодолели этот вызов?
- Отредактировано -
Чтение байтов из /dev/random будет хорошо работать на самом деле. Но это все еще оставляет меня потерянным на том, как сделать преобразование? (при условии, что я прочитал достаточно байтов для 52 карт).
Мое настоящее желание - взять что-то простое и предсказуемое, например, системное время, и превратить его в рандомизированную колоду карт. Заполнение random () системным временем - ПЛОХОЙ способ сделать это. Отсюда хэширование времени и хэширование значений, которые получаются случайными ().
Черт, если бы я захотел, я мог бы хэшировать байты из /dev/random, только для смеха и хихиканья. Хеширование улучшает случайность вещей, не так ли? Разве не поэтому современные менеджеры паролей хранят пароли, которые были хешированы тысячи раз?
- Правка 2 -
Поэтому я прочитал ваши ответы, и меня смущает вывод, на который намекают многие из вас. Я намекнул на это в своем первом редактировании, но это действительно заставляет меня задуматься. Я просто хотел бы указать на это и двигаться дальше.
Существуют "радужные" таблицы, в которых используется математика в стиле фанк и умная магия, которые, по сути, выступают в качестве таблицы поиска общих хэшей, которые сопоставляются с определенным паролем. Насколько я понимаю, более длинные, более надежные пароли вряд ли будут отображаться в этих радужных таблицах. Но факт остается фактом: несмотря на то, что многие пользовательские пароли являются общими, хешированные пароли остаются безопасными после хеширования тысячи раз.
Так это тот случай, когда многие детерминированные операции увеличили случайность исходного пароля (или кажется?). Я не говорю, что я прав, я просто говорю, что это мое чувство.
Второе, на что я хочу обратить внимание, это то, что я делаю это задом наперед.
Я имею в виду, что вы все предлагаете мне взять отсортированную, предсказуемую, неслучайную колоду карт и использовать на ней перетасовку Фишера-Йейтса. Я уверен, что Фишер-Йейтс - хороший алгоритм, но допустим, что вы не могли использовать его по любой причине.
Не могли бы вы взять случайный поток байтов, скажем, по соседству с 416 байтами (52 карты по 8 байт на карту), а БАМ сгенерировал уже случайную колоду карт? Байты были случайными, поэтому это не должно быть слишком сложно.
Большинство людей начинали с колоды из 52 карт (случайных или нет) и обменивали их несколько раз (выбирая случайный индекс для обмена). Если вы можете сделать это, то вы можете взять 52 случайных числа, пробежать их один раз и создать рандомизированную колоду.
Как я могу описать, алгоритм принимает поток случайных байтов и просматривает каждый 8-байтовый фрагмент. Он отображает каждый кусок на карту.
Ex. 0x123 карты для пикового туза Ex. 0x456 карты для короля бриллиантов Ex. 0x789 карты для 3 клубов.... и так далее.
Пока мы выбрали хорошую модель для картирования, это нормально. Перестановка не требуется. Программа будет сокращена до двух шагов.
Шаг 1: Получить достаточное количество случайных байтов из хорошего источника. Шаг 2: Разделить этот поток байтов на 52 блока, по одному для каждой карты в колоде. Шаг 2а: Пробежать 52 блока, преобразовав их в значения карт в соответствии с нашими карта.
Имеет ли это смысл?
8 ответов
Вы сильно усложняете проблему. Вам нужно два компонента, чтобы решить вашу проблему:
- Алгоритм тасования
- Достаточно качественный генератор случайных чисел для алгоритма тасования.
Первое легко, просто используйте алгоритм случайного преобразования Фишера-Йейтса.
Во-вторых, если вам нужны достаточные степени свободы, чтобы можно было генерировать каждую возможную перестановку (из 52! Возможностей), тогда вам нужно как минимум 226 бит энтропии. Использование системных часов не даст вам больше 32 или 64 битов энтропии (на практике гораздо меньше, поскольку большинство битов предсказуемы), независимо от того, сколько избыточных хэшей вы выполняете. Найдите RNG, который использует 256-битное начальное число, и запустите его 256 случайными битами (проблема с самозагрузкой, но вы можете использовать для этого /dev/random или аппаратное устройство RNG).
Вы не упоминаете, на какой ОС вы работаете, но большинство современных ОС имеют заранее сделанные источники высококачественной энтропии. В Linux это /dev/random а также /dev/urandom, из которого вы можете прочитать столько случайных байтов, сколько захотите.
Написание собственного генератора случайных чисел очень нетривиально, если вы хотите хорошую случайность. Любое доморощенное решение может быть ошибочным и потенциально может быть нарушено, а его результаты предсказаны.
Вы никогда не улучшите свою случайность, если по-прежнему используете псевдослучайный генератор, независимо от того, сколько детерминированных манипуляций вы с ним делаете. На самом деле, вы, вероятно, делаете это значительно хуже.
Я бы использовал коммерческий генератор случайных чисел. Большинство используют аппаратные решения, такие как счетчик Гейгера. Некоторые используют существующий пользовательский ввод в качестве источника энтропии, такого как фоновый шум в микрофоне компьютера или задержка между нажатиями клавиш.
Редактировать:
Вы упомянули, что вы также хотите знать, как сопоставить это с алгоритмом случайного перемешивания. Эта часть на самом деле довольно проста. Одним из простых способов является тасовка Фишера-Йейтса. В основном все, что вам нужно от вашего RNG, - это случайное число, равномерно распределенное между 0 и 51 включительно. То, что вы можете сделать в вычислительном отношении с учетом любого ГСЧ и обычно встроено в хорошую библиотеку. См. Раздел "Потенциальные источники предвзятости" статьи в Википедии.
Отличный вопрос!
Я настоятельно рекомендую вам не использовать random функция, встроенная в любой язык программирования. Это генерирует псевдослучайные числа, которые не криптографически безопасны, и поэтому умный злоумышленник мог бы посмотреть на последовательность чисел, возвращающихся в виде карточек, и перепроектировать начальное число случайных чисел. Исходя из этого, они могли легко начать предсказывать карты, которые выйдут из колоды. Я слышал, что некоторые ранние покерные сайты имели эту уязвимость.
Для вашего приложения вам понадобятся криптографически защищенные случайные числа, чтобы злоумышленник не мог предсказать последовательность карточек, не взломав что-то криптографически безопасное. Для этого вы можете использовать аппаратный источник случайности или криптографически безопасный генератор псевдослучайных чисел. Аппаратные генераторы случайных чисел могут быть дорогими, поэтому криптографически безопасный PRNG может быть хорошим вариантом.
Хорошей новостью является то, что очень легко получить криптографически безопасный PRNG. Если вы берете какой-либо безопасный блочный шифр (скажем, AES или 3DES) и используете случайный ключ, начинайте шифровать числа 0, 1, 2, ... и т. Д., Тогда полученная последовательность будет криптографически безопасной. То есть вы могли бы использовать /dev/random чтобы получить несколько случайных байтов для использования в качестве ключа, затем получить случайные числа путем последовательного шифрования целых чисел с использованием надежного шифра с заданным ключом. Это безопасно, пока вы не вернете примерно √n чисел, где n - размер пространства ключа. Для шифра, такого как AES-256, это 2128 значений, прежде чем вам потребуется сбросить случайный ключ. Если вы "только" хотите играть в миллиарды игр (240), это должно быть более чем хорошо.
Надеюсь это поможет! И удачи в проекте!
Вы должны обязательно прочитать ответ на этот вопрос: понимание "случайности"
Ваш подход применения ряда произвольных преобразований к существующему псевдослучайному числу вряд ли улучшит ваши результаты, и на самом деле рискует сделать менее случайные числа.
Вы можете рассмотреть возможность использования случайных чисел, полученных физически, а не псевдослучайных чисел: http://en.wikipedia.org/wiki/Hardware_random_number_generator
Если вы определенно собираетесь использовать псевдослучайные числа, то вам, скорее всего, лучше всего заполнить устройством случайности вашей операционной системы, которое может включать дополнительную энтропию от таких вещей, как время поиска диска, а также пользовательский ввод-вывод.
Здесь вы можете найти готового оценщика покерных комбинаций. Все отзывы приветствуются на адрес электронной почты, найденный в нем.
С точки зрения фактического превращения случайных чисел в карты (если вы последуете советам других при создании случайных чисел), вы можете сопоставить наименьшее число с тузом алмазов, 2-е наименьшее число с 2 бриллиантом и т. Д.
В основном вы предполагаете, что фактические карты имеют естественный порядок, а затем вы сортируете случайные числа и наносите карту в колоду.
редактировать
Видимо, в Википедии перечислен этот метод как альтернатива алгоритму Фишера-Йейтса(о котором я раньше не слышал - спасибо Дэн Дайер!). Одна вещь в статье википедии, о которой я не думал, это то, что вы должны быть уверены, что вы не будете повторять случайные числа, если используете алгоритм, который я описал.
Чтение байтов из /dev/random будет хорошо работать на самом деле. Но это все еще оставляет меня потерянным на том, как сделать преобразование? (при условии, что я прочитал достаточно байтов для 52 карт).
Преобразование чего? Просто возьмите колоду карт и, используя свой криптографически безопасный PRNG, перемешайте ее. Это будет производить каждую возможную колоду карт с равной вероятностью, и никто не сможет определить, какие карты последуют - это лучшее, что вы могли бы сделать.
Просто убедитесь, что вы правильно реализовали алгоритм тасования:)