Come mischiare un mazzo di carte

Question

Quando ho bisogno di mescolare un mazzo di carte da poker in Java/Android, io uso Collections.shuffle(List<?> list), ovviamente. Ho sempre fatto questo e i risultati sembravano accettabili. Ma loro non lo sono.

Come indicato in this paper, ci sono 52! possibili mescolanze uniche di un mazzo di carte da 52 carte. Ciò equivale a circa 2^226.

Ma Collections.shuffle(List<?> list) utilizza new Random() di default che utilizza un 48-bit seed e può quindi creare solo 2^48 riordini unici - che è solo 3.49*10^(-52) per cento di tutti i possibili riordini!

Quindi, come faccio a mischiare le carte nel modo giusto?

Ho iniziato a utilizzare SecureRandom, ma è sufficiente, finalmente?

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); 

Answer 1

Potrebbe essere possibile ottenere solo 2 mani diverse da un accordo di partenza specifico, ma non è necessario che inizi ogni volta alla stessa disposizione.

Presumibilmente, dopo che il mazzo è finito (mani di poker, blackjack e così via), sarà in un ordine indeterminato, e uno qualsiasi di questi riarrangiamenti sarà adatto.

E, se si è preoccupati del fatto che si parte da un accordo fisso ogni volta che si avvia il programma, basta mantenere l'ordine quando si esce e ricaricarlo la volta successiva.

In ogni caso, 2 è ancora un numero enorme di possibilità (alcune 280,000,000,000,000), più che sufficiente per un gioco di carte, tanto più quando si arriva a una realizzazione che è limitante mescola piuttosto che accordi. A meno che tu non sia un serio statistico o crittografo, quello che hai dovrebbe andare bene.

Answer 2

Anche se si utilizza uno SecureRandom, è ancora presente uno stato limitato. Finché quel seme di input ha un intervallo inferiore a 52! non può essere completamente casuale.

Infatti, SHA1PRNG is 160 bit seeded, il che significa che non è ancora abbastanza casuale. Segui this link, ha una soluzione anni fa utilizzando una libreria di terze parti chiamata UnCommons Math.

Answer 3

Rubare una risposta da questo articolo si collega:

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] 

Il generatore di numeri casuali dovrebbe essere buona e utilizzare un seme a 64 bit che si sceglie in modo imprevedibile, preferibilmente utilizzando hardware.

Answer 4

Se si desidera la casualità reale, è possibile saltare i generatori pseudo casuali e scegliere qualcosa di meglio dei numeri casuali generati dal rumore atmosferico.

random.org offre un API per integrare i numeri casuali generati in questo modo nel proprio software.

Answer 5

Come veramente mischiare un mazzo?

Ci sono diversi shuffling techniques.

O (Spogliarello/Overhand):

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 

Or (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 

E ci sono più in cima a questa, come dettagliato nel mio link qui sopra.

---

Indipendentemente da ciò, ci sono così tante combinazioni che anche l'algoritmo rimescolamento ideale sarebbe prendere una macchina esplorare 2*10^50 permutazioni unici al secondo per finire esplorare ogni permutazione nel momento in cui l'universo esiste. I computer moderni sono previsti solo per colpire 1 ExaFLOPs (1*10^18 operazioni in virgola mobile al secondo) entro il 2019.

No shuffler umana che esplorerà gamma di possibilità sia, e tu sei, credo (a livello di base) simulare un mischiare umano, giusto? Troverebbe probabile che un croupier possa mischiare un mazzo ordinato in ordine crescente in ordine decrescente in una mescolata? Per dividere il mazzo con ranghi pari prima dispari, in uno shuffle?

Non trovo inaccettabile limitarsi a una (seppur estremamente) piccola sottosezione di quello spazio di fase (2^48 possibili numeri casuali) in ogni shuffle, purché non si effettui il seeding continuo allo stesso modo, ecc.

Ci sono esattamente 52 fattoriali (espressi in stenografia come 52!) Possibili ordinamenti delle carte in un mazzo da 52 carte. Questo è approssimativamente 8 × 10 possibili ordini o specificamente: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
L'entità di questo numero significa che è estremamente improbabile che due mazzi scelti casualmente e casualmente selezionati, mai, anche nella storia dell'Universo, siano uguali. Tuttavia, mentre l'esatta sequenza di tutte le carte in un mazzo randomizzato è imprevedibile, potrebbe essere possibile fare delle predizioni probabilistiche su un mazzo che non è sufficientemente randomizzato.
~ Wikipedia

Inoltre, vale la pena notare che la Bayer & Diaconis nel 1992 ha dimostrato che ci vuole solo 7 buoni mescola per randomizzare correttamente un ponte, here è la sezione su di esso da wikipedia che ha un sacco collega a giornali parlano di questo .