Я использовал, Random (java.util.Random)
чтобы перетасовать колоду из 52 карт. Есть 52! (8.0658175e + 67) возможностей. Тем не менее, я обнаружил, что начальное число для java.util.Random
a long
- намного меньше при 2 ^ 64 (1.8446744e + 19).
Отсюда я подозреваю, java.util.Random
действительно ли это случайно ; действительно ли он способен генерировать все 52! возможности?
Если нет, то как я могу надежно генерировать лучшую случайную последовательность, которая может произвести все 52! возможности?
java
random
permutation
random-seed
java.util.random
Серж Ардович
источник
источник
Random
никогда не являются реальными случайными числами. Это PRNG, где P означает «псевдо». Для реальных случайных чисел вам нужен источник случайности (например, random.org).Ответы:
Выбор случайной перестановки требует одновременно большей и меньшей случайности, чем подразумевает ваш вопрос. Позволь мне объяснить.
Плохая новость: нужно больше случайности.
Основным недостатком вашего подхода является то, что он пытается выбирать между ~ 226 вариантами, используя 64 бита энтропии (случайное начальное число). Чтобы честно выбрать между ~ 2 226 возможностями, вам нужно будет найти способ генерировать 226 битов энтропии вместо 64.
Существует несколько способов генерации случайных битов: выделенное оборудование , инструкции процессора , интерфейсы ОС , онлайн-сервисы . В вашем вопросе уже есть неявное предположение, что вы можете каким-то образом сгенерировать 64 бита, поэтому просто делайте то, что вы собирались сделать, только четыре раза, и жертвуйте лишние биты на благотворительность. :)
Хорошая новость: нужно меньше случайности.
Как только у вас есть эти 226 случайных битов, все остальное можно сделать детерминистически, и поэтому свойства
java.util.Random
можно сделать неактуальными . Вот как.Допустим, мы генерируем все 52! перестановки (потерпите меня) и сортируйте их лексикографически.
Чтобы выбрать одну из перестановок, нам нужно только одно случайное целое число между
0
и52!-1
. Это целое число - наши 226 битов энтропии. Мы будем использовать его как индекс в нашем отсортированном списке перестановок. Если случайный индекс распределен равномерно, вы не только гарантируете, что все перестановки могут быть выбраны, они будут выбраны равновероятно (что является более сильной гарантией, чем вопрос).Теперь вам не нужно генерировать все эти перестановки. Вы можете создать его напрямую, учитывая его случайно выбранную позицию в нашем гипотетическом отсортированном списке. Это можно сделать за время O (n 2 ) с использованием кода Лемера [1] (см. Также перестановки нумерации и факториальную систему счисления ). Здесь n - размер вашей колоды, т.е. 52.
Существует реализация C в этом ответе StackOverflow . Там есть несколько целочисленных переменных, которые переполняются при n = 52, но, к счастью, в Java вы можете использовать
java.math.BigInteger
. Остальные вычисления могут быть расшифрованы почти как есть:[1] Не путать с Лерером . :)
источник
Ваш анализ верен: заполнение генератора псевдослучайных чисел любым конкретным начальным числом должно давать ту же последовательность после тасования, ограничивая число перестановок, которые вы можете получить, до 2 64 . Это утверждение легко проверить экспериментально ,
Collection.shuffle
дважды позвонив , передавRandom
объект, инициализированный одним и тем же начальным числом, и заметив, что два случайных шаффла идентичны.Решение этой проблемы состоит в том, чтобы использовать генератор случайных чисел, который учитывает большее начальное число. Java обеспечивает
SecureRandom
класс, который можно инициализироватьbyte[]
массивом практически неограниченного размера. Затем вы можете передать экземплярSecureRandom
toCollections.shuffle
для выполнения задачи:источник
SecureRandom
Реализация будет почти наверняка использовать основной ПСЧ. И от периода PRNG (и в меньшей степени от длины состояния) зависит, сможет ли он выбирать из 52 факторных перестановок. (Обратите внимание, что в документации говорится, чтоSecureRandom
реализация «минимально соответствует» определенным статистическим тестам и генерирует выходные данные, которые «должны быть криптографически стойкими», но не устанавливает явного нижнего предела для длины состояния основного PRNG или его периода.)В общем случае генератор псевдослучайных чисел (PRNG) не может выбирать среди всех перестановок списка из 52 элементов, если его длина состояния меньше 226 бит.
java.util.Random
реализует алгоритм с модулем 2 48 ; таким образом, его длина состояния составляет всего 48 бит, что намного меньше, чем 226 бит, о которых я говорил. Вам нужно будет использовать другой PRNG с большей длиной состояния, в частности, с периодом 52 фактора или более.Смотрите также «Перемешивание» в моей статье о генераторах случайных чисел .
Это соображение не зависит от характера PRNG; это в равной степени относится к криптографическим и некриптографическим PRNG (конечно, некриптографические PRNG неуместны, когда речь идет о защите информации).
Хотя
java.security.SecureRandom
позволяет передавать семена неограниченной длины,SecureRandom
реализация может использовать базовый PRNG (например, «SHA1PRNG» или «DRBG»). И от периода PRNG (и в меньшей степени от длины состояния) зависит, сможет ли он выбирать из 52 факторных перестановок. (Обратите внимание, что я определяю «длину состояния» как «максимальный размер затравки, которую PRNG может использовать для инициализации своего состояния без сокращения или сжатия этого затравки »).источник
Позвольте мне заранее извиниться, потому что это немного сложно понять ...
Прежде всего, вы уже знаете, что
java.util.Random
это не совсем случайно. Он генерирует последовательности совершенно предсказуемым образом из семян. Вы совершенно правы, поскольку, поскольку начальное число имеет длину всего 64 бита, оно может генерировать только 2 ^ 64 различных последовательностей. Если бы вы как-то сгенерировали 64 реальных случайных бита и использовали их для выбора начального числа, вы не могли бы использовать этот начальный случайный выбор между всеми этими 52! возможные последовательности с равной вероятностью.Однако этот факт не имеет никакого значения, если вы на самом деле не собираетесь генерировать более 2 ^ 64 последовательностей, если нет ничего «особенного» или «заметно особенного» в последовательностях 2 ^ 64, которые он может генерировать ,
Допустим, у вас был намного лучший PRNG, который использовал 1000-битные семена. Представьте, что у вас есть два способа его инициализации - один из них будет инициализировать его с использованием всего начального числа, а один - хинизировать начальное значение до 64 битов перед его инициализацией.
Если вы не знаете, какой это был инициализатор, можете ли вы написать какой-либо тест, чтобы различить их? Если вам не повезло (в итоге) инициализировать плохой с одинаковыми 64 битами дважды, тогда ответ - нет. Вы не могли бы различить два инициализатора, не зная некоторых слабых мест в конкретной реализации PRNG.
В качестве альтернативы представьте, что
Random
класс имел массив из 2 ^ 64 последовательностей, которые были выбраны полностью и случайным образом в какое-то время в далеком прошлом, и что начальное число было просто индексом в этом массиве.Так что тот факт, что
Random
использует только 64 бита для своего начального числа, на самом деле не является статистически проблемой, если не существует значительного шанса, что вы будете использовать одно и то же начальное число дважды.Конечно, для криптографических целей 64-разрядного начального числа просто недостаточно, поскольку получение системой, использующей одно и то же начальное число дважды, вычислительно возможно.
РЕДАКТИРОВАТЬ:
Я должен добавить, что, хотя все вышеперечисленное является правильным, фактическая реализация
java.util.Random
не является удивительной. Если вы пишете карточную игру, возможно, используйтеMessageDigest
API для генерации хэша SHA-256"MyGameName"+System.currentTimeMillis()
и используйте эти биты для перетасовки колоды. По приведенному выше аргументу, пока ваши пользователи на самом деле не играют в азартные игры, вам не нужно беспокоиться о том, чтоcurrentTimeMillis
возвращает долго. Если ваши пользователи действительно играют в азартные игры, то используйтеSecureRandom
без начальных затрат.источник
Я собираюсь пойти по другому пути. Вы правы в своих предположениях - ваш PRNG не сможет ударить все 52! возможности.
Вопрос в том, каков масштаб вашей карточной игры?
Если вы делаете простую игру в стиле клондайка? Тогда вам определенно не нужны все 52! возможности. Вместо этого посмотрите на это так: у игрока будет 18 квинтиллионных игр. Даже учитывая «проблему дня рождения», им придется сыграть миллиарды рук, прежде чем они попадут в первую игру-дубликат.
Если вы делаете симуляцию Монте-Карло? Тогда ты, наверное, в порядке. Возможно, вам придется иметь дело с артефактами из-за 'P' в PRNG, но вы, вероятно, не столкнетесь с проблемами просто из-за малого начального пространства (опять же, вы смотрите на квинтиллионы уникальных возможностей). с другой стороны, если вы работаете с большим количеством итераций, тогда, да, ваше низкое начальное пространство может нарушить условия сделки.
Если вы делаете многопользовательскую карточную игру, особенно если на кону есть деньги? Затем вам нужно будет немного погуглить, как сайты онлайн-покера решают ту же проблему, о которой вы спрашиваете. Потому что, хотя проблема низкого начального пространства незаметна для среднего игрока, она пригодна для использования, если она того стоит. (Все покерные сайты прошли фазу, когда их PRNG были «взломаны», позволяя кому-то видеть закрытые карты всех других игроков, просто вынимая семя из открытых карт.) Если вы находитесь в такой ситуации, дона не просто найти лучший PRNG - вам нужно относиться к нему так же серьезно, как к проблеме криптографии.
источник
Краткое решение, которое по сути то же самое, что и dasblinkenlight:
Вам не нужно беспокоиться о внутреннем состоянии. Длинное объяснение почему:
Когда вы создаете
SecureRandom
экземпляр таким образом, он обращается к генератору истинных случайных чисел в ОС. Это либо пул энтропии, к которому обращаются значения, которые содержат случайные биты (например, для наносекундного таймера точность по наносекунде является практически случайной), либо внутренний аппаратный генератор чисел.Этот вход (!), Который все еще может содержать ложные следы, подается в криптографически сильный хеш, который удаляет эти следы. Вот почему эти CSPRNG используются, а не для создания самих номеров! Он
SecureRandom
имеет счетчик, который отслеживает, сколько битов было использовано (getBytes()
иgetLong()
т. Д.) И пополняетSecureRandom
биты энтропией, когда это необходимо .Вкратце: просто забудьте про возражения и используйте в
SecureRandom
качестве генератора случайных чисел.источник
Если вы рассматриваете число как просто массив битов (или байтов), то, возможно, вы могли бы использовать (Безопасные)
Random.nextBytes
решения, предложенные в этом вопросе переполнения стека , и затем отобразить массив вnew BigInteger(byte[])
.источник
Очень простой алгоритм - применить SHA-256 к последовательности целых чисел, увеличивающейся от 0 и выше. (Соль может быть добавлена при желании, чтобы «получить другую последовательность».) Если мы предположим, что вывод SHA-256 «так же хорош», как равномерно распределенные целые числа от 0 до 2 256 - 1, то у нас достаточно энтропии для задача.
Чтобы получить перестановку из вывода SHA256 (когда она выражается как целое число), нужно просто уменьшить ее по модулю 52, 51, 50 ... как в этом псевдокоде:
источник