Идея клеточного автомата

Представьте поле из клеток, у каждой — простое состояние и одно правило «посмотри на соседей». Никакого центрального начальника, никакого плана. И всё же из этой скуки рождаются движущиеся фигуры, фракталы и волны. Это и есть клеточный автомат.

Клеточный автомат — это сетка (1D, 2D или больше) из клеток, каждая клетка имеет состояние из конечного набора, и на каждом шаге времени состояние клетки пересчитывается по одному и тому же локальному правилу, зависящему только от состояний клетки и её соседей.

Слово «локальное» здесь — главное. Клетка не видит всю сетку. Она знает только себя и ближайшее окружение. И тем не менее, когда тысячи клеток применяют одно и то же крошечное правило одновременно, на уровне всей сетки возникает поведение, которого в самом правиле «не написано». Этот разрыв между простотой правила и сложностью результата называют эмерджентностью.

Зачем это нужно? Клеточные автоматы — это минимальная модель того, как устроены многие реальные системы: распространение огня и эпидемий, рост кристаллов, узоры на раковинах моллюсков, поведение толпы. Везде, где есть много одинаковых элементов с локальными взаимодействиями, автомат даёт честную и понятную модель. А ещё это идеальный учебный пример: на нём видно, что «сложное» не обязано иметь «сложную причину».

Из чего собран автомат

Чтобы задать клеточный автомат, нужно определить четыре вещи:

• Сетка — геометрия клеток. Линия (1D), плоскость (2D), иногда тор (края склеены).
• Множество состояний — что может быть в клетке. В простейшем случае это 0 и 1 («мертва/жива»), но бывает и больше: «пусто/дерево/горит».
• Окрестность — какие соседи влияют на клетку.
• Правило перехода — функция, которая по состояниям клетки и её соседей выдаёт новое состояние.

Окрестность: фон Нейман и Мур

Две классические окрестности на 2D-сетке отличаются тем, считаем ли мы диагонали соседями.

Окрестность фон Неймана — это 4 соседа по сторонам (сверху, снизу, слева, справа):

. X .
X O X
. X .

Окрестность Мура — это 8 соседей, включая 4 диагональных:

X X X
X O X
X X X

Здесь O — сама клетка, X — её соседи. Выбор окрестности — часть правила: Игра «Жизнь» (следующий урок) использует окрестность Мура, а лесной пожар — обычно фон Неймана.

Самый простой случай: элементарный 1D-автомат

Прежде чем браться за плоскость, полезно понять одномерный автомат. Сетка — это просто строка из нулей и единиц. Окрестность клетки — она сама и два соседа (слева и справа), всего 3 клетки. Правило по трём двоичным соседям — это таблица из 8 строк (потому что троек из 0 и 1 ровно 2 ** 3 = 8), и для каждой тройки правило говорит новое состояние. Таких правил всего 2 ** 8 = 256 штук, и Стивен Вольфрам пронумеровал их от 0 до 255.

Возьмём знаменитое Rule 90. Его правило формулируется одной строчкой: новое состояние клетки — это XOR (исключающее ИЛИ) её левого и правого соседа. Сама клетка на результат не влияет. Края строки считаем нулями.

def rule90(width, steps):
    row = [0] * width
    row[width // 2] = 1
    rows = [row]
    for _ in range(steps):
        new = [0] * width
        for i in range(width):
            left = rows[-1][i - 1] if i > 0 else 0
            right = rows[-1][i + 1] if i < width - 1 else 0
            new[i] = left ^ right
        rows.append(new)
    return rows

for row in rule90(17, 3):
    print(''.join('#' if c else '.' for c in row))

Вывод:

........#........
.......#.#.......
......#...#......
.....#.#.#.#.....

Прочитаем вывод как историю во времени: верхняя строка — нулевой шаг, ниже — следующие. На нулевом шаге горит одна центральная клетка. XOR соседей зажигает по бокам от неё две клетки (левый сосед центра видит справа единицу, правый — слева единицу), а сам центр гаснет, потому что оба его соседа — нули. Дальше узор раздваивается снова и снова. Если прогнать rule90(33, 16), на экране проступит треугольник Серпинского — классический фрактал. Вот это и есть эмерджентность во всей красе: в правиле написано лишь «XOR двух соседей», а на сетке вырастает фрактальная структура, про которую в правиле нет ни слова.

Как работает под капотом

Ключевая деталь любого клеточного автомата — синхронность. Все клетки обновляются одновременно, на основе одного и того же «снимка» прошлого шага. Поэтому в коде нельзя писать новое состояние прямо в текущую сетку: тогда клетка, которую мы уже обновили, испортит расчёт для своего соседа. Правильный приём — завести отдельный массив new и заполнять его, читая только из старого.

В коде выше это видно: внутри цикла мы читаем rows[-1] (последний, уже готовый ряд) и пишем в свежий список new. Старый ряд во время вычисления не меняется. Затем new целиком добавляется в историю.

Второй тонкий момент — границы. У крайних клеток нет одного из соседей. Здесь мы выбрали политику «за краем всё ноль»: left для нулевой клетки равен 0, right для последней — тоже 0. Это видно в условиях if i > 0 и if i < width - 1. Другой популярный вариант — замкнуть строку в кольцо (тор), тогда сосед последней клетки — первая. Политика границ — часть определения автомата, и она реально меняет результат у краёв.

Частые ошибки

• Обновление «на месте». Если писать новое состояние в ту же сетку, из которой читаете соседей, шаг получится несинхронным и неправильным. Всегда нужен отдельный буфер new.
• Забытые границы. Обращение к row[i + 1] для последней клетки вызовет либо ошибку, либо (в Python) «заворот» на row[-1], то есть тихо неверный результат. Границы надо обрабатывать явно.
• Путаница окрестностей. 4 соседа (фон Нейман) и 8 соседей (Мур) дают принципиально разные автоматы. Перед кодом всегда уточняйте, считаются ли диагонали.
• «Сложный результат требует сложного правила». Это интуитивная, но ложная мысль. Rule 90 — это буквально один XOR, а рисует фрактал.

Итоги

• Клеточный автомат — это сетка клеток с состояниями, общее локальное правило и понятие соседства.
• Новое состояние клетки зависит только от неё самой и соседей; глобального плана нет.
• Из простых локальных правил возникает сложное глобальное поведение — это эмерджентность.
• Окрестность фон Неймана — 4 соседа по сторонам, окрестность Мура — 8 соседей с диагоналями.
• Элементарный 1D-автомат (правило по 3 соседям) — простейший пример; Rule 90 (XOR соседей) строит треугольник Серпинского.
• Обновлять клетки нужно синхронно, через отдельный буфер, и аккуратно задавать политику границ.