El algoritmo de barajado de cartas del juego Freecell de Windows
(solitairelaboratory.com)Muchos habrán jugado Freecell de Windows, que organiza las cartas de forma aleatoria y asigna un número a cada disposición. Si eliges el mismo número, las cartas se acomodan exactamente igual.
Hasta antes de Windows 2000, los números iban del 1 al 32,000, pero desde XP se ampliaron hasta 1,000,000.
El algoritmo que genera la disposición de cartas al ingresar un número es público, por lo que también se usa en otros programas de Freecell.
Este algoritmo fue implementado en un código C corto y depende de las funciones rand() y srand() implementadas por el compilador de MS.
8 comentarios
Hermano Tag, juegas muy bien.
El algoritmo original de generación de números aleatorios parece
random, pero en realidad usa una fórmula de recurrencia que produce una secuencia de números pseudoaleatorios, no verdaderamente aleatorios. Cada implementación de la funciónrand()difiere, pero casi todos los algoritmos comparten la característica de que, si la semilla inicial es la misma, la secuencia de números que sigue también es idéntica. Por lo tanto, si el algoritmo de distribución de cartas es determinista, todas las distribuciones de cartas quedan determinadas de forma determinista por la semilla.Aunque se desvía un poco del tema, la cuestión de qué tan pseudoaleatorios pueden generarse números que parezcan arbitrarios también ha sido durante mucho tiempo un tema de investigación. TAOCP Vol.2 también trata este contenido brevemente.
En realidad, no existe el concepto de aleatoriedad en una computadora.
Por eso, normalmente se mide el comportamiento de una persona en milisegundos y se usa eso como semilla aleatoria.
Yo pensaba que los números aleatorios usaban la marca de tiempo actual como
timestamp, pero estaba equivocado jaja. Gracias por compartirlo.Al inicializar, mucha gente suele usar el tiempo como
seed. Porque el tiempo cambia constantemente.Como referencia, en la ayuda de Windows dice: “No está demostrado, pero todos los juegos que se juegan aquí tienen solución”; sin embargo, según los intentos de varias personas, el número 11982 es conocido hasta ahora como imposible de ganar.
Más allá del número 32,000, también hay distribuciones de cartas conocidas como imposibles de ganar, como las de los números 146692, 186216, 455889, 495505, 512118, 517776 y 781948.
¿Cómo habrán descubierto cómo estaba escrito esto y aun así no pudieron resolverlo? ¡Hay mucha gente tenaz!
Qué gente tan aterradora...!