Hashlife es un algoritmo memorizado para calcular el destino a largo plazo de una configuración inicial dada en el Juego de la Vida de Conway y autómatas celulares relacionados , mucho más rápido de lo que sería posible utilizando algoritmos alternativos que simulan cada paso de tiempo de cada celda del autómata. El algoritmo fue descrito por primera vez por Bill Gosper a principios de la década de 1980 mientras se dedicaba a la investigación en el Centro de Investigación de Xerox Palo Alto . Hashlife se implementó originalmente en máquinas Symbolics Lisp con la ayuda de la extensión Flavors .
Hashlife está diseñado para explotar grandes cantidades de redundancia espacial y temporal en la mayoría de las reglas de Life. Por ejemplo, en Life de Conway , muchos patrones aparentemente aleatorios terminan siendo colecciones de naturalezas muertas y osciladores simples . Sin embargo, Hashlife no depende de que los patrones permanezcan en la misma posición; se trata más bien de explotar que los patrones grandes tienden a tener subpatrones que aparecen en varios lugares, posiblemente en diferentes momentos.
El campo se trata típicamente como una cuadrícula teóricamente infinita , con el patrón en cuestión centrado cerca del origen . Se utiliza un árbol cuaternario (con nodos compartidos ) para representar el campo. Un nodo en el k -ésimo nivel del árbol representa un cuadrado de 2 2 k celdas, 2 k de lado, haciendo referencia a los cuatro nodos de nivel k –1 que representan los cuatro cuadrantes de ese cuadrado de nivel k . Por ejemplo, un nodo de nivel 3 representa un cuadrado de 8×8, que se descompone en cuatro cuadrados de 4×4. Los contenidos explícitos de las celdas solo se almacenan en el nivel 0. El nodo raíz tiene que estar en un nivel lo suficientemente alto como para que todas las celdas vivas se encuentren dentro del cuadrado que representa.
Aunque un quadtree parece requerir ingenuamente mucho más trabajo adicional que representaciones más simples (como usar una matriz de bits ), permite varias optimizaciones. Dado que cada celda está viva o muerta, solo hay dos posibilidades para un nodo en el nivel 0, por lo que si se permite que los nodos se compartan entre padres, nunca hay necesidad de tener más de 2 nodos de nivel 0 en total. Del mismo modo, las 4 celdas de un cuadrado de 2 × 2 solo pueden exhibir diferentes combinaciones, por lo que tampoco se necesitan más de esa cantidad de nodos de nivel 1. Al ir a niveles superiores, el número de posibles cuadrados de nivel k aumenta como , pero el número de cuadrados de nivel k distintos que ocurren en cualquier ejecución particular es mucho menor y, muy a menudo, el mismo contenido de cuadrado aparece en varios lugares. Para compartir al máximo los nodos en el quadtree (que no es tanto un árbol como un gráfico acíclico dirigido ), solo queremos usar un nodo para representar todos los cuadrados con el mismo contenido.
Una tabla hash , o más generalmente cualquier tipo de matriz asociativa , puede utilizarse para mapear contenidos cuadrados a un nodo ya existente que represente esos contenidos, de modo que uno a través de la técnica de hash consing puede evitar la creación de un nodo duplicado que represente esos contenidos. Si esto se aplica de manera consistente, entonces es suficiente aplicar un hash a los cuatro punteros a los nodos componentes, ya que un hash de abajo hacia arriba de los contenidos cuadrados siempre encontraría esos cuatro nodos en el nivel inferior. Resulta que se pueden realizar varias operaciones en nodos de nivel superior sin producir explícitamente los contenidos de esos nodos, en su lugar, es suficiente trabajar con punteros a nodos un número fijo de niveles hacia abajo.
El árbol cuaternario se puede ampliar para que en un nodo también se almacene en caché el resultado de una actualización de los contenidos de ese nodo. No hay suficiente información en un cuadrado para determinar los contenidos del siguiente paso de tiempo en todo ese cuadrado, pero los contenidos de un cuadrado centrado en el mismo punto determinan los contenidos del siguiente paso de tiempo del cuadrado. Este nodo de nivel k para ese siguiente paso de tiempo está desplazado por celdas tanto en la dirección horizontal como en la vertical, por lo que incluso en el caso de una naturaleza muerta, probablemente no estaría entre los nodos de nivel k que se combinan en el cuadrado, pero en el nivel k –1 los cuadrados están nuevamente en las mismas posiciones y se compartirán si no se modifican.
En la práctica, calcular el contenido del siguiente paso de tiempo es una operación recursiva que, de abajo a arriba, llena el campo de caché de cada nodo de nivel k con un nodo de nivel k –1 que representa el contenido del cuadrado central actualizado. Compartir nodos puede acelerar significativamente esta operación, ya que el trabajo requerido es proporcional al número de nodos, no al número de celdas como en una representación más simple. Si se comparten nodos entre árboles cuaternarios que representan diferentes pasos de tiempo, entonces solo será necesario calcular un valor en caché de aquellos nodos que se crearon recientemente durante el paso de tiempo anterior.
Superspeed va más allá, utilizando la observación de que el contenido de un cuadrado en realidad determina el contenido de su cuadrado central para los siguientes pasos de tiempo. En lugar de tener un nodo de nivel k que almacene en caché un nodo de nivel k –1 para el contenido que se encuentra un paso por delante, podemos hacer que almacene en caché uno para el contenido que se encuentra pasos por delante. Debido a que las actualizaciones en el nivel k se calculan a partir de las actualizaciones en el nivel k –1, y dado que en el nivel k –1 hay resultados almacenados en caché para los pasos de tiempo que avanzan, bastan dos rondas de avance en el nivel k –1 para avanzar por pasos en el nivel k .
En el peor de los casos, 2 rondas en el nivel k –1 pueden tener que hacer 4 rondas completas en el nivel k –2, lo que a su vez requiere 8 rondas completas en el nivel k –3, etc., pero en la práctica, muchos subpatrones en el árbol son idénticos entre sí y la mayoría de las ramas de la recursión son cortas. Por ejemplo, el patrón que se está estudiando puede contener muchas copias de la misma nave espacial y, a menudo, grandes franjas de espacio vacío. Cada instancia de estos subpatrones se convertirá en el mismo nodo del árbol cuaternario y, por lo tanto, solo es necesario almacenarlos una vez. Además, estos subpatrones solo necesitan evaluarse una vez, no una vez por copia como en otros algoritmos de Life.
En el caso de patrones dispersos o repetitivos, como el clásico cañón planeador , esto puede generar enormes aceleraciones, lo que permite calcular patrones más grandes en generaciones más altas con mayor rapidez , a veces de manera exponencial . Una generación de los diversos reproductores y rellenadores de espacio , que crecen a velocidades polinómicas , se puede evaluar en Hashlife utilizando espacio y tiempo logarítmicos .
Dado que los subpatrones de distintos tamaños se ejecutan efectivamente a distintas velocidades, algunas implementaciones, como el programa hlife del propio Gosper, no tienen una pantalla interactiva; simplemente avanzan el patrón de inicio una cantidad determinada de pasos y, por lo general, se ejecutan desde la línea de comandos . Sin embargo, programas más recientes como Golly tienen una interfaz gráfica que puede controlar un motor basado en Hashlife.
El comportamiento típico de un programa Hashlife en un patrón propicio es el siguiente: primero, el algoritmo se ejecuta más lento en comparación con otros algoritmos debido a la sobrecarga constante asociada con el hash y la construcción del árbol ; pero luego, se recopilarán suficientes datos y su velocidad aumentará enormemente; el rápido aumento de velocidad a menudo se describe como " explosión ".
Al igual que muchos códigos memorizados , Hashlife puede consumir significativamente más memoria que otros algoritmos, especialmente en patrones de tamaño moderado con mucha entropía, o que contienen subpatrones mal alineados con los límites de los nodos del árbol cuaternario (es decir, tamaños de potencia de dos); la caché es un componente vulnerable. También puede consumir más tiempo que otros algoritmos en estos patrones. Golly , entre otros simuladores de Life, tiene opciones para alternar entre Hashlife y algoritmos convencionales.
Hashlife también es significativamente más complejo de implementar . Por ejemplo, necesita un recolector de basura dedicado para eliminar los nodos no utilizados de la memoria caché.
Debido a que están diseñadas para procesar patrones generalmente predecibles, las reglas caóticas y explosivas generalmente funcionan mucho peor en Hashlife que en otras implementaciones. [1]
