После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «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 – он и будет ответом.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/0f9/6f3/150/0f96f3150d56d2ff181b5b0eb4c0e261.png)
Для реализации алгоритма нам нужно уметь следующее:
Если искать результат эволюции в момент построения квадрата, то достаточно иметь структуру с 5 полями:
Тогда алгоритм объединения четырех квадратов в один можно записать так:
Собственно, все. Остались мелочи:
Остановить рекурсию. Для этого в словарь заносятся все квадраты 4*4 и результаты их эволюции на 1 шаг (собственно, только в этом месте программе требуется знание правил игры). Для квадратов 2*2 эволюция на полшага не просчитывается, они помечаются каким-нибудь особым образом.
Удвоить число шагов эволюции. В терминах алгоритма это то же самое, что и удвоить размер квадрата, содержащего исходное поле. Если мы хотим оставить квадрат в центре, дополнив его нулями, можно поступить так:
Здесь 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 бита.
Алгоритм я опробовал на таких конструкциях:
«Мусороукладчик».
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/0b0/d29/d53/0b0d29d53615a8fa39524df99db3da39.png)
Движется со скоростью 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 точек.
Что необычного в этом алгоритме? Я бы отметил следующее:
Общая идея алгоритма такая.
Допустим, что у нас есть квадрат поля размером 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 – он и будет ответом.
![](https://habrastorage.org/getpro/habr/post_images/0f9/6f3/150/0f96f3150d56d2ff181b5b0eb4c0e261.png)
Для реализации алгоритма нам нужно уметь следующее:
- Разбить квадрат на четыре квадратика;
- Найти результат эволюции квадрата;
- По четырем квадратикам найти состоящий из них квадрат.
Если искать результат эволюции в момент построения квадрата, то достаточно иметь структуру с 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 бита.
Алгоритм я опробовал на таких конструкциях:
«Мусороукладчик».
![](https://habrastorage.org/getpro/habr/post_images/0b0/d29/d53/0b0d29d53615a8fa39524df99db3da39.png)
Движется со скоростью 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 точек.
Что необычного в этом алгоритме? Я бы отметил следующее:
- Мы практически без усилий получили программу, способную отделять пустые участки от активных, отслеживать активные участки и отрабатывать их взаимодействие. Если бы мы писали такой анализ напрямую, через множество динамических двумерных массивов, программа была бы намного сложнее.
- Алгоритм не только вычисляет состояние поля через T шагов – он запоминает все развитие. Из результата его работы можно без особого труда извлечь состояние через любой промежуток T_k=2^k (как получить состояние поля через время, не являющееся степенью двойки – отдельный вопрос). При этом вся эволюция оказывается хорошо упакованной – опять-таки, без специальных усилий: 2^40 поколений «мусороукладчика» уложились в 3 MB.
- Несмотря на то, что словарь строится по исходной конфигурации, его содержимое от этой конфигурации не зависит. После того, как мы закончили какой-нибудь расчет, мы можем воспользоваться тем же словарем для новой конфигурации, и при везении сэкономить немало времени (правда, я не пробовал).
- Формально конфигурации на плоскости предствлены в виде 4-деревьев. Но для анализа взаимодействия между крайними точками соседних ветвей мы не осуществляем явного спуска до этих точек, а спускаемся только на 1-2 шага, после чего ищем/строим дерево, подходящее для решения нашей задачи. Впрочем, здесь ничего необычного — только то, что времени из-за построения новых узлов мы не теряем, а скорее, наоборот.
- В алгоритме нигде не используется ни реальный размер «атомарных» клеток, ни число их состояний. Самый низкий уровень, до которого может спуститься рекурсия — клетки с 16 состояниями, которые мы воспринимаем как квадратики 2*2. Пространство-время на этом уровне (для алгоритма) выглядит как гранецентрированная решетка (трехмерная шахматная доска, из которой взяли только черные клетки). Число 16 придумали мы сами на основании правил Конвея. В алгоритме оно могло бы быть любым, от него основной код не зависит