Как реально перетасовать колоду карт

Когда мне нужно перетасовать колоду карт покера в Java / Android, я использую Collections.shuffle(List<?> list) , конечно. Я когда-либо делал это, и результаты казались приемлемыми. Но это не так.

Как указано в этой статье , существует 52! Возможные уникальные перетасовки колоды для покера с 52 карточками. Это составляет около 2 ^ 226.

Но Collections.shuffle(List<?> list) использует new Random() по умолчанию, который использует 48-битное семя и поэтому может создавать только 2 ^ 48 уникальных тасов – всего 3.49*10^(-52) процентов всех Возможные перетасовки!

Итак, как правильно перетасовать карты?

Я начал использовать SecureRandom , но этого достаточно, наконец?

 List<Card> cards = new ArrayList<Card>(); ... SecureRandom secureRandom; try { secureRandom = SecureRandom.getInstance("SHA1PRNG"); } catch (NoSuchAlgorithmException e) { secureRandom = new SecureRandom(); } secureRandom.nextBytes(new byte[20]); // force SecureRandom to seed itself Collections.shuffle(cards, secureRandom); 

Solutions Collecting From Web of "Как реально перетасовать колоду карт"

Вы можете получить только 2 48 разных рук от конкретной стартовой компоновки, но не требуется, чтобы вы начали с одной и той же компоновки каждый раз.

Предположительно, после того, как колода будет завершена (покерные руки, блэкджек и т. Д.), Она будет в неопределенном порядке, и любая из этих перестроек будет подходящей.

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

Во всяком случае, у 2 48 все еще есть огромное количество возможностей (около 280 000 000 000 000), что более чем подходит для карточной игры, тем более, когда вы осознаете, что это ограничивает перетасовку, а не аранжировки. Если вы не серьезный статистик или криптограф, то у вас должно быть хорошо.

Хотя вы используете SecureRandom , все еще имеет ограниченное состояние. Пока это входное семя имеет меньший диапазон, чем 52! Он не может быть полностью случайным.

Фактически SHA1PRNG составляет 160 бит , что означает, что он все еще не является случайным. Следуйте по этой ссылке , она имеет решение несколько лет назад, используя стороннюю библиотеку под названием UnCommons Math .

Если вам нужна реальная случайность, вы можете просто пропустить псевдослучайные генераторы и перейти к чему-то лучшему, например, случайным числам, генерируемым из атмосферного шума.

Random.org предлагает API для интеграции случайных чисел, сгенерированных таким образом в ваше собственное программное обеспечение.

Кража ответа из статьи, которую вы связываете:

 START WITH FRESH DECK GET RANDOM SEED FOR CT = 1, WHILE CT <= 52, DO X = RANDOM NUMBER BETWEEN CT AND 52 INCLUSIVE SWAP DECK[CT] WITH DECK[X] 

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

Как действительно перетасовать колоду?

Существует несколько методов перетасовки .

Либо (Снятие / Сверху):

 Cut the deck in two Add a small (pseudorandom) amount of one half to the front of the front of the other Add a small (pseudorandom) amount of one half to the front of the back of the other Do this until one hand is empty Repeat 

Или (Riffle):

 Cut the deck in two Set down a small (pseudorandom) portion of one half Set down a small (pseudorandom) portion of the other Do this until both hands are empty, and you have a new deck Repeat 

И есть больше на этом, как описано в моей ссылке выше.


Несмотря на это, существует так много комбинаций, что даже идеальный алгоритм перетасовки заставил машину исследовать 2*10^50 уникальных перестановок в секунду, чтобы завершить изучение каждой перестановки за время существования Вселенной. Ожидается, что к 2019 году только современные компьютеры достигнут 1 ExaFLOP ( 1*10^18 операций с плавающей точкой в ​​секунду).

Ни один человеческий shuffler не изучит этот диапазон возможностей , и вы, я полагаю (на самом базовом уровне), имитируя человеческое перетасовку, правильно? Не могли бы вы обнаружить, что крупье может перемешать поэтапно упорядоченную колоду в порядке убывания в одном перетасовке? Разделить колоду с ровными рангами до нечетного, в одной перетасовке ?

Я не считаю неприемлемым ограничивать себя (хотя и чрезвычайно) небольшим подразделением этого фазового пространства ( 2^48 возможных случайных чисел) в каждом тасовании, если вы не будете постоянно посеять таким же образом и т. Д.

Есть ровно 52 факториала (выраженные в стенограмме 52!) Возможных порядков карточек в колоде на 52 карты. Это приблизительно 8 × 10 67 возможных порядков или, в частности: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 .
Величина этого числа означает, что чрезвычайно маловероятно, чтобы две случайно выбранные, действительно рандомизированные колоды, никогда, даже в истории Вселенной, не были бы одинаковыми. Однако, в то время как точная последовательность всех карт в рандомизированной колоде непредсказуема, может быть возможно сделать некоторые вероятностные прогнозы относительно колоды, которая недостаточно рандомизирована.
~ Википедия

Кроме того, стоит отметить, что Bayer & Diaconis в 1992 году доказал, что для правильной рандомизации колоды требуется 7 хороших тасований, вот раздел на ней из Википедии, в котором есть много ссылок на бумаги, обсуждающие это.