Los demonios de Griffeath

Hace unos días volví a encontrarme con mi amigo Jorge Portillo para jugar a unos juegos de mesa.

Jorge y yo nos conocemos desde el instituto, fuimos compañeros de aventuras de Dungeons and Dragons, y coincidimos de nuevo en los estudios de Ingeniería Informática en la Universidad Complutense.

Tras una partida de Formula D salieron una vez más los recuerdos de nuestros años mozos y Jorge sacó del cajón unos papeles impresos. "A ver si te acuerdas de esto", dijo mientras me enseñaba un listado de impresora matricial, en papel continuo.

Se trataba del listado de un programa. La cabecera incluía la fecha: 29 de abril de 1994. A las 5:42 PM, para ser precisos.

Bienvenidos a 1994

Ya ni nos acordábamos de qué demonios era ese listado. Por la pinta del código, debía ser Pascal o Modula-2, los lenguajes que por aquellos años usábamos en la carrera. Sí, tras mirarlo más detenidamente era Pascal, seguramente habríamos usado Turbo Pascal para editarlo. Y efectivamente, era un demonio, o al menos ese era el título del programa.

El código era corto y fácil de entender, además de estar lleno de comentarios a boli azul. Y una implementación bastante sencilla, que hacía fácil su lectura. Un procedimiento inicial generaba un tablero 2D, con números aleatorios correspondientes a colores. Y después un bucle infinito que calculaba las siguientes generaciones de colores a partir de unas reglas sencillas.

Vale, ya me iba sonando todo esto... algún tipo de autómata celular seguramente, pero no adelantemos acontecimientos. Pensaba que lo más bonito sería aprovechar este viaje al pasado y saborearlo, volver a escribir el código... en Turbo Pascal directamente. Como en los viejos tiempos.

DOSBox, la máquina del tiempo

Han pasado ya varias décadas desde que imprimimos ese listado en el laboratorio de la facultad, y todo ha cambiado muchísimo.

¿Cómo hace uno hoy día para programar en Pascal? Resulta que hay unas cuantas opciones. Por ejemplo, está Turbo Pascal Online, un IDE que funciona directamente en un navegador web. Está muy bien, pero sólo ofrece modo texto, y este programa cambiaba a gráficos VGA. Cuando Turbo Pascal quedó atrás con la llegada de Delphi a mediados de los 90, apareció Free Pascal, que sigue siendo mantenido a día de hoy.

El cambio a modo VGA no era trivial: había que llamar a la BIOS para seleccionar el modo 13h, cargando los registros ah := 0, al := 19 y ejecutando la interrupción 10h. La verdad ya ni me acordaba de todo esto, pero desde luego eso no iba a funcionar en mi Mac. Necesitaba un PC con MS-DOS. No tenía ninguno a mano, así que opté por la forma más práctica de hacerlo: emulando con DOSBox.

Ya tenía todas las piezas. De vuelta al MS-DOS de 1994, instalé Free Pascal, un IDE muy similar a Turbo Pascal, y pude por fin teclear el código del listado impreso. Como referencia, aquí está el código completo, en toda su sencillez estudiantil:

PROGRAM Demonio;

uses Dos, Graph, Crt;

CONST Max_X = 150; Max_Y = 150;

TYPE
  Fila = ARRAY [0..Max_X] OF BYTE;
  Tablero = ARRAY [0..Max_Y] OF Fila;

VAR Tab1, Tab2: Tablero;
    Res: REGISTERS;
    X, Y, Colores: INTEGER;

(* Generacion Cero*)

PROCEDURE Generacion_Cero (VAR tA : Tablero);

VAR i, j : INTEGER;

BEGIN
  Randomize;

  FOR i := 0 TO x DO
    FOR j := 0 TO y DO BEGIN
                         tA[i,j] := TRUNC(RANDOM(Colores)+1);
                         MEM[$A000:j*320+i] := tA[i,j]
                       END
END;

(* Siguiente Generacion *)

PROCEDURE Siguiente_Generacion (VAR tA, tB : Tablero);

VAR i, j, ii, id, jar, jab, color: INTEGER;

BEGIN
  FOR i := 0 TO x DO
    FOR j := 0 TO y DO
      BEGIN
        IF i = 0 THEN ii := x ELSE ii := i-1;
        IF i = x THEN id := 0 ELSE id := i+1;
        IF j = 0 THEN jar := y ELSE jar := j-1;
        IF j = y THEN jab := 0 ELSE jab := j+1;
        IF tA[i,j] = Colores THEN color := 1 ELSE color := tA[i,j]+1;

        IF ((tA[ii,j] = color)
            OR (tA[id,j] = color)
            OR (tA[i,jar] = color)
            OR (tA[i,jab] = color)) THEN BEGIN
                                           tB[i,j] := color;
                                           MEM[$A000:j*320+i] := color
                                         END
                                    ELSE tB[i,j] := tA[i,j]

      END;
      tA := tB
END;

(* PROGRAMA PRINCIPAL *)

BEGIN
  Write ('¿CUANTOS COLORES? (lo normal, entre 12 y 16) (entre 1 y 256) ');
  REPEAT
    ReadLn (Colores)
  UNTIL (Colores > 0) AND (Colores < 257);

  Write(' ANCHURA DEL TABLERO (m�ximo 150) = ');
  REPEAT
    ReadLn (X)
  UNTIL (X > 0) AND (X < Max_X + 1);

  Write (' ALTURA DEL TABLERO (m�ximo 150) = ');
  REPEAT
    ReadLn (Y)
  UNTIL (Y > 0) AND (Y < Max_Y + 1);

  WITH Res DO
    BEGIN
      ah := 0;
      al := 19
    END;
  INTR ($10, Res);

  Generacion_Cero(Tab1);

  REPEAT
    Siguiente_Generacion(Tab1, Tab2)
  UNTIL KeyPressed;

  WITH Res DO
    BEGIN
      ah := 0;
      al := 3
    END;
  INTR($10, Res)
END.

Compile, Make, Build... Run!

Tras un rato peleándome con la configuración del teclado conseguí transcribir el listado completo, y compilarlo.

Al ejecutarlo, esto es lo que apareció en mi pantalla:

Vida Artificial

¡Así que efectivamente esto es lo que era!

Se trataba de un autómata celular, en concreto el "Demonio de Griffeath". Uno de los ejemplos que vimos en la asignatura de Vida Artificial, que cursamos como optativa de Biología.

Personalmente, encuentro que esta rama de la computación es fascinante. Dado un escenario sencillo y unas reglas muy básicas, ver cómo surgen los comportamientos emergentes es increíble.

En este ejemplo las reglas son muy básicas:

1. Partimos de un tablero bidimensional. En el ejemplo, máximo de 150x150, o sea, 22.500 celdas. El tablero es toroidal: las celdas de la derecha conectan con las de la izquierda, y las de arriba con las de abajo.
2. Inicialmente (generación 0), cada celda tiene un estado aleatorio, que nosotros representamos mediante un color. En el ejemplo, hay 10 estados, numerados del 1 al 10.
3. Los colores van ordenados como un ciclo. El 2 vence al 1, el 3 vence al 2, el 10 vence al 9, pero el 1 vence al 10. Como un círculo.
4. Cada generación se calcula a partir de la anterior, recorriendo las celdas. Si alguna tiene en su "vecindario" a otra celda con el color siguiente, toma este color. El vecindario estándar es el llamado vecindario de Von Neumann, consistente en la celda de arriba, abajo, izquierda y derecha. El vecindario de Moore incluye además las diagonales inmediatas.

Eso es todo, a partir de ahí se trata de generar un nuevo tablero para la siguiente generación, pintarlo, y continuar a la generación 2, 3, etc.

El resultado de todo esto es que de un desorden inicial, van surgiendo patrones. En concreto, los llamados "demonios", patrones cíclicos formados por celdas adyacentes que contienen, en orden, un estado de cada color.

Wikipedia describe esta fase como la “etapa de los demonios”: ciclos de celdas adyacentes que contienen los estados en orden y que giran continuamente, generando ondas en espiral alrededor de ellos.

Pero... ¿quién es Griffeath?

David Griffeath es un matemático estadounidense, profesor emérito de la University of Wisconsin–Madison, que dedicó buena parte de su carrera a estudiar cómo pueden surgir estructuras complejas a partir de reglas locales extremadamente sencillas.

Su manera de mirar los autómatas celulares es especialmente interesante. Para él, una cuadrícula de células que evoluciona según unas pocas reglas es una especie de "sopa primordial" digital: partimos del desorden y dejamos que las interacciones locales hagan su trabajo. De ahí pueden emerger ondas, espirales, formas geométricas e incluso estructuras que recuerdan a organismos vivos.

Griffeath hablaba de los autómatas celulares como “toy universes”, “universos de juguete” y describía su método como "mirar películas con mucha atención" (thoughtful movie watching): observar atentamente las películas que generan y utilizarlas para descubrir matemáticas.

La vida y obra de David Griffeath da para otro post, pero no puedo dejar de mencionar que su antigua página personal en la Universidad de Wisconsin es simplemente una receta de sopa de guisantes.

El demonio en un donut

Cuando le expliqué toda esta historia a mi hijo Biel, se le ocurrió que podríamos visualizar el tablero en 3D, como un toroide, esto es, un donut - el tablero 2D se comporta como tal ya que sus lados están conectados con sus contrarios.

Me explica mi hijo que con Blender se pueden definir texturas con Python, así que podríamos probar a generar una textura dinámica con el demonio de Griffeath.

Efectivamente es así, y este es el resultado:

Gracias Biel por el extra de frikismo!

Regreso al Futuro

Estoy muy agradecido a mi amigo Jorge por haber conservado ese listado impreso de Pascal todos estos años. Me ha devuelto la curiosidad y la paciencia para hacer las cosas a mano y con menos recursos. Ha sido un gustazo y un frikerío volver a teclear ese código en el IDE de Pascal, dentro de MS-DOS.

Ahora, de vuelta al futuro, esto es, al presente, las cosas se hacen de otra manera pero la esencia sigue ahí, la curiosidad y la fascinación por los comportamientos emergentes siguen intactos.

Por ello, estuve explorando la manera de actualizar estos códigos y, con ayuda de Claude, monté una versión JS que corre directamente en el navegador. La podéis encontrar en la sección de Proyectos de esta web.

La app tiene controles para generar tableros de diferentes colores, tamaños, y con diferentes vecindarios y paletas. ¡Espero que la disfrutéis tanto como yo e investiguéis sobre Vida Artificial!

Puedes probarlo en Demon.