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

Когда мне нужно перетасовать колоду карт покера в 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);

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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-битное семя, которое вы выбираете непредсказуемо, предпочтительно используя аппаратное обеспечение.

Ответ 5

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

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

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

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 ⁶⁷ возможных порядков или, в частности: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
Величина этого числа означает, что чрезвычайно маловероятно, чтобы две случайно выбранные, действительно рандомизированные колоды никогда, даже в истории Вселенной, не были бы одинаковыми. Однако, хотя точная последовательность всех карты в рандомизированной колоде непредсказуемы, может быть возможно сделать некоторые вероятностные прогнозы относительно колоды, которая недостаточно рандомизирована.
~ Wikipedia

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