Введение

Hashlife — это алгоритм с запоминанием (мемоизацией) для вычисления долгосрочной эволюции заданной начальной конфигурации в игре «Жизнь» Конвея и связанных с ней клеточных автоматах, значительно быстрее, чем при использовании альтернативных алгоритмов, имитирующих каждый временной шаг каждой ячейки автомата. Алгоритм был впервые описан Биллом Госпером в начале 1980-х годов во время его исследований в Исследовательском центре Xerox Palo Alto. Первоначально Hashlife был реализован на Lisp-машинах Symbolics с использованием расширения Flavors.

Хашлайф

Hashlife разработан для использования значительной пространственной и временной избыточности, свойственной большинству правил Life. Например, в "Жизни Конвея" многие, на первый взгляд случайные, конфигурации в конечном итоге превращаются в наборы простых устойчивых форм и осцилляторов. Однако Hashlife не зависит от того, остаются ли паттерны на одном и том же месте; он скорее использует тот факт, что в больших паттернах часто встречаются подпаттерны, появляющиеся в нескольких местах, возможно, в разное время.

Представительство

Поле обычно рассматривается как теоретически бесконечная сетка, с рассматриваемым узором, центрированным вблизи начала координат. Для представления поля используется квадродерево (с совместным использованием узлов). Узел на k-м уровне дерева представляет собой квадрат из 2<sup>2k</sup> ячеек, 2<sup>k</sup> на сторону, ссылаясь на четыре узла (k–1)-го уровня, которые представляют четыре квадранта этого квадрата k-го уровня. Например, узел уровня 3 представляет собой квадрат 8×8, который распадается на четыре квадрата 4×4. Явное содержимое ячеек хранится только на уровне 0. Корневой узел должен быть на достаточно высоком уровне, чтобы все живые клетки находились в пределах квадрата, который он представляет. Хотя квадродерево, на первый взгляд, кажется требующим значительно больше накладных расходов, чем более простые представления (например, использование матрицы битов), оно позволяет проводить различные оптимизации. Поскольку каждая клетка либо жива, либо мертва, для узла на уровне 0 существует только две возможности, поэтому, если разрешено совместное использование узлов между родителями, никогда не потребуется более 2 узлов уровня 0 в общей сложности. Аналогично, 4 ячейки квадрата 2×2 могут демонстрировать только различные комбинации, поэтому не требуется больше узлов уровня 1. При переходе на более высокие уровни число возможных квадратов k-го уровня растет как 4<sup>k</sup>, но количество различных квадратов k-го уровня, встречающихся в любом конкретном прогоне, намного меньше, и очень часто одно и то же содержимое квадрата появляется в нескольких местах. Для максимального совместного использования узлов в квадродереве (которое не столько дерево, сколько направленный ациклический граф) мы хотим использовать только один узел для представления всех квадратов с одинаковым содержимым.

Хэширование

Хэш-таблица, или в более общем случае любой ассоциативный массив, может использоваться для сопоставления содержимого квадрата с уже существующим узлом, представляющим это содержимое, чтобы, используя технику хэш-консинга, избежать создания дублирующего узла, представляющего то же содержимое. Если это применяется последовательно, достаточно хешировать четыре указателя на узлы-компоненты, поскольку восходящее хеширование содержимого квадрата всегда обнаружит эти четыре узла на уровне ниже. Оказывается, ряд операций над узлами более высокого уровня можно выполнять без явного вычисления содержимого этих узлов, вместо этого достаточно работать с указателями на узлы, расположенные на фиксированное количество уровней ниже.

Кэширование и суперскорость

Квадричное дерево может быть дополнено таким образом, чтобы узел также кэшировал результат обновления содержимого этого узла. В квадрате недостаточно информации для определения содержимого следующего временного шага на всем квадрате, но содержимое квадрата, центрированного в той же точке, определяет содержимое следующего временного шага этого квадрата. Этот узел уровня k для следующего временного шага смещен на клетки как в горизонтальном, так и в вертикальном направлениях, поэтому даже в случае статических конфигураций он, вероятно, не будет среди узлов уровня k, объединяющихся в квадрат, но на уровне k–1 квадраты снова окажутся в тех же позициях и будут разделены, если не изменятся. На практике вычисление содержимого следующего временного шага – это рекурсивная операция, которая последовательно снизу вверх заполняет поле кэша каждого узла уровня k узлом уровня k–1, представляющим содержимое обновленного центрального квадрата. Совместное использование узлов может значительно ускорить эту операцию, поскольку объем работы пропорционален количеству узлов, а не количеству ячеек, как в более простом представлении. Если узлы используются совместно между квадричными деревьями, представляющими разные временные шаги, то кэшированное значение необходимо вычислить только для тех узлов, которые были вновь созданы на предыдущем временном шаге. Superspeed идет еще дальше, используя наблюдение, что содержимое квадрата фактически определяет содержимое его центрального квадрата для следующих временных шагов. Вместо того чтобы узел уровня k кэшировал узел уровня k–1 для содержимого на 1 шаг вперед, он может кэшировать узел для содержимого на шагов вперед. Поскольку обновления на уровне k вычисляются из обновлений на уровне k–1, а на уровне k–1 есть кэшированные результаты для продвижения на временных шагов, всего двух раундов продвижения на уровне k–1 достаточно для продвижения на шагов на уровне k.

В худшем случае 2 раунда на уровне k–1 могут потребовать 4 полных раунда на уровне k–2, что, в свою очередь, потребует 8 полных раундов на уровне k–3 и так далее, но на практике многие подпаттерны в дереве идентичны друг другу, и большинство ветвей рекурсии коротки. Например, изучаемый паттерн может содержать множество копий одного и того же космического корабля и часто большие участки пустого пространства. Каждый экземпляр этих подпаттернов будет хешироваться в один и тот же узел квадричного дерева и, следовательно, его нужно хранить только один раз. Кроме того, эти подпаттерны необходимо оценивать только один раз, а не один раз для каждой копии, как в других алгоритмах «Жизни». Для разреженных или повторяющихся паттернов, таких как классический пистолет-планер, это может привести к огромному ускорению, позволяя вычислять более крупные паттерны на более высоких поколениях быстрее, иногда экспоненциально. Поколение различных селекционеров и заполнителей пространства, которые растут с полиномиальной скоростью, можно оценить в Hashlife, используя логарифмическое пространство и время. Поскольку подпаттерны разных размеров эффективно работают с разной скоростью, некоторые реализации, такие как программа hlife, написанная Госпером, не имеют интерактивного дисплея; они просто продвигают начальный паттерн на заданное количество шагов и обычно запускаются из командной строки. Более поздние программы, такие как Golly, однако, имеют графический интерфейс, который может управлять движком на основе Hashlife. Типичное поведение программы Hashlife на благоприятном паттерне следующее: сначала алгоритм работает медленнее по сравнению с другими алгоритмами из-за постоянных накладных расходов, связанных с хешированием и построением дерева; но позже будет собрано достаточно данных, и его скорость значительно увеличится – быстрое увеличение скорости часто описывается как «взрыв».

Недостатки

Как и многие алгоритмы с мемоизацией, Hashlife может потреблять значительно больше памяти, чем другие алгоритмы, особенно для умеренно больших паттернов с высокой энтропией или содержащих подпаттерны, плохо выровненные по границам узлов квадродерева (то есть размеров, являющихся степенями двойки); кэш является слабым местом. Он также может требовать больше времени для обработки таких паттернов. Golly, как и другие симуляторы «Жизни», предоставляет возможность переключаться между Hashlife и традиционными алгоритмами. Hashlife значительно сложнее в реализации. Например, ему требуется специальный сборщик мусора для удаления неиспользуемых узлов из кэша. Поскольку Hashlife разработан для обработки в основном предсказуемых паттернов, хаотичные и взрывные правила обычно работают в нем гораздо хуже, чем в других реализациях.