Cómo mezclar realmente una baraja de cartas

Cuando necesito barajar una baraja de cartas de poker en Java / Android, utilizo Collections.shuffle(List<?> list) , Por supuesto. He estado haciendo esto y los resultados parecían aceptables. Pero no lo son.

Como se describe en este documento , hay 52! Posibles barajadas únicas de una baraja de poker de 52 cartas. Eso equivale a alrededor de 2 ^ 226.

Sin embargo, Collections.shuffle(List<?> list) utiliza new Random() por defecto que utiliza una semilla de 48 bits y por lo tanto sólo puede crear 2 ^ 48 barajadas únicas – que es sólo 3.49*10^(-52) por ciento de todos Posibles mezclas!

Entonces, ¿cómo puedo barajar las cartas de la manera correcta?

He empezado a usar SecureRandom , pero ¿es suficiente?

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

Sólo puede obtener 2 48 manos diferentes de un acuerdo de partida específico, pero no es necesario que empiece con el mismo arreglo cada vez.

Presumiblemente, después de que la cubierta esté terminada (manos de póquer, blackjack, etc.), estará en un orden indeterminado, y cualquiera de esos reordenamientos será adecuado.

Y, si te preocupa el hecho de que empieces con un arreglo fijo cada vez que inicies tu programa, solo persiste el pedido al salir y lo vuelvas a cargar la próxima vez.

En cualquier caso, 2 48 sigue siendo un gran número de posibilidades (unos 280.000.000.000.000), más que adecuado para un juego de cartas, más aún cuando se llega a la conclusión de que es limitar barajaduras en lugar de arreglos. A menos que seas un estadístico o criptógrafo serio, lo que tienes debe estar bien.

Aunque está utilizando un SecureRandom , todavía tiene un estado limitado. Mientras que la semilla de entrada tiene un rango más pequeño que 52! No puede ser completamente al azar.

De hecho, SHA1PRNG tiene 160 bits sembrados , lo que significa que todavía no es aleatorio. Sigue este enlace , tiene una solución hace años usando una biblioteca de terceros llamada UnCommons Math .

Si desea aleatoriedad real, podría saltarse generadores pseudo aleatorios e ir a algo mejor como números aleatorios generados a partir de ruido atmosférico.

Random.org ofrece una API para integrar números aleatorios generados de esa manera en su propio software.

Robar una respuesta del artículo que enlazas:

 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] 

El generador de números aleatorios debe ser bueno y utilizar una semilla de 64 bits que escoger de manera impredecible, preferiblemente con hardware.

¿Cómo mezclar realmente una baraja?

Hay varias técnicas de barajar .

Cualquiera (Stripping / 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 

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

Y hay más en la parte superior de este, como se detalla en mi enlace anterior.


De todas maneras, hay tantas combinaciones que incluso el algoritmo de barajado perfecto tomaría una máquina explorando 2*10^50 permutaciones únicas por segundo para terminar de explorar cada permutación en el tiempo que el universo haya existido. Las computadoras modernas sólo se pronostican para golpear 1 ExaFLOPs ( 1*10^18 operaciones de punto flotante por segundo) para 2019.

Ningún barajador humano explorará esa gama de posibilidades , y tú, creo (en el nivel más básico), simular una barajadura humana, ¿correcto? ¿Le parecería probable que un croupier pudiera barajar una baraja ordenada de forma incremental en orden decreciente en una barajadura? ¿Para dividir la baraja con rangos pares antes impares, en una barajadura ?

No me parece inaceptable limitarme a una pequeña (aunque extremadamente) subsección de ese espacio de fase ( 2^48 posibles números aleatorios) en cada barajadura, siempre y cuando no continuamente semillas de la misma manera, etc

Hay exactamente 52 factorial (expresado en taquigrafía como 52!) Posibles ordenaciones de las cartas en una baraja de 52 cartas. Esto es aproximadamente 8 × 10 67 pedidos posibles o específicamente: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 .
La magnitud de este número significa que es sumamente improbable que dos cubiertas aleatoriamente seleccionadas, verdaderamente aleatorias, sean iguales, incluso en la historia del Universo. Sin embargo, aunque la secuencia exacta de todas las cartas en una baraja aleatoria es impredecible, puede ser posible hacer algunas predicciones probabilísticas acerca de una baraja que no está suficientemente aleatorizada.
Wikipedia

Además, vale la pena señalar que Bayer & Diaconis en 1992 demostró que sólo se necesitan 7 buenas barajadas para asignar al azar correctamente una cubierta, aquí está la sección sobre ella de wikipedia, que tiene muchos enlaces a los documentos que discuten esto.

  • Algoritmo / teoría para la eliminación de la fluctuación de posición GPS
  • ¿Por qué HttpUrlConnection está lanzando una SSLException mientras está en una conexión de datos móvil?
  • Excepción de host desconocido de Java
  • Acceder a la clase externa desde el enum interno anidado
  • Android: realizar arrastrar y soltar mediante programación
  • Android: Ocultar ActionBar, mantener las pestañas
  • No se puede realizar la operación porque no hay ninguna transacción actual al insertar en la base de datos
  • Aplicación NDK Firma de cheque
  • Dibujar y gancho guestures sin detener app underneith
  • Cómo cambiar la línea de fondo de EditText mediante programación
  • ¿Cuáles son los problemas comunes que experimentan los pequeños equipos de desarrollo de Android?
  • FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.