Первоначально опубликовано на http://thescinder.com 16 февраля 2021 г. Друзья могут прочитать эту статью здесь: https://bit.ly/carle_2.

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

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

Фиат Сетка

Пусть это будет великолепная вселенная.

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

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

Это лучше, теперь у нас есть одна клетка в состоянии 1, в просторечии известном как «живая» в сообществе клеточных автоматов, похожих на жизнь. Теперь пришло время дать определение физике. Они определят максимальную скорость, с которой информация может распространяться по нашей Вселенной, известную как скорость света, а также универсальную динамику. Мы начнем с определения того, какие клетки могут взаимодействовать друг с другом в данной области, определяя местоположение нашей вселенной. Мы определяем это, выбирая район, а наш выбор района, в свою очередь, определяет скорость света в нашей Вселенной. Для похожих на жизнь автоматов мы будем использовать окрестности Мура. Это означает, что на каждую ячейку могут влиять только ее соседние соседи.

Теперь давайте выберем наш набор правил. В этом примере мы начнем с «Игры жизни» Джона Конвея. Правила Жизни гласят, что любая пустая клетка, имеющая ровно трех живых соседей, станет живой, и любая живая клетка, имеющая 2 или 3 соседей, останется живой. Все остальные клетки переходят или остаются в состоянии 0, которое также в просторечии называется «мертвым». В обозначениях, используемых для клеточных автоматов, похожих на живые, это записывается как B3/S23, и на случай, если вы пролистываете это эссе с предельной скоростью, правила снова вызываются в пунктах списка ниже.

При каждом обновлении:

  • Мертвые клетки с ровно 3 живыми клетками в их окрестности Мура идут от 0 до 1.
  • Живые ячейки с 2 или 3 живыми ячейками в их окрестности Мура остаются в состоянии 1.
  • Все остальные ячейки исчезают или остаются пустыми.

Теперь, если мы обратимся к нашей вселенной с одним живым состоянием, мы заметим, что у единственной живой клетки в нашей вселенной ровно 0 соседей. Это не соответствует критериям выживания, поэтому мы помечаем эту ячейку перехода от 1 к 0 грязной копейкой.

После обновления сетка снова становится пустой, и, поскольку ячейка не может перейти от 0 к 1 без соседей, она остается такой.

Рассмотрим немного более интересный узор.

С 3 живыми ячейками нам нужно вычислить больше окрестностей Мура (хе-хе). Мы начнем слева направо.

В крайнем левом столбце и на одну клетку левее нет районов, содержащих ровно 3 клетки, поэтому рождений не будет. Однако самая левая живая ячейка имеет только 1 живого соседа, поэтому нам нужно пометить ее для удаления. Обратите внимание, что самая правая живая ячейка все еще там, но она не является частью этого соседства. Мы меняем ячейки только потом, после того, как прикинем все изменения, которые нам нужно внести в следующем обновлении.

Мы следуем тому же процессу справа и отмечаем эту ячейку для перехода в мертвое состояние.

Теперь мы можем рассмотреть центральную колонку.

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

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

Но мигалка периода 2 далека от более интересных машин, которые мы можем построить в жизни. Жизненные правила облегчают стационарные, мобильные и генеративные машины, и они могут стать довольно сложными. Давайте взглянем на простейший мобильный образец, 5-планер.

Удалив карточку соседства Мура и ускорив процесс обновления, мы начнем видеть, как шаблон перемещается по вселенной.

Теперь, если мы пройдем тот же процесс обновления, но на этот раз удалив маркеры обновления:

В Life было изобретено/открыто множество разнообразных космических кораблей и других машин. Еще один легкий космический корабль, лишь немногим более сложный, чем 5-планер, выглядит крошечной уткой:

Замечательная вещь в жизни — это сложность, которая может возникнуть из простого набора правил. С определением местоположения через окрестности ячеек и короткой строкой (B3/S23), описывающей обновления ячеек на каждом временном шаге, возможно огромное количество машин. На самом деле, в Life можно даже построить универсальный компьютер, который в принципе можно использовать для запуска симуляций игры Джона Конвея Жизнь. Просто следуйте простому двухэтапному процессу создания машины Тьюринга Пола Ренделла, и вы мгновенно освоите вычисления!

Я использовал программное обеспечение клеточных автоматов Golly, чтобы сделать рисунок выше (щелкните, чтобы увидеть версию с более высоким разрешением), и я признаю, что машина Тьюринга действительно доступна в программном обеспечении в качестве примера. Но для тех, кто ищет дополнительные задачи, ничто не мешает вам построить полную машину на физической сетке и обновить ее монетами или камнями.

Итак, Жизнь — это всего лишь одна вселенная, и существует более 260 000 наборов правил только для подмножества клеточных автоматов, которые похожи на жизнь, т.е. которые подвергаются обновлениям B/S в соответствии с количеством соседей в окрестности Мура каждой ячейки. Мы рассмотрим некоторые другие наборы правил и машины, которые можно с их помощью построить, в следующих постах.

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