Pull to refresh

HashLife на коленке

Reading time 5 min
Views 8.5K
После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.





Для реализации алгоритма нам нужно уметь следующее:

  1. Разбить квадрат на четыре квадратика;
  2. Найти результат эволюции квадрата;
  3. По четырем квадратикам найти состоящий из них квадрат.


Если искать результат эволюции в момент построения квадрата, то достаточно иметь структуру с 5 полями:

class Square{
	internal Square LB,RB,LT,RT,Res;
}


Тогда алгоритм объединения четырех квадратов в один можно записать так:
Square Unite(Square a0, Square a1, Square a2, Square a3){
	Square res=FindInDictionary(a0,a1,a2,a3);
	if(res!=null) return res;
// layer at T=N/4
	Square b1=Unite(a0.RB,a1.LB,a0.RT,a1.LT).Res;
	Square b3=Unite(a0.LT,a0.RT,a2.LB,a2.RB).Res;
	Square b4=Unite(a0.RT,a1.LT,a2.RB,a3.LB).Res;
	Square b5=Unite(a1.LT,a1.RT,a3.LB,a3.RB).Res;
	Square b7=Unite(a2.RB,a3.LB,a2.RT,a3.LT).Res;
// layer at T=N/2	
	Square c0=Unite(a0.Res,b1,b3,b4).Res;
	Square c1=Unite(b1,a1.Res,b4,b5).Res;
	Square c2=Unite(b3,b4,a2.Res,b7).Res;
	Square c3=Unite(b4,b5,b7,a3.Res).Res;
	return AddToDictionary(new Square(){ LB=a0,RB=a1,LT=a1,RT=a3,Res=Unite(c0,c1,c2,c3)});
}


Собственно, все. Остались мелочи:

Остановить рекурсию. Для этого в словарь заносятся все квадраты 4*4 и результаты их эволюции на 1 шаг (собственно, только в этом месте программе требуется знание правил игры). Для квадратов 2*2 эволюция на полшага не просчитывается, они помечаются каким-нибудь особым образом.

Удвоить число шагов эволюции. В терминах алгоритма это то же самое, что и удвоить размер квадрата, содержащего исходное поле. Если мы хотим оставить квадрат в центре, дополнив его нулями, можно поступить так:

Square Expand(Square x){
	Square c0=Unite(Zero,Zero,Zero,x.LB);
	Square c1=Unite(Zero,Zero,x.RB,Zero);
	Square c2=Unite(Zero,x.LT,Zero,Zero);
	Square c3=Unite(x.RT,Zero,Zero,Zero);
	return Unite(c0,c1,c2,c3);
}

Здесь Zero – особый квадрат, все части и результат которого равны ему самому.

А можно просто чередовать действия x=Unite(x,Zero,Zero,Zero) и x=Unite(Zero,Zero,Zero,x). Исходный квадрат будет оказываться где-то в центре.

Реализовать словарь. Здесь я красивого решения не нашел: нужен поиск объекта по ключу, который составляет 80% этого объекта (причем надо искать не только оставшиеся 20%, но и сам объект). Повозившись с разными типами коллекций, я махнул рукой и поступил по-фортрановски: описал пять целочисленных массивов (LT,RT,LB,RB,Res) и сказал, что квадрат определяется целым числом –индексом в этих массивах. Индексы от 0 до 15 зарезервированы для квадратиков 2*2. Шестой массив, вдвое большей длины, используется для хеширования.

Еще надо задавать поле и читать результат – но это уже дело техники. Хотя со чтением надо быть осторожным: если выполнить Expand более 63 раз, длина стороны поля перестанет укладываться в 64 бита.

Алгоритм я опробовал на таких конструкциях:

«Мусороукладчик».


Движется со скоростью c/2, оставляет за собой много мусора и каждые 240 шагов выпускает пару планеров. Триллион поколений (точнее, 2^40) вычислились за 0.73 секунды. В словарь попало примерно 120000 квадратиков (1500 на каждое удвоение времени), количество живых клеток на поле – 600 миллиардов.
Фрагмент полученного поля выглядит так:
(2001x2001, 82 KB)

«Битва планерных ружей»

Два планерных ружья расположены на расстоянии 800 клеток друг от друга, выпущенные ими потоки сталкиваются:
(T=2048, 804x504, 11 KB)
Вскоре после столкновения из кучи обломков вылетают планеры, которые уничтожают сначала одно ружье:
(T=4096, 1098x1024, 30 Kb)
А потом и второе (после чего развитие быстро заканчивается):
(T=8192, 3146x3252, 190 Kb)
Время счета – 0.84 сек, число элементов в словаре – около 270000.

«Случайное заполнение»

Поле 1024*1024 случайно заполнено клетками с плотностью 1/3. Для алгоритма это самый сложный случай: конфигурация стабилизируется медленно, и квадратики начинают повторяться не сразу.
Вот пример развития одной из конфигураций:
(T=0, 1024x1024, 300 Kb)
(T=1024, 1724x1509, 147 Kb)
(T=2048, 2492x2021, 177 Kb)
(T=4096, 4028x3045, 300 Kb)
(T=8192, 7100x5093, 711 Kb)
Время счета – 14 секунд, число элементов в словаре – около 15 миллионов, на поле осталось примерно 35000 точек.

Что необычного в этом алгоритме? Я бы отметил следующее:

  1. Мы практически без усилий получили программу, способную отделять пустые участки от активных, отслеживать активные участки и отрабатывать их взаимодействие. Если бы мы писали такой анализ напрямую, через множество динамических двумерных массивов, программа была бы намного сложнее.
  2. Алгоритм не только вычисляет состояние поля через T шагов – он запоминает все развитие. Из результата его работы можно без особого труда извлечь состояние через любой промежуток T_k=2^k (как получить состояние поля через время, не являющееся степенью двойки – отдельный вопрос). При этом вся эволюция оказывается хорошо упакованной – опять-таки, без специальных усилий: 2^40 поколений «мусороукладчика» уложились в 3 MB.
  3. Несмотря на то, что словарь строится по исходной конфигурации, его содержимое от этой конфигурации не зависит. После того, как мы закончили какой-нибудь расчет, мы можем воспользоваться тем же словарем для новой конфигурации, и при везении сэкономить немало времени (правда, я не пробовал).
  4. Формально конфигурации на плоскости предствлены в виде 4-деревьев. Но для анализа взаимодействия между крайними точками соседних ветвей мы не осуществляем явного спуска до этих точек, а спускаемся только на 1-2 шага, после чего ищем/строим дерево, подходящее для решения нашей задачи. Впрочем, здесь ничего необычного — только то, что времени из-за построения новых узлов мы не теряем, а скорее, наоборот.
  5. В алгоритме нигде не используется ни реальный размер «атомарных» клеток, ни число их состояний. Самый низкий уровень, до которого может спуститься рекурсия — клетки с 16 состояниями, которые мы воспринимаем как квадратики 2*2. Пространство-время на этом уровне (для алгоритма) выглядит как гранецентрированная решетка (трехмерная шахматная доска, из которой взяли только черные клетки). Число 16 придумали мы сами на основании правил Конвея. В алгоритме оно могло бы быть любым, от него основной код не зависит
Tags:
Hubs:
+58
Comments 7
Comments Comments 7

Articles