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.
- No hay carpeta de menú en el proyecto de estudio de Android
- Importa datos de JSON o XML feed y crea una lista en Android
- Botones de estilo AlertDialog para una actividad
- Android TTS no habla gran cantidad de texto
- Circular revela la animación al sustituir el fragmento
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);
- Cómo obtener el tamaño de un tamaño de aplicación + de datos de la aplicación
- Cómo decirle a ProGuard que mantenga campos privados sin especificar cada campo
- Uso de Android @Override
- Cómo introducir la contraseña automáticamente en Webview
- Android requiere el nivel de cumplimiento del compilador 5.0 o 6.0. Se encontró '1.7' en su lugar. Utilice Herramientas de Android> Fijar propiedades del proyecto
- Detección de estilo de conducción mediante sensores de Smartphone
- Hacer un bucle de audio en Android
- ¿Se eliminan los paquetes si no recibo activamente un DatagramSocket?
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.
- Tiempo de espera para solicitud de servidor hecha usando "Volley" solo en Android no iOS
- Android: Abrir archivo con el selector de intenciones de URI obtenido por Storage Access Framework