Шестой раздел: Игра Жизни

Оригинал: Глава 6 Игра Жизни

Переводчик: Феликс Ли

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

В этом разделе мы рассмотрим двумерные клеточные автоматы, особенно игру "Жизнь" Джона Конвея (GoL). Как некоторые клеточные автоматы из предыдущего раздела, GoL следует простым правилам и демонстрирует удивительно сложное поведение. Подобно правилу 110 Уолффрама, было установлено, что GoL является универсальным; то есть, теоретически он может вычислять любую вычислимую функцию.

Сложное поведение GoL вызывает вопросы научной философии, особенно относящиеся к научному реализму и инструментализму. Я обсуждаю эти вопросы и даю рекомендации по дополнительному чтению.

В конце этого раздела я продемонстрирую, как эффективно реализовать GoL на Python.

Код этого раздела находится в файле chap06.ipynb в репозитории этой книги. Дополнительная информация о использовании кода представлена в разделе ?.

6.1 Игра Жизни Конвея

Один из первых исследованных клеточных автоматов, возможно, самый популярный среди них, это двухмерный клеточный автомат, известный как "игра 'жизнь'", сокращённо GoL. Он был разработан Джоном Х. Конвеем и популяризирован Мартином Гарднером в колонках журнала Scientific American в 1970 году. См. http://en.wikipedia.org/wiki/Conway_Game_of_Life.В GoL клетки располагаются на двумерной сетке, ограниченной с двух сторон или образующей тор. Бидirectional boundary grid называется тором, так как она эквивалентна поверхности тора в географическом плане. См. https://en.wikipedia.org/wiki/Torus.

Каждая клетка имеет два состояния — живое и мертвое — и восемь соседей — запад, восток, юг, север и четыре диагонали. Эти соседи иногда называют "моносферическим окружением".

Как и одномерные клеточные автоматы из предыдущих разделов, игра "жизнь" развивается согласно правилам, аналогичным простым законам физики.

В GoL следующее состояние каждой клетки зависит от её текущего состояния и количества активных соседей. Если клетка жива, она будет жить, если у неё два или три активных соседа, иначе она умрёт. Если клетка мертва, она останется мертвой, за исключением случая, когда у неё ровно три соседа.

Ниже приведена таблица, которая сводит эти правила:

Эта модель схожа с естественным клеточным делением: отдельные или пере飽和的状态下，细胞会死亡；它们在适度密集的情况下茁壮成长。

GoL受到了广泛的欢迎，原因如下：

В условиях пере飽和状态下，细胞会死亡；它们在适度密集的情况下茁壮成长。GoL受到了广泛欢迎的原因如下：- Она может создавать неожиданно сложное поведение из простых начальных условий.

• Существует множество интересных стабильных паттернов: некоторые колеблются взад-вперед (с различными периодами), а другие движутся аналогично космическим кораблям в правиле Wolfram CA Rule 110.
• Как правило 110, так и GoL являются Turing-complete.
• Еще одной причиной интереса является гипотеза Конвея — отсутствие начальных условий, при которых количество живых клеток может расти бесконечно, а также его предложение вознаграждения в размере 50 долларов за то, чтобы кто-то смог подтвердить или опровергнуть эту гипотезу.
• Наконец, с увеличением доступности компьютеров автоматизация вычислений и графическое представление результатов становятся все более легкими.### 6.2 Живые образцы

Рисунок 6.1: Стационарный образец, известный как "пчелиная сота" (beehive).

Рисунок 6.2: Осциллирующий образец, известный как "жаба" (toad).

Рисунок 6.3: Космический корабль, известный как "летающая лодка" (glider).

Если запустить GoL с случайной начальной конфигурацией, могут возникнуть различные стационарные образцы. Со временем эти образцы были определены и названы.

Например, Рисунок 6.1 показывает стационарный образец, называемый "пчелиная сота". В каждой клетке пчелиной соты есть два или три соседних клетки, поэтому они выживают; мертвые клетки рядом с пчелиной сотой не имеют трех живых соседей, поэтому новые клетки не рождаются.

Другие образцы осциллируют; то есть, они меняются со временем, но в конце концов возвращаются к своему начальному состоянию (при условии, что они не сталкиваются с другим образцом). Например, Рисунок 6.2 демонстрирует образец, называемый "жаба", который представляет собой осциллирующий образец, альтернирующий между двумя состояниями. Этот осциллирующий образец имеет период равный двум.

Наконец, некоторые образцы осциллируют и возвращаются к своему начальному состоянию, но при этом перемещаются в пространстве. Поскольку эти образцы кажутся движущимися, их называют "космическими кораблями".Рисунок 6.4 демонстрирует космический корабль, известный как "летающая лодка". После четырёх шагов летающая лодка возвращается в своё начальное положение, перемещаясь вниз и вправо на одну единицу.

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

Люди потратили много времени на поиск и название этих образцов. Если вы проведёте поиск в интернете, вы найдёте множество коллекций таких образцов.

6.3 Гипотеза Конвея

Конвей высказал гипотезу, согласно которой нет начального условия, которое бы привело к бесконечному увеличению количества живых клеток. Он также предложил награду в размере 50 долларов США за доказательство или опровержение этой гипотезы. На основе начальных условий, GoL быстро достигает устойчивого состояния, количество живых клеток практически не меняется (возможно, с небольшими колебаниями).

Рисунок 6.4: Начальное и конечное состояние r-пентамино

Однако некоторые простые начальные условия требуют очень долгого времени для достижения устойчивости и могут привести к удивительному количеству живых клеток. Эти паттерны называются "Метушелеями", так как они имеют длительный срок жизни.Среди них самым простым является r-пентамино, который состоит всего из пяти клеток, имеющей форму, приближенную к букве "r". Рисунок ? показывает начальное состояние r-пентамино и его конечное состояние после 1103 шагов.

Это состояние считается "конечным", поскольку все оставшиеся паттерны являются устойчивыми, колеблющимися или летящими, и никогда не будут конфликтовать друг с другом. R-пентамино в общей сложности производит 6 летающих, 8 блоков, 4 бликера, 4 соты, 1 маленькую лодку, 1 корабль и 1 хлеб.

Рисунок 6.5: Гангрелевская пушка летающих, которая производит поток летающих.

Существование долгоживущих паттернов заставляет Конвей сомневаться в том, существуют ли начальные условия, которые никогда не становятся устойчивыми. Он полагал, что нет таких условий, но описал два типа паттернов, которые могли бы доказать обратное — "пушку" и "пароход". Пушка представляет собой устойчивый паттерн, регулярно производящий летающие; благодаря этому поток летающих увеличивает количество живых клеток бесконечно. Пароход представляет собой движущийся паттерн, который оставляет след из живых клеток.

Как выяснилось, оба эти типа действительно существуют. Группой под руководством Билла Гангла был найден первый пример, известный как Гангрелева пушка летающих, показанная на рисунке. Ганг также нашёл первый пароход.Оба этих типа имеют множество вариантов, однако их сложно спроектировать или найти. Это не случайность. Конвей выбрал правила GoL таким образом, чтобы его гипотеза не была очевидна ни как правдоподобная, ни как ложная. Из всех возможных правил двумерных клеточных автоматов большинство из них порождает простое поведение: большинство начальных условий быстро достигают устойчивости или бесконечного роста. Уклоняясь от скучных клеточных автоматов, Конвей также избегает первых двух типов поведения Вулффрама и возможно третьего.

Если мы верим в принцип вычислительной эквивалентности Вулффрама, то мы можем ожидать, что GoL будет относиться к четвертому типу, и это так. Жизнь игра была доказана в 1982 году своей универсальностью Тьюринга (в Yöz 1983 года было независимое доказательство). С тех пор несколько людей создали паттерны GoL, реализующие машины Тьюринга или другие известные машины Тьюринга. ## 6.4 РеализмУстойчивые конфигурации в игре «жизнь» трудно не заметить, особенно те, что движутся. Признание их как постоянных сущностей естественно, но помните, что CA состоит из клеток; нет лягушек или хлеба. Глиссеры и другие корабли ещё менее реальны, так как со временем они даже не состоят из одних и тех же клеток. Так что эти паттерны похожи на звездные созвездия. Мы видим их таким образом, потому что мы способны замечать образцы или потому что у нас активное воображение, но они не являются реальными.Но это не совсем так. Многие сущности, которые мы считаем "реальными", также являются устойчивыми образцами меньших сущностей. Ураганы — это просто модели воздушных потоков, но мы придумываем им личные названия. А люди, как глиссеры, не состоят из одних и тех же клеток со временем. Но даже если вы замените каждую клетку вашего организма, мы всё ещё будем считать вас одним и тем же человеком.

Это не новое наблюдение — примерно за 2500 лет назад Гераклит отметил, что вы не можете дважды войти в одну и ту же реку — но сущности, возникающие в игре «жизнь», служат практическими тестовыми случаями для философского реализма.

В контексте философии реализм представляет собой взгляд, согласно которому сущности мира существуют независимо от человеческого восприятия и понятий. «Восприятие» относится к информации, которую мы получаем через наши чувства, а «понятие» — к нашему умному представлению о мире. Например, наш зрительный аппарат воспринимает некоторые вещи как двумерные проекции сцен, а мозг использует эту картину для создания трёхмерной модели объектов в этих сценах.Научный реализм связан с научными теориями и сущностями, которые они предполагают. Если теория использует свойства и поведение сущностей для своего выражения, то эта теория предполагает существование такой сущности. Например, теории электромагнетизма используют электрические и магнитные поля. Некоторые экономические теории используют предложения, спрос и рыночные силы. Теории биологии используют гены.Но являются ли эти сущности реальными? То есть, существуют ли они независимо от нас и наших теорий?

Ещё раз, я считаю полезным формулировать философские позиции в ряду различных степеней силы; вот четыре заявления научного реализма, усиленные по мере продвижения:

SR1:

Для того, насколько они приближаются к истине, научные теории могут быть истинными или ложными, но ни одна теория не является полностью правильной. Некоторые предполагаемые сущности могут быть реальными, но нет принципиального способа сказать, какие именно.## 6.5 Инструментализм

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

Чтобы понять, удовлетворяет ли вас инструментализм, рассмотрите следующие утверждения:

"Элементы игры 'Жизнь' не являются реальными; они просто милые названия для паттернов клеток."

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

"Мы считаем, что многие объекты в мире представляют собой произвольные наборы, подобные звездным созвездиям. Например, грибы — это вторичные органы плесени, большая часть которой находится под землёй и представляет собой почти непрерывную сеть клеток. Мы сосредоточены на грибах из практических соображений, таких как видимость и привлекательность."

"Некоторые объекты имеют чёткие границы, но многие имеют смазанные границы. Например, какие молекулы являются частью вашего тела: воздух в ваших лёгких? Еда в вашем желудке? Нутриенты в вашей крови? Внутренние части клеток? Вода в клетках? Структурные части клеток? Волосы? Омертвевшая кожа? Грязь? Бактерии на вашей коже? Бактерии в вашем кишечнике? Митохондрии? Когда вы взвешиваетесь, сколько из этих молекул включено в ваш вес? Представление мира через отдельные объекты полезно, но определённые сущности не являются реальными." За каждое согласие с утверждением начисляется один балл. Если ваш балл превышает 4, вы можете являться инструменталистом!Если вы предпочли бы эти утверждения по сравнению с другими, спросите себя почему. Какие различия в этих ситуациях могут повлиять на ваши ответы? Можете ли вы сделать принципиальное различие между ними?

Дополнительную информацию об инструментализме можно найти по адресу https://ru.wikipedia.org/wiki/Инструментализм.

6.6 Реализация

Заключительное упражнение этой главы требует попробовать и модифицировать игру Жизнь и реализовать другие двумерные клеточные автоматы. В этом разделе рассматривается реализация игры Жизни, которую вы можете использовать как отправную точку для экспериментов.

Для представления состояния клеток используется массив NumPy типа uint8, что представляет собой 8-битное беззнаковое целое число. Например, следующий код создаёт 10x10 массив и случайным образом заполняет его значениями 0 и 1:

a = np.random.randint(2, size=(10, 10)).astype(np.uint8)

Можно рассчитывать правила игры Жизни несколькими способами. Самый простой метод — это использование цикла for для прохода по строкам и столбцам массива:

b = np.zeros_like(a)
rows, cols = a.shape
for i in range(1, rows-1):
    for j in range(1, cols-1):
        state = a[i, j]
        neighbors = a[i-1:i+2, j-1:j+2]
        k = np.sum(neighbors) - state
        if state:
            if k == 2 or k == 3:
                b[i, j] = 1
        else:
            if k == 3:
                b[i, j] = 1
```Начально, `b` является нулевым массивом такого же размера, как `a`. В каждом цикле состояние центральной клетки определяется условием `state`, а соседи представляют собой окрестность `3x3`. `k` представляет количество активных соседей (не считая центральной клетки). Вложенные условия `if` оценивают правила игры "Жизни" и активируют соответствующие клетки в массиве `b`.Эта реализация является прямым переводом правил, но она длинная и медленная. Мы можем использовать корреляцию для лучшего выполнения, как мы видели в разделе ??. Там мы использовали `np.correlate` для вычисления одномерной корреляции. Теперь, чтобы вычислить двухмерную корреляцию, будем использовать `correlate2d` из модуля `scipy.signal`, который предоставляет функции для вычисления корреляций сигналов:

```py
from scipy.signal import correlate2d

kernel = np.array([[1, 1, 1],
                   [1, 0, 1],
                   [1, 1, 1]])

c = correlate2d(a, kernel, mode='same')

В контексте одномерной корреляции содержимое "окна" называется "ядром", но идея та же: correlate2d перемножает ядро и массив, выбирая окрестность, затем суммирует результат. Это позволяет ядру выбрать 8 соседних клеток вокруг центральной. correlate2d применяет ядро ко всем позициям в массиве. При использовании mode='same' результат имеет ту же размерность, что и массив a.

Теперь мы можем использовать логические операторы для вычисления правила:

b = (c == 3) | ((c == 2) & a)
b = b.astype(np.uint8)

Первая строка вычисляет булевый массив, где значения True указывают на живые клетки, а остальные — на мертвые. Затем метод astype преобразует булевый массив в целочисленный.

Этот вариант работает быстрее, возможно, достаточно хорошо, но его можно ещё упростить, модифицировав ядро:```py kernel = np.array([[1, 1, 1], [1, 10, 1], [1, 1, 1]])

c = correlate2d(a, kernel, mode='same') b = (c == 3) | (c == 12) | (c == 13) b = b.astype(np.uint8)

В данном случае ядро включает центральную ячейку с весом 10. Если центральная ячейка равна нулю, то результат будет находиться в диапазоне от 0 до 8; если она равна единице, то результат будет находиться в диапазоне от 10 до 18. Используя это ядро, можно упростить логическое правило, выбрав только те значения, которые равны 3, 12 и 13.

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

```py
table = np.zeros(20, dtype=np.uint8)
table[[3, 12, 13]] = 1
c = correlate2d(a, kernel, mode='same')
b = table[c]

Кроме значений 3, 12 и 13, все остальные значения в таблице равны нулю. Когда мы используем c как индекс для таблицы, NumPy выполняет поэлементный поиск; то есть, он берёт каждый элемент из c, находит его значение в таблице и помещает результат в b.

Этот вариант работает быстрее и проще, единственным недостатком является необходимость более подробного объяснения.

Файл Life.py, содержащийся в репозитории книги, предоставляет класс Life, который представляет реализацию правила. Если вы запустите Life.py, вы должны видеть анимацию "паровозика", которая является типом корабля, оставляющего за собой след из отбросов.

Упражнение 1

Код текущего раздела находится в Jupyter-ноутбуке `chap06.ipynb`, расположенном в репозитории книги. Откройте этот ноутбук, прочитайте код и выполните ячейки. Вы можете использовать этот ноутбук для практики упражнений текущего раздела. Мои решения находятся в `chap06soln.ipynb`.

Упражнение 2

Запустите игру Жизнь с случайным состоянием и запустите её до стабилизации. Какие стабильные формы вы сможете распознать?

Упражнение 3

Многие известные формы представлены в портативном формате файла. Измените `Life.py`, чтобы он мог парсить один из этих форматов и инициализировать сетку.

Упражнение 4

Одним из самых долгоживущих малых паттернов является "Зайцы", который начинается с 9 активных клеток и требует 17 331 шага для достижения стабильного состояния. Вы можете получить начальное состояние в различных форматах по адресу <http://www.conwaylife.com/wiki/Rabbits>. Загрузите это состояние и запустите его.

Упражнение 5

В моей реализации класс `Life` основан на родительском классе `Cell2D`, а класс `LifeViewer` основан на классе `Cell2DViewer`. Вы можете использовать эти базовые классы для реализации других двумерных автоматических клеточных машин.

Например, одна вариация игры Жизнь называется "Высшая жизнь" (Highlife) и имеет те же правила, что и игра Жизнь, но также включает правило: мёртвые клетки, имеющие 6 соседей, становятся живыми.Создайте класс `Highlife`, который наследуется от `Cell2D` и реализует этот вариант правил. Также создайте класс `HighlifeViewer`, который наследуется от `Cell2DViewer` и попробуйте представить результаты различными способами. В качестве простого примера используйте различные цветовые таблицы.

Один из более интересных паттернов в Highlife — это репликатор (replicator). Используйте метод `add_cells` и инициализируйте `Highlife` репликатором, чтобы посмотреть, что он делает.

Упражнение 6

Если расширить машины Тьюринга до двухмерной плоскости или добавить голову чтения/записи к двумерной АКМ, то результат будет являться двумерной автоматической клеточной машиной, известной как турмит (Turmite). Из-за того, как движется голова чтения/записи, её называют так, как будто бы это муравьи (termite), хотя ошибочное написание является данью уважения Аллану Тьюрингу.

Наиболее известным турмитом является муравей Лэнгтона (Langton's Ant), найденный Крисом Лэнгтоном в 1986 году. Подробнее см. <http://en.wikipedia.org/wiki/Langtons_ant>.

Муравей представляет собой голову чтения/записи со четырьмя состояниями, которую можно рассматривать как ориентированную на восток, запад, юг или север. Клетки имеют два состояния: черный и белый.Правила очень просты. На каждом временноm шаге муравей проверяет цвет клетки, на которой находится. Если клетка чёрная, муравей поворачивает направо, меняет цвет клетки на белый и передвигается на одну клетку вперёд. Если клетка белая, муравей поворачивает налевo, меняет цвет клетки на чёрный и затем передвигается вперёд.При наличии простого мира, набора простых правил и одного единственного перемещаемого объекта вы могли бы ожидать увидеть простое поведение, но теперь вам следует знать лучше. Начиная с полностью белых клеток, муравей Лэнгтона перемещается случайным образом более чем за 10 000 шагов, прежде чем войти в цикл продолжительностью 104 шага. После каждого цикла муравей перемещается по диагонали, оставляя след, известный как "скоростная дорога".

Реализуйте муравья Лэнгтона.