Игра «Жизнь»

(Электронные таблицы: применяем с пользой; часть 11)

(описание используемых условных обозначений, а также список других публикаций канала по теме электронных таблиц, находится здесь).

Математик Джон Конвей известен как автор игры под названием «Жизнь». Данная игра его коллегами более точно классифицируется как «клеточный автомат» (математическая модель особого типа). Приведу здесь её довольно простые правила [1]:

Место действия этой игры – «вселенная» – это размеченная на клетки поверхность или плоскость – безграничная, ограниченная, или замкнутая (в пределе – бесконечная плоскость).

Каждая клетка на этой поверхности может находиться в двух состояниях: быть «живой» (заполненной) или быть «мёртвой» (пустой). Клетка имеет восемь соседей, окружающих её.

Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

- в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;

- если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»)

Игра прекращается, если

- на поле не останется ни одной «живой» клетки

- конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация)

- при очередном шаге ни одна из клеток не меняет своего состояния (складывается стабильная конфигурация; предыдущее правило, вырожденное до одного шага назад)

Игра известна довольно давно и посвящённые ей публикации помимо научной литературы имеются и в научно-популярной – например, журнал «Наука и жизнь» писал о ней неоднократно (там, правда, она именуется «Эволюцией» [2, 3, 4]), ну а количество материалов о «Жизни», которые можно отыскать в Интернете, вообще трудно поддаётся учёту.

Ниже предлагается создание программы для «Жизни» в среде табличного процессора, хотя в отношении данной реализации нужно заранее сделать акцент на следующих двух моментах:

1. Правила игры таковы, что возникают некоторые затруднения, если её поле («вселенная») имеет конечные размеры – непонятно, как применять правила в отношении клеток на границах. Для избежания подобных ситуаций «Жизнь» будет здесь реализована на развертке на плоскость поверхности тора – более подробно об этом рассказано ниже.

2. Я стараюсь, чтобы заметки в этой серии публикаций канала были не просто описанием хода решения каких-либо практических задач, но и чтобы они могли выполнять обучающую роль, позволяющую освоить различные возможности табличных процессоров. В более ранних материалах ещё ни разу не рассматривалось использование так называемых «именованных диапазонов» и, как мне кажется, именно сейчас предоставился хороший случай для рассказа об этом. Использование именованных диапазонов позволит сделать сами правила «Жизни» регулируемыми – процитированный выше «классический» их набор в предлагаемой реализации будет представлять лишь частный случай.

Вернёмся к упомянутой развёртке тора на плоскость. Рассмотрим размеченный на клеточки прямоугольник (а) – как нетрудно догадаться, внешне он очень похож на лист книги (файла электронной таблицы). Представим, что прямоугольник изготовлен из гибкого материала и свернём его в трубку, сомкнув края, помеченные малиновым цветом (б). Далее плавно изогнём получившуюся цилиндрическую поверхность так, чтобы сомкнулись её концы, расцвеченные красным – при этом образуется тор (в), также размеченный «в клеточку» (изображение тора я взял уже готовое, из соответствующей статьи Википедии [5], ведь художник из меня тот ещё – моих способностей хватило лишь на небольшую модификацию позаимствованной картинки под нужды настоящей заметки).

Легко видеть, что каждая клетка на такой поверхности обязательно имеет по 8 соседних и в этом случае правила «Жизни» не потребуют никаких дополнительных оговорок для тех, которые расположены с края прямоугольника. Обратите также внимание на метки A, B, C и D «угловых» клеток– они помогают лучше сориентироваться в их ближайшем окружении при замыкании «плоскости в бублик», скоро это тоже пригодится при написании формул.

Дополнительно введём следующую терминологию:

• минимальное количество живых соседей живой клетки, при которых она так и останется живой (и не умрёт «от одиночества») назовём «нижней границей выживаемости» (NGV) – в классическом наборе правил оно равно 2;
• максимальное количество живых соседей живой клетки, при которых она продолжит оставаться живой (не погибнет «от перенаселённости») назовём «верхней границей выживаемости» (VGV) – в классическом наборе правил оно равно 3;
• минимальное количество живых соседей мёртвой клетки, при которых в ней зародится жизнь, назовём «нижним пределом зарождения» (NPZ);
• максимальное количество живых соседей мёртвой клетки, при которых в ней зародится жизнь, назовём «верхним пределом зарождения» (VPZ). Таким образом в классическом наборе правил NPZ и VPZ одинаковы и равны 3;
• исходную конфигурацию клеток на поле будем здесь называть «нулевым поколением», а не «первым», чтобы подчеркнуть отличие стартовой конфигурации, задаваемой «вручную», от последующих, которые определяются далее правилами игры.

На основании приведённых сокращённых обозначений общий алгоритм «Жизни» для отдельно взятой клетки при переходе к каждому последующему поколению можно представить в следующем виде:

Создадим новую книгу, в которой один лист переименуем в “settings” («настройки») и оформим его так:

Теперь предстоит ячейкам присвоить собственные имена – создать именованные диапазоны.

Щёлкните правой кнопкой мыши по ячейке “B2” и в открывшемся контекстном меню выберите пункт «Присвоить имя...»:

Появится диалоговое окно «Создание имени» – введите в соответствующем поле имя “NGV”:

Выделите ячейку “B2”, после чего в программном меню выберите пункт «Лист» → «Именованные диапазоны и выражения» → «Задать...». Появится диалоговое окно «Задать имя» – введите в соответствующем поле имя “NGV”:

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

Действуя аналогично, присвойте имена “VGV”, “NPZ” и “VPZ” ячейкам “B4”, “B6” и “B8” соответственно. При необходимости можно посмотреть перечень всех поименованных диапазонов.

Этой цели служит диалоговое окно «Диспетчер имен», которое вызывается нажатием также называющейся кнопки в секции «Определенные имена» вкладки ленты «Формулы»:

Этой цели служит диалоговое окно «Управление именами», вызываемое через программное меню: «Лист» → «Именованные диапазоны и выражения» → «Управление...»

Первый подготовительный этап закончен. Далее предстоит ещё один, заключающийся в оформлении листа для «вселенной» в состоянии нулевого поколения – на его основе потом будет создаваться лист, показывающий последующее состояние в игре. Пусть размеры «вселенной» составят 50×100 клеточек, при этом «живой» клеткой будем считать ячейку, содержащую число 1, а «мёртвой» – пустую ячейку (её численное значение табличный процессор принимает равной нулю).

Создайте новый лист с именем“00i” и у столбцов “А”– “CX” (или вообще у всех столбцов листа) установите ширину, равную их высоте, после чего, воспользовавшись соответствующим инструментом в правой части строки состояния:

измените масштаб отображения листа так, чтобы диапазон ячеек “B2:CW51” (это как раз и есть те самые 50×100 клеточек) помещался в рабочем окне программы – именно этот диапазон и будет изображать собой «вселенную» игры.

В LibreOffice Calc масштаб отображения настраивается для всей книги в целом, поэтому подписи параметров игры в листе “settings” могут оказаться слишком мелкими. Чтобы сохранить удобочитаемость, просто увеличьте в ячейках этого листа кегль (размер) шрифта.

Теперь пора вспомнить, что «вселенная» игры является развёрткой «клетчатого» тора. Чтобы в пределах диапазона “B2:CW51” (клетках «вселенной») можно было обойтись по сути одной и той же формулой (которая, кстати, и так будет не самой короткой), в ячейках листа, непосредственно примыкающих к указанному блоку, продублируем содержимое граничных с “B2:CW51” ячеек:

1) В ячейку “B1” введём формулу:

=B51

Маркером заполнения её следует откопировать вправо, вплоть до “CW1”.

2) В “B52” нужно ввести

=B2

и размножить её вправо до “CW52” включительно.

3) Ввести в “A2” выражение

=CW2

и откопировать вниз, до “A51”.

4) В “CX2” ввести

=B2

Эту формулу необходимо будет размножить вниз до “CX51”.

5) Ещё остаются четыре «угловых» ячейки, формулы в которых должны быть такими:

Если всё сделать правильно, «вселенная» приобретёт окаймление из ноликов по своим краям. Чтобы дополнительно подчеркнуть границы «вселенной», в ячейках с нулями можно выполнить светло-серую заливку фона:

Для большей визуальной привлекательности лучше сделать так, чтобы «живая» клетка в игре выглядела чёрной. Проще всего этого добиться при помощи условного форматирования.

Выделите ячейку “B2”, после чего на вкладке ленты «Главная», в секции «Стили» выберите «Условное форматирование» → «Правила выделения ячеек» → «Равно»:

Появится диалоговое окно, в левом поле которого нужно будет ввести единицу, а в выпадающем списке справа выбрать пункт «Пользовательский формат...»:

При этом откроется ещё одно окно «Формат ячеек», в котором на вкладке «Заливка» нужно будет выбрать чёрный цвет:

Создайте стиль ячейки (Пособие, с. 35) с названием “alive-cell”

и при настройке его форматирования выберите чёрные шрифт

и заливку

Далее выделите ячейку “B2”, после чего через программное меню «Формат» → «Условное» → «Условие...» вызовите диалоговое окно, в котором нужно будет задать следующие настройки:

После настроек введите в “B2” число 1, чтобы убедиться в работоспособности заданного условного форматирования, а затем маркером заполнения размножьте это форматирование на весь диапазон “B2:CW51”.

Далее нужно создать копию листа “00i”. Делается это так. Выполните щелчок правой кнопкой мыши по ярлычку с именем листа.

В контекстном меню выберите пункт «Переместить или скопировать...»

Появится диалоговое окно, в котором в списке нужно будет выбрать «(переместить в конец)» и установить флажок «Создать копию»:

После нажатия кнопки «ОК» появится дубликат листа – переименуйте его в “01i”:

В контекстном меню выберите пункт «Переместить или скопировать...»

Появится диалоговое окно, в котором нужно будет поставить переключатель в положение «Копировать», выбрать « - переместить в конец - » в списке и в поле «Новое имя» ввести “01i”, после чего нажать кнопку «ОК»:

В получившемся листе должна отображаться конфигурация клеток на поле, следующая за нулевым поколением, для чего в его ячейки в диапазоне “B2:CW51” должны быть введены формулы, работающие в соответствии с алгоритмом, блок-схема которого была приведена выше. Строго говоря достаточно ввести нужную формулу в “B2”, а затем размножить её маркером заполнения. Выражение для неё довольно громоздкое, вот оно:

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

=ЕСЛИ('00i'!B2=1;ЕСЛИ(И(СУММ('00i'!A1:C1;'00i'!A2;'00i'!C2;'00i'!A3:C3)>=NGV;СУММ('00i'!A1:C1;'00i'!A2;'00i'!C2;'00i'!A3:C3)<=VGV);1;"");ЕСЛИ(И(СУММ('00i'!A1:C1;'00i'!A2;'00i'!C2;'00i'!A3:C3)>=NPZ;СУММ('00i'!A1:C1;'00i'!A2;'00i'!C2;'00i'!A3:C3)<=VPZ);1;""))

=IF($00i.B2=1;IF(AND(SUM($00i.A1:C1;$00i.A2;$00i.C2;$00i.A3:C3)>=NGV;SUM($00i.A1:C1;$00i.A2;$00i.C2;$00i.A3:C3)<=VGV);1;"");IF(AND(SUM($00i.A1:C1;$00i.A2;$00i.C2;$00i.A3:C3)>=NPZ;SUM($00i.A1:C1;$00i.A2;$00i.C2;$00i.A3:C3)<=VPZ);1;""))

Формула анализирует состояние аналогичной клетки нулевого поколения (лист “00i”): сначала проверяет, является ли она «живой»: если да (эта часть формулы набрана зелёным), то далее проверяется количество «живых» соседей на соответствие диапазону от NGV до VGV. В случае, если клетка «мертва» (набрано красным), то делается проверка на соответствие количества «живых» соседей диапазону от NPZ до VPZ. Подсчёт количества «живых» соседей в окрестности клетки выполняет выделенный в формуле жирным шрифтом фрагмент:

СУММ('00i'!A1:C1;'00i'!A2;'00i'!C2;'00i'!A3:C3)

SUM($00i.A1:C1;$00i.A2;$00i.C2;$00i.A3:C3)

В результате на листе “01i” отображается следующее за нулевым (то есть первое) поколение клеток игры. Разумеется, работу созданного клеточного автомата интереснее наблюдать, когда есть возможность посмотреть изменение конфигурации клеток в целом ряду поколений. Сделать это можно следующим образом.

Создайте копию листа “01i”, которой присвойте имя “02i” и сделайте данный лист активным:

На вкладке ленты «Главная» в секции «Редактирование» раскройте меню нажатием кнопки «Найти и выделить», в которой выберите пункт «Заменить...»:

Откроется диалоговое окно «Найти и заменить», в текстовых полях вкладки «Заменить» которого нужно задать замену символов "00i" на "01i". При этом нелишним будет дополнительно убедиться нажатием кнопки «Параметры >> », что искать указанные знаки табличный процессор должен только в пределах текущего листа:

В программном меню выберите «Правка» → «Найти и заменить...». Откроется диалоговое окно, в текстовых полях которого задать замену символов "00i" на "01i". При этом нелишним будет дополнительно убедиться, что флажок «Все листы» снят, чтобы табличный процессор искал заменяемые знаки только в пределах текущего листа:

После нажатия кнопки «Заменить все» формулы в “02i” станут ссылаться на ячейки листа “01i” и получится отображение ещё одного поколения «Жизни» (по завершении замен будет выдано диагностическое сообщение о проделанной работе).

При наличии возможности обзора трёх поколений клеток уже становятся наблюдаемыми некоторые типовые явления, характерные для «Жизни». Если в нулевом поколении задать три фигуры, изображённые ниже на рисунке, то первая из них неизбежно погибнет. Вторая фигура («палочка») являет пример самого простейшего «осциллятора» – периодически повторяющейся конфигурации клеток. Третья фигура («уголок») на следующем шаге достраивается до квадрата 2×2 – простейшей стабильной фигуры, которая не меняется при последующих ходах:

Далее можно создать копию листа “02i”, обозначив её как “03i”, где заменить в формулах символы "01i" на "02i" и т. д., насколько хватит терпения. У меня хватило до “10i” – в этом случае можно просматривать изменения конфигурации клеток в десяти поколениях, хотя иногда оказывается достаточно меньшего их количества. Например, для наблюдения движения «глайдера» (его ещё называют «планером») хватает поколений 0-4:

Важно отметить, что из-за довольно большого количества ячеек, содержащих длинные формулы, при подготовке отображения каждого нового поколения клеток табличный процессор может «подвисать».

Значительно чаще десяти поколений клеток всё равно оказывается недостаточно, чтобы достигнуть условия окончания игры. В этом случае можно поступить так: на листе последнего поколения выделить клетки «вселенной», скопировать их и выполнить специальную вставку одних только значений ячеек (Пособие, с. 52) в соответствующий диапазон листа “00i” – при этом в остальных листах формулы сработают по новой и в них отобразится последовательность ещё одного десятка поколений.

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

Ссылки:

1. Статья «Игра “Жизнь”» // RU.WIKIPEDIA.ORG: Википедия. Свободная энциклопедия. URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь» (дата обращения: 28.03.2022)
2. Заметка«“Эволюция”. Фантастическое богатство комбинаций новой игры» – Наука и жизнь, 1971, № 8, с. 130
3. Снитковский С. «Еще раз об “Эволюции”» – Наука и жизнь, 1972, № 8, с.141
4. Сидоров И. «Эволюция игры “Эволюция”» – Наука и жизнь, 1975, № 3, с.116
5. Статья «Тор (поверхность)» // RU.WIKIPEDIA.ORG: Википедия. Свободная энциклопедия. URL: https://ru.wikipedia.org/wiki/Тор_(поверхность) (дата обращения: 28.03.2022)

Файлы с примерами: xlsx / ods

Перечень публикаций на канале