HashLife на коленке

    После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «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 придумали мы сами на основании правил Конвея. В алгоритме оно могло бы быть любым, от него основной код не зависит
    • +58
    • 5,5k
    • 7
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 7
    • +2
      Спасибо за статью. Правильно ли я понимаю, что эволюцию через 2^k — 1 получить наиболее трудозатратно?
      • 0
        Пожалуй, да. Способ получить результат через время T мог бы быть таким:
        Берем интересующую нас область S, она порождается из области S0=S*T (здесь * — расширение на T клеток в каждую сторону). Предположим, что мы знаем результат развития области S0 через время T1=N1*k, где N1 — степень двойки, k=[T/N1]. Этот результат представлен как двумерный массив квадратов со стороной 2*N1. Теперь смотрим. Если T-T1<N1/2, то разбиваем каждый квадрат на четыре части, это и будет массив для следующего шага. Если нет, придется просчитать эволюцию на N1/2 шагов вперед. Для самих квадратов со стороной 2*N1 берем их результат, для квадратов на стыках — пользуемся тем же методом, что и в Unite. Насколько я понимаю, новых квадратов в словарь при этом не добавится, но доказать это утверждение еще не пробовал.
        После получения нового массива полезно проверить, какие клетки на краю нам нужны, и выбросить лишние.
      • +7
        Глаз упорно читает «HalfLife» вместо «HashLife» ))
        • +2
          «HashLife как наиболее эффективный способ интерпретации разумных программных объектов. Вся история вашей цивилизации будет просчитана за полчаса! Забудьте про жизнь на скорости 1/17 от реального времени!»
        • +5
          Алгоритм мутновато описан, я ничего не понял пока не прочитал эту статью.
          • 0
            Спасибо за ссылку. Может быть, кому-нибудь пригодится. Я сам этой статьи не читал, но здесь трудно придумать что-нибудь неправильное. Хотя, надо прочитать подробнее. Может быть, у автора есть какие-нибудь детали, которых я не заметил.
          • 0
            Помню на своём первом компе делал жизнь по другому: считался bounding-box где что-то есть + поле билось на достаточно крупные квадраты и там, где ничего нет — расчет не проводился.

            Позволяло бодренько гонять на поле 2048x2048 и выше на P-133 :-)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.