Números aleatorios y ordenadores

19/12/2017 1 comentario
Menear

¿Quién no ha jugado nunca a un videojuego en el que cada partida es diferente? Si todas las partidas de Tetris o buscaminas siguieran la misma secuencia no tendría ningún interés. Pero ¿cómo hace un ordenador, que sólo sabe hacer operaciones matemáticas con resultados definidos, para generar aleatoriedad?

El Tetris fue uno de los videojuegos favoritos de mi juventud. Combina de una manera extraordinaria unas normas simples con una gran variedad de posibilidades. Así uno va adquiriendo habilidad, pero siempre está a merced de la suerte, y nunca sabes lo que va a ocurrir. Este juego tipo puzzle se basa en ir colocando piezas (llamadas tetrominos) de 7 distintos tipos de modo que se completen líneas enteras y no nos dejemos huecos. No era extraño verte suplicando que por fin caiga una pieza  de tipo I para poder pasar de pantalla. Sin embargo, hay una cuestión que entonces se me pasaba desapercibida, y que sólo fui pensando cuando empecé a programa. ¿Cómo podía ser que cada partida fuera diferente? Un ordenador está diseñado para hacer siempre operaciones matemáticas, y estas tienen un resultado definido. Al menos eso espera uno. ¿De dónde vienen entonces el orden aleatorios de las piezas? 

Tetris_2 

 

Números aleatorios y pseudoaleatorios

La idea de aleatoriedad es bien antigua. Casi desde que existe el ser humano existen los juegos de azar. Varios milenios antes de Cristo ya se practicaban juegos de azar en China y Egipcio, y según la mitología griega Zeus, Hades y Poseidón se dividieron el mundo jugando a "tirar los dados". 

 Aquiles 

Ya en los juegos de azar encontramos el problema de generar números aleatorios. Al lanzar un dado, o la bola en una ruleta el propósito es precisamente obtener un resultado aleatorio, ya que si se puede predecir el resultado alguien podría aprovecharse y ganar. Podríamos usar esta manera para generar números aleatorios. Si lanzamos una buena moneda al aire obtendremos una serie aleatoria de 'cara' y 'cruz', que podemos sin problema convertir en '0's y '1's. Este método es bastante limitado y no es fácilmente usable por un ordenador. El principal problema es el tiempo que requiere. Lanzar dados puede parecer simple, pero si necesitas un millón de números es una tarea larga y tediosa.  

Una manera "primitiva" de usar números aleatorios con ordenadores es el uso de bases de datos. De hecho, todavía hay dispositivos como radios y marcos digitales que utilizan este método para simular aleatoriedad. Este método tiene dos problemas. Primero, hay que generar grandes bases de datos y asegurarse de que no se usan de manera repetida. Si utilizas los mismos números una y otra vez ya no son aleatorios, y cualquier cálculo que hagas pierde validez. El segundo problema es aún peor. Los números se deben almacenar, y eso ocupa mucho espacio. Además, leer los números de un disco duro requiere mucho tiempo (más que generarlos, porque eso se hace en la memoria RAM). Veamos un ejemplo, yo quiero simular un sistema que tiene 15 variables, para eso tengo que generar series de 15 números de doble precisión. Cada número en doble precisión ocupa 64 bits, que son 8 bytes. Si mi simulación requiere 10 millones de series, que no es mucho, requiero 1200 millones de bytes, o 1,2 gigabytes de números aleatorios. Esto no es un caso extremo, muchas simulaciones requieren más, y si además la tengo que repetir varias veces ya necesito una cantidad enorme de datos.

Parece claro que si queremos usar números aleatorios en el ordenador tendremos que ser capaces de generarlos con el mismo ordenador. Por otro lado, también tenemos claro que un ordenador sólo nos dará números obtenidos por operaciones matemáticas que tienen un resultado bien definido. Frente a esta disyuntiva sólo nos queda tomar un camino intermedio. En lugar de usar números aleatorios, usaremos números obtenidos por operaciones matemáticas que se parezcan a los aleatorios. Estos son los números pseudoaleatorios. Aunque se parezcan, no hay que olvidar nunca que no son aleatorios de verdad y pueden fallar para ciertas aplicaciones. Esto fue apreciado por uno de los primeros científicos interesados en este tema,el físico John von Neumann. Él mismo reconocía que la tarea en sí era imposible y acuñó la frase "aquel que trate de producir dígitos aleatorios mediante métodos aritméticos está, por supuesto, pecando"1.

¿Qué requisitos debe cumplir una serie de números para que se consideren pseudoaleatorios? Eso es un tema de ferviente discusión y los requisitos se van actualizando a medida que los ordenadores van mejorando. Veamos los más sencillos, con ejemplos y contraejemplos, para familiarizarnos con el tema. Para ellos nos centramos en números binarios2 ('0's y '1's) y suponemos que tenemos una serie muy grande. 

Requisitos:

  • Tiene que haber aproximadamente el mismo número de '0's y '1's. Esto evita la serie '0000000....', pero no la serie '01010101...', que tampoco es válida.
  • No tiene que haber una periodicidad dentro de la serie. Obviamente pequeñas repeticiones habrá inevitablemente, pero mediante técnicas estadísticas podemos ver si esa pequeña repetición es esperable o es un problema del algoritmo. Esto evita la serie '01010101...' pero nos deja otras como '01001100011100001111...'.
  • Los '0's y '1's deben aparece agrupados de manera correcta. Esto quiere decir que si tener 30 '0's seguidos es muy improbable debido al tamaño de nuestra serie debemos descartarla si eso ocurre. Esto nos evitaría la serie '01001100011100001111...', pero nos dejaría otras.

Estos son sólo los requisitos más sencillos, pero hay muchos más que tener en cuenta.

 

El método Middle-Square 

Ahora que sabemos a qué problema nos enfrentamos vamos a buscarle una solución. Como ya os imaginaréis hay infinidad de algoritmos para resolver este problema, y cada año aparecen muchos nuevos. En lugar de discutir tecnología puntera será más pedagógico si nos centramos en un método más antiguo y fácilmente entendible. 

El método elegido se lo debemos a von Neumann, y se denominó Middle-Square Method. La idea es sencilla. Primeros decidimos el número de dígitos de nuestros números aleatorios, por ejemplo, dos cifras. Entonces escogemos un número, por ejemplo el 42. A este primer número lo denominamos semilla. Para generar el siguiente número simplemente elevamos la semilla al cuadrado. Esto nos dará en general un número de 4 dígitos (si faltan rellenamos con ceros a la izquierda), en este caso obtenemos 1764. Nuestro nuevo número, y semilla, lo obtenemos con los dos dígitos de enmedio, 76. Si repetimos otra vez obtenemos como nuevo número 77. Así podemos proceder hasta caer en el 00, que siempre se repite, o hasta volver a la semilla inicial.

En la siguiente tabla (autor) podéis ver todas las series de dos dígitos generadas con este método.

Middle 

Este método tiene dos problemas principales. Primero, nunca repite números salvo que ya entre en blucle. Segundo, muchas veces se entra en bucles muy pequeños, con la consecuente pérdida de aleatoriedad. Un ejemplo es el número 675248 como se ve en el siguiente gráfico (autor).

  Middle2

A pesar de sus deficiencias este pionero método ilustra muy bien cómo generar números pseudoaleatorios mediante procedimientos algebraicos. Así, para responder a la pregunta de cómo hace el Tetris para simular aleatoriedad sólo nos falta un ingrediente, la semilla. ¿Qué número utiliza para empezar a generar los otros números? Eso os dejo que lo contestéis vosotros mismos en los comentarios.

 

Notas

1En inglés: "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin".

2Esto no es una limitación, ya que de una cadena de '0's y '1's se pueden generar números en cualquier base.