16.07.2026 11:57
lightln2 12 9800 Источник

Игра «Жизнь», придуманная Джоном Конвеем в 1970 году, до сих пор не теряет популярности. В 1984 году американский математик Билл Госпер опубликовал статью с алгоритмом, позже названным HashLife, ускоряющим симуляцию в триллионы и больше раз. Описание алгоритма и его реализации довольно сложны для понимания и отладки. Я хочу вам представить его версию, реализация которой на питоне влезает на один экран, а суть умещается в 40 строк кода. Если вам это интересно, а также то, как HashLife связан с динамическим программированием, персистентными структурами и системой контроля версий Git, добро пожаловать под кат.

Игра «Жизнь» – клеточный автомат на плоскости, в котором на каждом шаге времени клетка выживает при двух или трёх соседях, мёртвая клетка рождается при трёх соседях, иначе клетка остаётся или становится мёртвой.

Код на Питоне, эмулирующий игру
class SimpleLife:
  def __init__(self, points):
    self.field = set(points)

  def _evolve(self, x, y):
    own = 1 if (x,y) in self.field else 0
    alive = sum((x-1+i, y-1+j) in self.field for i in range(3) for j in range(3)) - own
    return alive == 3 or (alive == 2 and own == 1)
    
  def step(self):
    newfield = set()
    for x,y in self.field:
      for i in range(3):
        for j in range(3):
          if self._evolve(x-1+i, y-1+j):
            newfield.add((x-1+i, y-1+j))
    self.field = newfield

Код можно ускорить в сотни и тысячи раз, и даже в миллионы раз на GPU, но скорость каждого шага пропорциональна как минимум количеству живых клеток. Алгоритм Билла Госпера позволяет эмулировать миллиарды клеток на миллиарды шагов за секунды, переиспользуя результаты вычислений для повторяющихся частей. Про HashLife есть много информации в интернете, в том числе, и на Хабре, но я хочу рассказать немного отличающуюся версию, которую нигде не встречал. Основная идея – рекурсивное разбиение поля не на 4, а на 9 частей.

Разбиение поля на дерево

Представим, что наше поле – квадрат размера 3^n\times 3^n для некоторого большого n. Мы можем представить его в виде дерева: разобьём его на 9 квадратов размера 3^{n-1} \times 3^{n-1}, выложенных в решетку 3x3. Далее каждый квадрат рекурсивно разобьём на все меньшие квадраты, пока не дойдем до квадрата размера 1x1, то есть, одной клетки. Так как многие квадраты будут совпадать, мы можем их дедуплицировать: назначить одинаковым квадратам один id, и в узле дерева держать только массив 3x3 из девяти id квадратов нижнего уровня. Зарезервируем id=0,1 для мертвых и живых клеток поля, тогда узел дерева самого нижнего уровня будет содержать кусок поля 3x3. Например:

При этом можем дедуплицировать квадраты снизу вверх, от менших к большим: два узла дерева совпадают, если совпадают все девять id их дочерних узлов. Это первый из двух трюков в HashLife, позводяющий компактно хранить поля размером миллиард на миллиард клеток и больше.

код на питоне с примером создания пустого узла
class Hashlife:
    def __init__(self):
        self.node_to_id = {}
        self.nodes = [None, None] # reserve for leaves

    def get_id(self, node) -> int:
        if node not in self.node_to_id:
            self.node_to_id[node] = len(self.nodes)
            self.nodes.append(node)
        return self.node_to_id[node]

    def make_empty(self, size):
        e = 0 if size == 3 else self.make_empty(size//3)
        return self.get_id(((e,e,e),(e,e,e),(e,e,e)))

Связь с Git

Мы от двумерного поля перешли к базе данных узлов, каждый из которых либо лист, либо ссылается на дочерние узлы; в этой реализации пока нету никакой специфики игры. Такая структура часто встречается, самый известный пример – система контроля версий Git. Он хранит файлы и директории как узлы делева, которые ссылаются на id дочерних. Только вместо числовых id, они используют хеш данных:

id     name       type     data
--------------------------------------------
ca2f5  main.py    file   print("Hello World!")
dd35a  readme.md  file   Sample python project
3af4e  src        dir    [ ca2f5 ]
69fed  .          dir    [ dd35a, 3af4e ]

Такая структура позволяет гиту эффективно создавать новые коммиты, отличающиеся от родителей только несколькими файлами, переиспользуя уже существующие объекты. Тогда, если вы знаете id объекта верхнего уровня (в гите они называются ref-ами), вы можете быстро восстановить всё дерево. Это классическая персистентная структура данных, где вместо модификации текущего состояния создаётся новое, переиспользующее неизменившиеся части старого, и все состояния хранятся вместе. Мы эту идею и будем использовать для HashLife.

Эволюция

Возьмем узел дерева первого уровня: квадрат 3x3. Мы можем однозначно понять, как эволюционирует его центральная клетка за 1 шаг: 

    def evolve3x3(self, node) -> int:
        own = node[1][1]
        alive = sum(node[i][j] for i in range(3) for j in range(3)) - own
        return 1 if alive == 3 or (alive == 2 and own == 1) else 0

Давайте теперь возьмем узел второго уровня, представляющий квадрат 9x9 клеток. За один шаг мы можем эволюционировать его внутренний подквадрат 7x7: каждый из 49 квадратов 3x3 мы превратим в узел первого уровня, и рекурсивно вызовем evolve3x3. Если мы повторим эту процедуру еще дважды, для квадрата 7x7 и потом 5x5, то в конце мы получим квадрат 3x3, из которого мы можем создать узел 1-го уровня, являющимся эволюцией центра нашего узла второго уровня через три шага.

Точно также мы можем для любого узла 3^n \times 3^n получить эволюцию его центра 3^{n-1} \times 3^{n-1} через 3^{n-1} шагов: возьмем девять его дочерних подузлов, и в каждом подузле возьмем девять его под-подузлов, расположив их в решётке 9x9. Каждый из 49 квадратов размера 3x3 в решетке превратим в узел размера 3^{n-1} \times 3^{n-1}, и вызовем для него рекурсивно evolve, получив 49 узлов 3^{n-2} \times 3^{n-2} после 3^{n-2} шагов в форме решетки 7x7. Повторим еще дважды, получив решетки 5x5 и 3x3, и из последней создадим узел 3^{n-1} \times 3^{n-1} после 3*3^{n-2} = 3^{n-1} шагов.

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

Еще один технический трюк, упрощающий реализацию: при эволюции решетки 9x9 -> 7x7 -> 5x5, левые верхние ячейки квадратов 3x3 используются только один раз. Поэтому, вместо того, чтобы создавать колию решетки 7x7, мы можем записывать результат в самy решетку, в первые ее 49 клеток.

код эволюции
class Hashlife:
  def __init__(self):
      self.node_to_id = {}
      self.nodes = [None, None]
      self.evolved = {}

  def get_id(self, node) -> int:
      if node not in self.node_to_id:
          self.node_to_id[node] = len(self.nodes)
          self.nodes.append(node)
      return self.node_to_id[node]
    
  def evolve(self, node) -> int:
      if node[1][1] in [0,1]:
        own = node[1][1]
        alive = sum(node[i][j] for i in range(3) for j in range(3)) - own
        return 1 if alive == 3 or (alive == 2 and own == 1) else 0

      if node not in self.evolved:
        field = [[0]*9 for _ in range(9)]
        def fget(x, y): 
          return (tuple(field[x][y:y+3]), tuple(field[x+1][y:y+3]), tuple(field[x+2][y:y+3]))
        def fset(x, y, node):
          field[x][y:y+3],field[x+1][y:y+3],field[x+2][y:y+3] = node

        for i in range(3):
          for j in range(3):
            fset(i*3, j*3, self.nodes[node[i][j]])
        for _ in range(3):
          for x in range(7):
            for y in range(7):
              field[x][y] = self.evolve(fget(x, y))
        self.evolved[node] = self.get_id(fget(0, 0))

      return self.evolved[node]

Это и есть основа алгоритма HashLife, занимающая всего 35 строчек кода на Питоне (сравните с классической реализацией алгоритма, имеющей десятки строчек типа ad = life(m.a.a, m.a.b, m.b.a, m.a.c, m.a.d, m.b.c, m.c.a, m.c.b, m.d.a) ).

Эволюция корня

Эволюция корня дерева, то есть, узла, представляющего всё поле 3^n\times 3^n, сложнее: нам не достаточно получить его центр из метода evolve; наоборот, нам надо в худшем случае увеличить поле в три раза (куда докатится волна изменений за 3^n шагов). Самый простой способ – создадим поле 5x5 ячеек, и поместим наш узел в его центр, заполнив оставшиеся ячейки пустыми узлами нужного размера, и запустим только один шаг evolve 5x5->3x3, и центральный квадрат и будет полем размера 3^{n+1} \times 3^{n+1}, являющимся результатом эволюции всего поля за 3^n шагов. То есть, с каждой эволюцией поля его размер и количество шагов за одну эволюцию будет экспоненциально увеличиваться в три раза: 3, 9, 27, 81, итд.

Вот полный код с проверкой результатов:

полный код на Питоне
class Hashlife:
    def __init__(self):
        self.node_to_id = {}
        self.nodes = [None, None]
        self.evolved = {}
        self.population = {}

    def get_id(self, node) -> int:
        if node not in self.node_to_id:
            self.node_to_id[node] = len(self.nodes)
            self.nodes.append(node)
        return self.node_to_id[node]
    
    def evolve(self, node) -> int:
        if node[1][1] in [0,1]:
            own = node[1][1]
            alive = sum(node[i][j] for i in range(3) for j in range(3)) - own
            return 1 if alive == 3 or (alive == 2 and own == 1) else 0

        if node not in self.evolved:
            field = [[0]*9 for _ in range(9)]
            fget = lambda x, y: (tuple(field[x][y:y+3]), tuple(field[x+1][y:y+3]), tuple(field[x+2][y:y+3]))
            def fset(x, y, node):
                field[x][y:y+3],field[x+1][y:y+3],field[x+2][y:y+3] = node

            for i in range(3):
                for j in range(3):
                    fset(i*3, j*3, self.nodes[node[i][j]])
            for _ in range(3):
                for x in range(7):
                    for y in range(7):
                        field[x][y] = self.evolve(fget(x, y))
            self.evolved[node] = self.get_id(fget(0, 0))

        return self.evolved[node]
    
    def evolve_root(self, node):
        e = self.make_empty(self.get_size(node))
        field = [[e]*5 for _ in range(5)]
        field[2][2] = self.get_id(node)
        fget = lambda x, y: (tuple(field[x][y:y+3]), tuple(field[x+1][y:y+3]), tuple(field[x+2][y:y+3]))

        for x in range(3):
            for y in range(3):
                field[x][y] = self.evolve(fget(x, y))
        return fget(0, 0)

    def make_empty(self, size):
        e = 0 if size == 3 else self.make_empty(size//3)
        return self.get_id(((e,e,e),(e,e,e),(e,e,e)))

    def _makefld(self, field: set, x: int, y: int, size: int) -> int:
        if size == 1: return 1 if (x,y) in field else 0
        field = {(p,q) for p,q in field if x <= p < x+size and y <= q < y+size}
        if not field: return self.make_empty(size)
        size //= 3
        node = tuple(tuple(self._makefld(field, x + size*i, y+size*j, size) for i in range(3)) for j in range(3))
        return self.get_id(node)
    
    def init(self, field: set, size: int):
        field = {(x + size//2, y + size//2) for x,y in field}
        return self.nodes[self._makefld(field, 0, 0, size)]
    
    def get_size(self, node):
        if node[1][1] in [0,1]: return 3
        return 3 * self.get_size(self.nodes[node[1][1]])
    
    def count_cells(self, node):
        if node[1][1] in [0,1]: return sum(sum(row) for row in node)
        if node not in self.population:
            count = sum(self.count_cells(self.nodes[node[i][j]]) for i in range(3) for j in range(3))
            self.population[node] = count
        return self.population[node]

class SimpleLife:
    def __init__(self, points):
        self.field = set(points)

    def _evolve(self, x, y):
        own = 1 if (x,y) in self.field else 0
        alive = sum((x-1+i, y-1+j) in self.field for i in range(3) for j in range(3)) - own
        return alive == 3 or (alive == 2 and own == 1)
    
    def step(self):
        newfield = set()
        for x,y in self.field:
            for i in range(3):
                for j in range(3):
                    if self._evolve(x-1+i, y-1+j):
                        newfield.add((x-1+i, y-1+j))
        self.field = newfield


life = SimpleLife([(1,0), (2,0), (0,1), (1,1), (1,2)])
for i in range(30000):
    if i in {0, 9, 36, 117, 360, 1089, 3276, 9837, 29520}:
        print(i, len(life.field))
    life.step()


life = Hashlife()
node = life.init({(1,0), (2,0), (0,1), (1,1), (1,2)}, 3**2)
steps = 0
for i in range(9):
    print(steps, life.count_cells(node))
    steps += life.get_size(node)
    node = life.evolve_root(node)

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

Этот пример является полнофункциональным, тем не менее, для реальной реализации можно добавить несколько вещей: сборку мусора (периодически удалять узлы, которе больше не используются, кстати, гит это тоже делает), и в эволюции запоминать не только центральный узел через n^k шагов, но также через n^{k-1}, 2n^{k-1} шагов. Тогда, комбинируя частичные эволюции на каждом уровне дерева, можно очень быстро переходить на любое произвольное число шагов в эволюции. Также нужна визуализация, где можно динамически менять масштаб и смотреть на произвольные части поля.

Заключение

Алгоритм HashLife является довольно нишевым, применимым в основном, к клеточным автоматам. Тем не менее, он комбинирует сразу несколько концепций из computer science (деревья, рекурсия, динамическое программирование, персистентные структуры данных). Попробуйте на этой структуре данных реализовать визуализацию или, например, подсчет живых клеток – это будет хорошее упражнение на динамическое программирование в самой классической его форме! Но по отдельности эти концепции очень важны в теории и на практике: динамическое программирование используется, например, в git diff, основанном на алгоритме Майерса; разбиение плоскости на дерево (QuadTree в оригинальном алгоритме, 9-ary tree в нашем) используется в обработке изображений и индексации геоданных; персистентные структуры используются, как мы видели, в Git, а также, например, в текстовых редакторах для Undo/Redo.

Ну и, конечно, с исторической точки зрения, это пример идеи, неожиданно оказавшейся настолько изящной и эффективной, что ее полезно знать каждому, кто интересуется алгоритмами и их практическим применением.

Комментарии (12)


  1. wataru
    16.07.2026 20:33
    #30230168

    Вообще, стандартный hashlife работает чуть-чуть по-другому. Там используется степень 2, а не 3. Откуда вы вообще 3 взяли?

    Результат эволюции куска 2^n x 2^n через 2^(n-1) шагов однозначно определяется куском 2^(n+1) x 2^(n+1). Поэтому там сохраняются именно эти результаты: для куска 2^(n+1) сохраняется результат в центре размера 2^n через 2^(n-1) шагов При n >= 1. Т.е. самый маленький кусок, который вы считаете, это 4x4 через один шаг и сохраняете внутренний квадрат 2x2.

    Потом, чтобы подсчитать ответ для n>1 вы отдельно считаете 9 квадратов для n-1 окаймляющих внутренний кусок, составив из них квадрат размера 2^n + 2^(n-2) через 2^(n-2) шага, потом через 4 квадрата для n-1 вы получаете ответ для внутреннего квадрата еще через 2^(n-2) шагов.

    Вроде как на этих картинках цветные квадраты отмечены:

    9 квадратов 4x4. Их центральные 2x2 блоки составляют квадрат 6x6
    9 квадратов 4x4. Их центральные 2x2 блоки составляют квадрат 6x6
    4 квадрата 4x4. Их внутренние 2x2 блоки составляют квадрат 4x4
    4 квадрата 4x4. Их внутренние 2x2 блоки составляют квадрат 4x4

    Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4, из них собирать куски 2x2. Потом результаты записать в матрицу 3x3, там опять составить блоки 2x2, результат даст блок 2x2 который надо взять в ответ, составив из них квадро-дерево.

    Это сильно эффективнее вашего варианта со сторонами из степени 3. Тут надо всего 13=9+4 рекурсивных шагов, а не 83=49+25+9. Плюс нужно 2 последовательных шага эволюций, а не 3 как у вас, так что если параллелить, то там меньше зависимостей по вычислениям.

    С другой стороны, тут экспоненциальный рост идет с основанием 2, а не 3, так что высота рекурсивного дерева для заданного количества шагов будет выше в log_2(3) раз. Но каждая вершина будет в 6 раз менее ветвиста. Так что в целом количество возможных вершин гораздо меньше, ибо 13^log_2(3) = 58.28.. < 83.


    1. lightln2 Автор
      16.07.2026 20:33
      #30230294

      Это сильно эффективнее вашего варианта со сторонами из степени 3.

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

      Откуда вы вообще 3 взяли?

      Я делал оба варианта hashlife для версии клеточного автомата (не “жизнь”, но не принципиально), в которой много структур, симметричных относительно сдвига на 3^k клеток, но не на 2^k. Моя версия действительно была быстрее (в пять раз), но что я не ожидал, что реализация будет проще, чем квадродерево. К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

      Была еще и другая конфигурация, в которой симметрия была фрактальной со сдвигом 2^k. Ожидаемо, там стандартный hashlife работал за логарифм, а мой вариант вырождался в линию.

      У меня недостаточно данных, чтобы утверждать, какой из вариантов лучше на практике в среднем. Навскидку, вариант с квадродеревом требует меньше памяти, но вариант с 3x3-деревом легче написать и отладить.


      1. wataru
        16.07.2026 20:33
        #30231226

        К тому же, мне идея эволюции квадрата 3x3 кажется более естесственной, чем 4x4 - собственно, я и хотел этим поделиться.

        В целом согласен. С листом особенно просто получается.


        1. lightln2 Автор
          16.07.2026 20:33
          #30235410

          Я поразмышлял на досуге, тут вообще получается интересно.

          Рассмотрим обобщенный клеточный автомат, у которого состояние клетки зависит от целой окрестности p \times p, p = 3,5,7,… нечётно (в частном случае, может быть обычный автомат, в котором мы ходим сразу на (p-1)/2 шагов). Тогда тот же подход позволяет использовать p \times p-дерево, с листом 1 \times 1, и эволюцией поля в p-1 этапов

          p^2 \times p^2 \to (p^2 - (p-1)) \times (p^2 - (p-1)) \to (p^2 - 2(p-1)) \times (p^2 - 2(p-1)) \dots \to p \times p

          Тогда эволюция узла будет p^k \times p^k \to p^{k-1} \times p^{k-1} за p^{k-1} шагов.

          Но также мы можем поменять размер листа 1 \times 1 \to d \times d, тогда база эволюции будет (p-1+d) \times (p-1+d) \to d \times d. Если мы подберем d так, чтобы s = (p-1+d)/d было маленькое и целое, то мы можем сделать эволюцию в s \times s дереве, узла s^kd \times s^kd \to s^{k-1}d \times s^{k-1}d за s^{k-1} шагов. То есть, мы разменяли часло шагов на размер узла и сложность его эволюции.

          Альтернативно, мы можем сделать s степенью маленького целого, тогда можно уменьшить размер узла. Например, вместо 4 \times 4-дерева можно взять квадродерево, но в эволюции раскрывать не два уровня вложенности, а четыре. То есть, мы разменяли число шагов и сложность эволюции на размер узла.

          Например, возьмем p = 3 - стандартную окрестность. Тогда стандартная эволюция в 3 \times 3-дереве с листом 1 \times 1 - мой вариант, или, если возьмем d=2, s=(3-1+2)/2=2, будет эволюция в квадродереве с листом 2 \times 2 - классический hashlife!

          Если взять p = 5, то есть варианты:

          • 5 \times 5-дерево, лист 1 \times 1,

          • 3 \times 3-дерево, лист 2 \times 2,

          • квадродерево, лист 3 \times 3.

          Для p = 7 варианты:

          • 7 \times 7-дерево, лист 1 \times 1,

          • 4 \times 4-дерево, лист 2 \times 2 (можно использовать квадродерево, и раскрывать 4 уровня),

          • 3 \times 3-дерево, лист 3 \times 3,

          • квадродерево, лист 6 \times 6.

          В общем, в этом подходе, вариант 3 \times 3 (и p \times p в общем случае) является “естессвенным”, а hashlife получается как размен скорости эволюции на размер дерева и сложности шага эволюции. Было бы интересно провести анализ, но мне кажется, если все учесть, то асимптотически все варианты будут одинаковы.


          1. wataru
            16.07.2026 20:33
            #30235612

            Асимптотически там везде K^n для n шагов. К зависит от того, как выбирать дерево. Чем больше промежуточных шагов, тем больше K. Все они экспоненциальны, но асимптотически различимы.


    1. lightln2 Автор
      16.07.2026 20:33
      #30231036

      Как у вас, надо будет всех внуков корня квадро-дерева выписать в квадрат 4x4

      Я сделал аналогичный код для квадродерева, по сложности получается примерно таким же! Усложняется эволюция листа, но упрощается эволюция корня. На моем примере вариант с квадродеревом работает в три раза быстрее, но при этом количество обработанных узлов - в пять раз меньше (то есть, время обработки одного узла сильно хуже, по крайней мере, в данной реализации на питоне).

      hashlife3x3

      hashlife2x2

      Но все равно мне вариант с 3x3 кажется интуитивно более понятным.


      1. wataru
        16.07.2026 20:33
        #30231240

        Быстро вы сделали, мое уважение.

        при этом количество обработанных узлов - в пять раз меньше

        По моей интуиции и формуле выше, чем дальше эволюция, тем сильнее будет выигрывать квадродерево. В стандартной "жизни" нет особо пространственных симметрий и периодов размера ни степени 2 ни степени 3, поэтому оба варианта будут сравнимо выигрывать от повторений.


  1. wataru
    16.07.2026 20:33
    #30235666

    А вот такой вопрос возник, что вы по этому поводу думаете?

    Вот есть у нас поле, допустим оно все помещается в 3^k x 3^k. Допустим мы хотим получить все поле через 3^n шагов (n >> k). Вроде бы легко - расширяем поле с ранга k до ранга n+1 пустыми полями. Потом выполняем один шаг и получаем точный размер поля 3^n x 3^n.

    Но, скорость света в игре жизнь - 1. Через 3^n шагов изначальное поле 3^k x 3^k может расползтись до (3^n+3^k) x (3^n + 3^k), что больше поля 3^n x 3^n. Т.е. чтобы получить все поле надо будет сделать шаг параллельно на нескольких полях, так? Это очень похоже на первый шаг во время эволюции состояния.

    Похоже, у вас именно так и делается - вы там корень помещаете в центр массива 5x5. Это удобно делать когда дерево нечетное, с центром, как у вас 3x3.

    Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа.

    И оффтопик, я тут поэксперементировал и выяснил, что если добавить в мапу состояний 0: [0, 0, 0, ... 0] для обозначения пустого поля любого размера, то это упрощает код (не надо отдельного make_empty), и немного сокращает количество состояний. Только вместо проверки, что у вас лист 0 или 1 надо помнить какого размера текущее поле.


    1. lightln2 Автор
      16.07.2026 20:33
      #30235786

      Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа

      Тут я, похоже, ошибся: я хотел упростить, и корень s^k \times s^k увеличиваю дважды до s^{k+2}, и делаю ему evolve, и проблема в вашем агрументе про скорость света. Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов, поэтому в корне всегда достаточно пустого периметра. Но для произвольного автомата, вы правы, поле может разрастить быстрее.

      Поэтому, видимо, в общем случае надо делать последний этап в эволюции:

      • Для 3x3: 9x9 -> 7x7 -> 5x5 -> 3x3, нужен один этап 5x5 -> 3x3

      • для 2x2: 4x4 -> 3x3 -> 2x2, нужен один этап 3x3 -> 2x2

      • для p \times p: один этап 2p - 1 \times 2p - 1 \to p \times p

      то это упрощает код

      Интересно, я в этом направлении не думал. А у вас есть код посмотреть? Я пытался делать мапу 0 -> 0, 1 -> 1, там немного упрощается база рекурсии, но не сильно.


      1. wataru
        16.07.2026 20:33
        #30235812

        Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов,

        Нет же. Берем длинную палку длинной L шириной 1. За один шаг она станет очень длинной O. За следующий шаг появятся 2 вертикальные полосы еще правее и еще левее. В итоге через L шагов родятся клетки отстоящие на L шагов вправо и влево от центра палки (и что-то еще по середине).

        Скорость света - 1 клетка/шаг.

        поэтому в корне всегда достаточно пустого периметра.

        Да. Но только если каждый под-блок этого расширенного с периметром поля считать отдельно. Если бы скорость света действительно была 1/2 клеток/шаг, то не надо было бы и расширять. Вот в примере выше в поле уже по краям достаточно пустого места.

        Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

        Код я потом скину, еще не отдебажил.


        1. lightln2 Автор
          16.07.2026 20:33
          #30235946

          Берем длинную палку длинной L шириной 1

          да, вы правы.

          Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.

          вроде, не надо: для p^{k+1} \times p^{k+1} \to p^k \times p^k за k шагов скорость света (p-1)/2. Чтобы перейти p^k \to p^{k+1}, у нас есть периметр шириной (p^{k+1} - p^k) / 2 клеток, то есть, мы можем сделать \frac{ (p^{k+1} - p^k) / 2 } {(p-1)/2} = p^k шага, именно это и делается, если взять массив (2p-1) \times (2p-1), положить в центр узел p^k \times p^k и сделать один этап эволюции.


          1. wataru
            16.07.2026 20:33
            #30235958

            вроде, не надо

            Да, согласен.