Problemas del mundo real con la mezcla ingenua

Question

Estoy escribiendo una serie de artículos destinados a enseñar conceptos básicos de programación mediante el uso de temas relacionados con el póquer.Actualmente estoy trabajando en el tema de la barajada.

Como Jeff Atwood señala en CodingHorror.com, un método simple de barajar (iterar a través de una matriz e intercambiar cada tarjeta con una tarjeta aleatoria en otra parte de la matriz) crea una distribución desigual de permutaciones.En una aplicación real, simplemente usaría el Mezcla de Knuth Fisher-Yates para una aleatoriedad más uniforme.Pero no quiero empantanar una explicación de los conceptos de programación con un algoritmo mucho menos amigable para los codificadores.

Esto lleva a la pregunta:¿Qué ventaja tendría un sombrero negro si supiera que estás usando una baraja ingenua de una baraja de 52 cartas?Parece que sería infinitamente pequeño.

Answer 1

No es como si estuvieras escribiendo un programa de póquer que se utilizará en un sitio de apuestas en línea real.La capacidad de alguien para hacer trampa en el programa no es gran cosa cuando se le enseña a la gente a programar.

Deje una nota diciendo que este es un modelo pobre del mundo real (con una referencia a él como una posible falla de seguridad) y continúe con la enseñanza.

Answer 2

La mezcla knuth es un cambio insignificante en comparación con la mezcla ingenua:Simplemente intercambie con cualquier carta en la sección restante (sin barajar) del mazo en lugar de en cualquier parte de todo el mazo.Si lo consideras como elegir repetidamente la siguiente carta en orden entre las cartas restantes no elegidas, también es bastante intuitivo.

Personalmente, creo que enseñar a los estudiantes un algoritmo deficiente cuando el correcto no es más complicado (¡y más fácil de visualizar!) es un mal enfoque.

Answer 3

Resulta que la ventaja es bastante significativa. Mira este artículo

Parte del problema es el algoritmo defectuoso, pero otra parte es la suposición de que se pueden obtener números "aleatorios" de una computadora.

Answer 4

Un algoritmo simple y justo para barajar sería asignar un número aleatorio de punto flotante (por ejemplo, entre 0 y 1) a cada carta del mazo y luego ordenar el mazo según los números asignados.

En realidad, este es un ejemplo perfecto para que los estudiantes se den cuenta de que sólo porque algo sea intuitivo (la ingenua mezcla en nuestro caso) no significa que sea correcto.

Answer 5

Subjetivo.

Parece que sería infinitamente pequeño.

Aceptar.

Answer 6

Aparte, hubo un publicación de blog en ITtoolbox sobre barajado que puede resultar de interés a la hora de simular un barajado.

En cuanto a tu pregunta, ¡considera que son 52!Las configuraciones del mazo con las que se podría comenzar pueden desempeñar un papel en el lugar donde aterrizan las cosas, como en el ejemplo de Jeff del mazo de 3 cartas, tenga en cuenta que el 1 en el sobrerrepresentado ocurre en cada ranura una vez.También tenga en cuenta que dice que tendría que tener algunos miles de ejemplos antes de que sea evidente dónde está la ventaja, pero con un mazo no es probable que comience de nuevo exactamente con el mismo mazo inicial, ¿verdad?Tomarías las cartas repartidas, las pondrías en la parte inferior y las barajarías, lo que no es probable que se repita, creo.