Generación de números aleatorios en Z80 (u otro de 8 bits)

Foro dedicado a la programación en todo tipo de sistemas clásicos.
Avatar de Usuario
Bubu
Atari 1040 STf
Atari 1040 STf
Mensajes: 886
Registrado: 04 Abr 2018, 23:10
Sistema Favorito: Spectrum 16Kb/48Kb
primer_sistema: Spectrum 16Kb/48Kb
consola_favorita: Atari 2600
Primera consola: Nintendo GameBoy
Gracias dadas: 20 veces
Gracias recibidas: 60 veces

Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Bubu » 07 Nov 2018, 02:21

¡Jarl, torpedos! Estoy ahora interesado en generar un número pseudo-aleatorio (en adelante, número aleatorio) en el Z80, con ciertas carasterísticas:

- De 0 a 255, uséase, que ocupe 1 byte
- Existe un byte en la RAM, llamado (SEED), que contiene un número aleatorio. Este número es realmente el número de microsegundos truncados a 1 byte que el usuario ha tardado en pulsar una tecla.
- No puedo acceder a ninguna otra posición de memoria, ni a ROM ni a RAM, sólo a (SEED)

He visto un hilo por ahí que trataba de generar un número del 0 al 100, pero la solución de fondo no la hi entendido bien.

Yo no soy matemático, y por tanto no entiendo de teorías del "randomizismo", jiji, pero sí intuyo que cualquier operación matemática que realice partiendo de (SEED), me dará otro byte, y el poblema está en que si ese byte vuelve a ser el mismo que (SEED), se bloquea la generación de números aleatorios.
Otro poblema, aunque menor, es que se (SEED)=58 p.ej., y F(58)=123, y F(123)=42, si ahora F(42)=58, volvemos a iniciar la semilla y por tanto el algoritmo F sólo me generaría 3 números aleatorios, y siempre esos 3: 58, 123 y 42.

Si intentamos arreglar esto haciendo que la semilla cambie tras generar el número aleatorio, vemos que aparentemente se solucionan los bloqueos y ciclos cortos:
(SEED)=58, F(58)=123 y (SEED)=17 p.ej., F(17)=66 y (SEED)=90, F(90)=58 y (SEED)=178

Pero tampoco, ya que basta con que el algoritmo produzca un (SEED)=58, para que de nuevo esta "aleatoriedad" sea cíclica.

¿Cómo resuelven los pogramadores este jaleo?
Si algo funciona... ¡¡NO LO TOQUES!! ¡¡NI DE COÑA!!

Avatar de Usuario
explorer
MSX Turbo R
MSX Turbo R
Mensajes: 398
Registrado: 11 May 2014, 17:10
Sistema Favorito: Atari ST
primer_sistema: Atari 800XL/600XL
consola_favorita: Atari 2600
Primera consola: Atari 2600
Ubicación: Valladolid, España
Gracias dadas: 2 veces
Gracias recibidas: 138 veces
Contactar:

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor explorer » 07 Nov 2018, 05:57

La forma más sencilla sería leer el registro de refresco (el registro I o el registro R). Pero tiene el problema de que si lo haces en intervalos regulares, puedes obtener valores "parecidos".

Otra opción es la de usar un método intermedio: vas generando el siguiente número aleatorio de SEED, por ejemplo, en los Atari ST, se hace así (con SEED de tamaño igual a 4 bytes):

SEED = SEED * 0x31415926
IF SEED = 0 THEN SEED = VBLCOUNT (contador de interrupciones verticales, o sea, cuadros de pantalla, hasta el momento)

Teniendo un valor de un byte, el mejor generador que encuentres empezará a repetir valores a los 256 extraídos. Por eso es mejor usar dos o más bytes.

Si quieres ver uno de dos bytes bastante bueno (secuencia de 8192 valores), mírate la parte final de este mensaje. El análisis de la aleatoridad de este generador está en otro mensaje.

Avatar de Usuario
Bubu
Atari 1040 STf
Atari 1040 STf
Mensajes: 886
Registrado: 04 Abr 2018, 23:10
Sistema Favorito: Spectrum 16Kb/48Kb
primer_sistema: Spectrum 16Kb/48Kb
consola_favorita: Atari 2600
Primera consola: Nintendo GameBoy
Gracias dadas: 20 veces
Gracias recibidas: 60 veces

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Bubu » 07 Nov 2018, 10:41

Bueno, explorer, he entrado en el enlace que me ponías, y he alucinado en 11 dimensiones. Tela, telita, tela, el análisis del PENGO. Lo he marcado como pendiente de lectura, tiene pinta de que me va a encantar. Yo tengo unas ganas locas de hacer un análisis de esos al Frogger: clasificar las zonas de memoria, darle nombre a las variables, darle nombre a las subrutinas, etc.

Ay...

Y a lo que vamos, dices que la rutina para números aleatorios es ésta:

Código: Seleccionar todo

(valor aleatorio inicial) = $365A

hl := (valor aleatorio anterior)
bc := hl
hl := 3 x hl
a := h + c
h := a
(nuevo valor aleatorio) = hl
(valor publicado) = h


Esto me recuerda bastante al algoritmo de generación del laberinto en el Berzerk, que publiqué aquí:

Código: Seleccionar todo

(valor aleatorio inicial) = $3153

hl: = (valor aleatorio anterior)
hl:= 7 x hl + $3153
hl:= 7 x hl + $3153
(nuevo valor aleatorio) = hl
(valor publicado) = h AND %11


Como ves, el valor publicado sólo tiene 2 bits, uséase, es un número del 0 al 3, lo cual sirve para pintar un muro, pero en Berzerk una pantalla tiene 8 muros, por lo que lo que se hace es llamar a esta función 8 veces, y así se obtiene un número de 16 bits.

En fins, todo esto es magistral.

A mí me da que no existe un método matemático para deducir cuán aleatoria es una función, ni cuál es el valor ideal de la semilla inicial, sino que lo que se hace es prooponer una función y una semilla inicial, ejecutarlo un montón de veces, guardar los valores generados, y "ver" si hay bloqueos, ciclos, etc. Si no los hay, se dan por buenas esa función y esa semilla.
Si una función y semilla no da bloqueos ni ciclos, pero sus valores de salida son "predecibles" (p.ej. si la función es F=S+1, entonces F=1, 2, 3, ..., lo cual es totalmente predecible) tampoco serviría de nada.

Y ¿qué es matemáticamente el concepto de "predictibilidad"? ¿Hay algo que mida el grado de "aleatoriedad"? Pues... en física (yo soy físico, jiji) tenemos un concepto que llamamos ENTROPIA, y que mide el desorden de un sistema. Así las cosas si consideramos que mi sistema son los números aleatorios generados, podría disponer de un método que midiera su entropía. Si es alta, esa función es buena, si no, no.

Bueno, quizás no hay que complicar tanto el jaleo, aunque me resulta bastante interesante... Lo que está claro es que esto de generar números aleatorios en nuestros ordeñadores de 8 bits es un poblemón, y que sólo hay un método simple: proponer una función, desplegarla, almacenar lo que genera, y analizar visualmente si aquello es aleatorio o en cambio es predecible.



---------------------------

Ahora planteo otro poblema que tiene relación con esto, pero no trata sobre la generación misma de números aleatorios, sino sobre su procesado. Supongamos que necesito una función que me genere aleatoriamente los números del 1 al 6, partiendo de una función que genera un número aleatorio de 8 bits (0 al 255). No vale poner un IF N<1 OR N>6 THEN OTRA VEZ
¿Cómo lo haríais? Creo que esto es ya simplemente aplicar algo de arismética digital, ¿nor?

Yo pienso que como genero 256 valores, pero quiero sólo 6 valores, tendría que ver hacer INT (256/6) = 42. Por tanto:

Código: Seleccionar todo

si genero del 0 al 41 --> valor generado = 1
si genero del 42 al 83 --> valor generado = 2
etc
si genero del 210 al 251 --> valor generado = 6


Hay pues un poblema cuando genero del 252 al 255, ¿a quién se lo asigno? Son 4 posibilidades, tendría que asumir p.ej. que el 1, 2, 3, y el 4 van a tener un poquito más de probabilidad de salir...

¿No habría una forma de generar direstamente los números del 1 al 6, en lugar de generar los números del 0 al 255 y operar con ellos?
Si algo funciona... ¡¡NO LO TOQUES!! ¡¡NI DE COÑA!!

Avatar de Usuario
explorer
MSX Turbo R
MSX Turbo R
Mensajes: 398
Registrado: 11 May 2014, 17:10
Sistema Favorito: Atari ST
primer_sistema: Atari 800XL/600XL
consola_favorita: Atari 2600
Primera consola: Atari 2600
Ubicación: Valladolid, España
Gracias dadas: 2 veces
Gracias recibidas: 138 veces
Contactar:

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor explorer » 07 Nov 2018, 23:06

En concreto, el código que usa el Pengo es este trozo de código:

Código: Seleccionar todo

; -----------------------------------------------------------------------------
;; Motor random
; Actualiza el valor aleatorio y devuelve en R.a un valor aleatorio

                        .org $2d7c
random:
                        push    bc
                        push    hl

                        ld      hl,(RANDOM)             ; valor aleatorio actual
                        ld      b,h                     ; bc = hl
                        ld      c,l
                        add     hl,hl                   ; hl *= 2
                        add     hl,bc                   ; hl += bc (hl = 3*hl)

                        ld      a,c                     ; a = c
                        add     a,h                     ; a += h
                        ld      h,a                     ; h = a (h = c+h)

                        ld      (RANDOM),hl             ; nuevo valor aleatorio

                        pop     hl
                        pop     bc
                        ret

El resultado es un byte en el registro A. De ahí salen luego, usando máscaras de bits, los distintos valores que usa a lo largo del juego: a veces necesita un valor aleatorio 0..1, 0..3, 0..8, 0..15.

A los generadores en los cuales se multiplica el valor anterior y se le suma una constante, se les llama Generador lineal congruencial. Y sí que hay una fórmula matemática: dada la fórmula de recurrencia

X(n+1) = (a·X(n) + c) mod m

el período de un generador congruencial mezclado (c ≠ 0) es como máximo su módulo, y para algunos valores específicos del multiplicador "a" este período se reduce considerablemente por debajo de este máximo. El generador congruencial mezclado tendrá un período completo para todas las semillas si y sólo si:

  1. m y el incremento c son primos entre sí,
  2. a − 1 es divisible entre todos los factores primos de m,
  3. a − 1 es divisible entre 4 si m es divisible entre 4.
Estos tres requerimientos son conocidos como el teorema Hull-Dobell.

Pero es cierto que la generación de números por medios deterministas es problemático.

«Los generadores lineales congruenciales presentan el inconveniente de generar secuencias de salida cuyos bits presentan distintos niveles de aleatoriedad».

Por ejemplo, el generador del Pengo, aunque genere 8192 números distintos, plantea problemas estadísticos: si te pones a jugar verás que aparecen los mismos patrones de laberintos, una y otra vez (unos 30). Solo si se da el caso de jugar muchas (pero muchas, muchas) partidas seguidas (sin que salga la partida de demostración en los créditos del juego), entonces se observa que los laberintos empiezan a cambiar.

Uno de los primeros generadores de números pseudoaleatorios fue el que inventó John von Neumann en 1946, conocido como el método del cuadrado de en medio. Consiste en tener una semilla, elevarla al cuadrado, y quedarte con los dígitos centrales como nueva semilla.

Luego salieron más métodos como la Secuencia media de Weyl:

Código: Seleccionar todo

#include <stdint.h>

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;

inline static uint32_t msws() {

   x *= x;
   x += (w += s);
   return x = (x>>32) | (x<<32);

}


Para el problema de extraer un valor 1..6, se puede pensar en la misma solución propuesta en el hilo que comentabas de sacar un número 1..100.

El procedimiento sería:

rand(1..6) = 1 + rand(0..5) = 1 + (rand(256) * 5 / 256)

Es decir:
  • rand(256) lo puedes obtener a partir del registro R del z80
  • lo multiplicas por 5 (ver más abajo)
  • te quedas con el byte alto
  • y le sumas 1
5x = 4x + x. Multiplicar por 4 son dos desplazamientos lógicos hacia la izquierda o hacer dos veces add hl,hl. Solo te queda guardar x en un registro temporal.

Al final, con operaciones muy básicas en ensamblador, ya lo tienes resuelto.

Avatar de Usuario
Bubu
Atari 1040 STf
Atari 1040 STf
Mensajes: 886
Registrado: 04 Abr 2018, 23:10
Sistema Favorito: Spectrum 16Kb/48Kb
primer_sistema: Spectrum 16Kb/48Kb
consola_favorita: Atari 2600
Primera consola: Nintendo GameBoy
Gracias dadas: 20 veces
Gracias recibidas: 60 veces

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Bubu » 08 Nov 2018, 00:38

Entonces entiendo que también un método para sacar rand(1..6) sería:

rand(1..6) = 1 + rand(0..1) + rand(0..1) + rand(0..1) + rand(0..1) + rand(0..1)



Muchas gracias por toda la explicación, explorer, me enchantan estos temas.
Si algo funciona... ¡¡NO LO TOQUES!! ¡¡NI DE COÑA!!

Avatar de Usuario
explorer
MSX Turbo R
MSX Turbo R
Mensajes: 398
Registrado: 11 May 2014, 17:10
Sistema Favorito: Atari ST
primer_sistema: Atari 800XL/600XL
consola_favorita: Atari 2600
Primera consola: Atari 2600
Ubicación: Valladolid, España
Gracias dadas: 2 veces
Gracias recibidas: 138 veces
Contactar:

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor explorer » 08 Nov 2018, 00:55

Sí, se podría hacer así, pero son más operaciones.

Avatar de Usuario
Namek
Atari 1040 STf
Atari 1040 STf
Mensajes: 838
Registrado: 11 Jul 2011, 13:13
Gracias dadas: 18 veces
Gracias recibidas: 63 veces

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Namek » 08 Nov 2018, 08:06

explorer escribió:El procedimiento sería:

rand(1..6) = 1 + rand(0..5) = 1 + (rand(256) * 5 / 256)

Es decir:
  • rand(256) lo puedes obtener a partir del registro R del z80
  • lo multiplicas por 5 (ver más abajo)
  • te quedas con el byte alto
  • y le sumas 1
5x = 4x + x. Multiplicar por 4 son dos desplazamientos lógicos hacia la izquierda o hacer dos veces add hl,hl. Solo te queda guardar x en un registro temporal.

Al final, con operaciones muy básicas en ensamblador, ya lo tienes resuelto.
El registro R solo toma valores de 0 a 127... :roll:

Avatar de Usuario
Bubu
Atari 1040 STf
Atari 1040 STf
Mensajes: 886
Registrado: 04 Abr 2018, 23:10
Sistema Favorito: Spectrum 16Kb/48Kb
primer_sistema: Spectrum 16Kb/48Kb
consola_favorita: Atari 2600
Primera consola: Nintendo GameBoy
Gracias dadas: 20 veces
Gracias recibidas: 60 veces

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Bubu » 08 Nov 2018, 09:52

Es verdad, el bit-7 siempre está a 0, pero es tan fácil como coger 2 veces el registro R. El bit-0 del segundo registro R lo usaría como bit-7 del primero:

Código: Seleccionar todo

ld a, r
ld b, a
ld a, r
bit 0, a
ret z
set 7, b
ret



Pero voy a contar por qué es tan malo coger el registro R (a pesar de que se llama R no tié ná que ver con la R de Random, sino de Refresh, jiji): resulta que R depende del número de instrucciones que se han ejecutado, en cada una se incrementa 1 este registro. Así las cosas, como los pogramas siempre ejecutan exácticamente el mismo número de instrucciones cá vez que los ejecutamos, sisnifica que sieeeempre que leemos la 1ª vez el registro R, siempre tié el mismo valor. Y cuando lo leemos la 2ª vez, siempre tié ese otro valor, etc.

Una manera de resolver esto es pidiendo al usuario que pulse una tecla, y cuando la pulse, entóns leo el registro R. Con esto me aseguro que al leer el R unas veces se habrán ejecutado más instrucciones que otras, ya que el usuario tardará unas veces más que otras en pulsar la tecla.

En un Spectrum real esto no ocurre, pues cuando lo encendemos, sale el BASIC, y ahí ya se está cambiando el R. Al hacer LOAD "" y pulsar ENTER, lo mismo, de tal manera que cuando carga un juego pues tenemos el valor de R aleatorio nada más empezar el juego. Pero en los emuladores esto no ocurre. En los emuladores R siempre vale lo mismo al empezar el juego.
Por eso cuando yo diseño un juego siempre le pido al usuario que pulse una tecla para empezar, y entóns leo el R.
Si algo funciona... ¡¡NO LO TOQUES!! ¡¡NI DE COÑA!!

Avatar de Usuario
explorer
MSX Turbo R
MSX Turbo R
Mensajes: 398
Registrado: 11 May 2014, 17:10
Sistema Favorito: Atari ST
primer_sistema: Atari 800XL/600XL
consola_favorita: Atari 2600
Primera consola: Atari 2600
Ubicación: Valladolid, España
Gracias dadas: 2 veces
Gracias recibidas: 138 veces
Contactar:

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor explorer » 08 Nov 2018, 13:48

Namek escribió:El registro R solo toma valores de 0 a 127... :roll:

No soy programador de Spectrum, así que estas cosas se me escapan. Lo siento.

Pego aquí la solución de jitursan para obtener el valor aleatorio de 8 bits a partir del registro R y la semilla anterior:

Código: Seleccionar todo

; Rutina para obtener un pseudoaleatorio entre 0-255 en A
; La semilla inicial es 0
ld hl,(seed)
ld a,r
ld d,a
ld e,(hl)
add hl,de
add a,l
xor h
; Guardamos una nueva semilla para aumentar la aleatoriedad la siguiente invocación
ld (seed),hl
; y almacenamos en HL el valor aleatorio obtenido
ld h,0
ld l,a


Bubu escribió:Por eso cuando yo diseño un juego siempre le pido al usuario que pulse una tecla para empezar, y entonces leo el R.

En teoría no hace falta si tienes algún tipo de contador entre pulsaciones de teclas. Por ejemplo, si tengo un contador de interrupciones verticales, o simplemente, un contador de veces que se ejecuta el bucle principal, ya sé cuánto tiempo ha pasado desde la anterior pulsación, y tomarlo como base para modificar lo que leeré del R.

Bueno... soluciones hay muchas. Y también depende de lo que necesitemos.

Avatar de Usuario
Bubu
Atari 1040 STf
Atari 1040 STf
Mensajes: 886
Registrado: 04 Abr 2018, 23:10
Sistema Favorito: Spectrum 16Kb/48Kb
primer_sistema: Spectrum 16Kb/48Kb
consola_favorita: Atari 2600
Primera consola: Nintendo GameBoy
Gracias dadas: 20 veces
Gracias recibidas: 60 veces

Re: Generación de números aleatorios en Z80 (u otro de 8 bits)

Mensajepor Bubu » 08 Nov 2018, 14:42

explorer escribió:No soy programador de Spectrum, así que estas cosas se me escapan. Lo siento.


El registro R no es específico del Spectrum, es de los microprocesadores Z80 y memorias dinámicas (DRAM).


explorer escribió:Pego aquí la solución de jitursan para obtener el valor aleatorio de 8 bits a partir del registro R y la semilla anterior:

Código: Seleccionar todo

; Rutina para obtener un pseudoaleatorio entre 0-255 en A
; La semilla inicial es 0
ld hl,(seed)
ld a,r
ld d,a
ld e,(hl)
add hl,de
add a,l
xor h
; Guardamos una nueva semilla para aumentar la aleatoriedad la siguiente invocación
ld (seed),hl
; y almacenamos en HL el valor aleatorio obtenido
ld h,0
ld l,a




De esa rutina no entiendo esta instrucción ld e, (hl). ¿Aónde está apuntando hl? ¿A la ROM? ¿A la RAM? ¿Y si esa zona está llena de ceros o $FF's?
Si algo funciona... ¡¡NO LO TOQUES!! ¡¡NI DE COÑA!!


Volver a “Programación”

¿Quién está conectado?

Usuarios navegando por este Foro: Chui y 8 invitados