Игры, Познавательно → Математическая игра “Жизнь”

«Жизнь». -одна из самых популярных математических игр столетия. Эта игра, представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Scientific American М.Гарднером, стала пользоваться большой известностью во всем мире. Игра "Жизнь", изобретенная Дж. Конвеем, описывает популяцию стилизованных организмов, развивающуюся во времени под действием противоборствующих тенденций размножения и вымирания.

Правила:

Правила игры Конвея «Жизнь»

Действие игры происходит на некой плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (окрестность Мура). Каждая клетка может находиться в двух состояниях - живом или мертвом, т. е. пустом. На состояние любой клетки оказывают влияние состояние соседних клеток. Во времени эти состояния дискретно в соответствии с некоторыми правилами или ГЕНЕТИЧЕСКИМИ ЗАКОНАМИ КОНВЕЯ, состоящими из 2 пунктов:

1) ВЫЖИВАНИЕ ИЛИ ГИБЕЛЬ.Если живая клетка имеет меньше 2 или более 3 соседей в окрестности из 8 клеток то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает;

2) РОЖДЕНИЕ. В пустой клетке появляется живая клетка, если у исходной клетки ровно 3 соседа.

Гибель и рождение всех организмов происходит одновременно.

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

Игра "Жизнь" относится к категории так называемых моделирующих игр - игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни.

Основная идея игры состоит в том, чтобы, начав с какого нибудь простого расположения живых клеток, проследить за эволюцией исходной позиции под действием упоминавшихся ГЕНЕТИЧЕСКИХ ЗАКОНОВ КОНВЕЯ, которые управляют рождением, гибелью и выживанием клеток. ГЕНЕТИЧЕСКИЕ ЗАКОНЫ КОНВЕЯ удовлетворяют трем основным условиям:

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

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

3) должны существовать простые начальные конфигурации, которые в течении значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих трех способов:

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

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

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

ПРОГРАММЫ ДЛЯ PC

life32

Cамая популярная программа для "Жизни" в мире

Текущая версия: 1.11 от апреля 1999 г.

Самая быстродействующая из всех аналогичных программ. Бесконечное поле (1 млн.х1 млн.) Огромное количество опций, включая изменение правил. Использует DirectX. Поддерживает множество форматов .lif-файлов, в т.ч. и юниксовые (XLife). К сожалению авторы программы прекратили ее разработку 3 года назад.

mcell420

Самая навороченная программа

Текущая версия: 4.2 от сентября 2001 г.

Полное название - Mirek's Cellebration. Мириады функций. Даже краткое описание основных функций займет очень много места. Вследствие своей навороченности, программа не очень быстрая. В ней есть все, и огромное количество лишнего, но это, бесспорно, лучшая программа в мире.

fam life

Программа FAM Life - одна из лучших российских программ для игры в "Жизнь".

Текущая версия: 3.5 от августа 2001 г.

К достоинствам программы относятся:

• двуязычный интерфейс (русский и английский) и справка с полным описанием всех правил Жизни на 2-х языках,
• возможность изменять правила эволюции и создавать свои правила,
• корректная реализация эволюции клеток по краям игрового поля,
• наличие встроенных стандартных фигур и возможность их вставки на игровое поле,
• множество возможностей настройки интерфейса, наличие готовых палитр оформления (океан, классика, небесный, кровавый и т. д.),
• возможность сохранения и загрузки конфигураций клеток в файлы формата .lif - собственный формат программы,
• использование DirectX для улучшения быстродействия.

life 3D

Программа Life 3D - трехмерная версия математической игры "Жизнь".

Текущая версия: 1.0 от декабря 2001 г.

Лучшая 3D версия "Жизни", которую я когда-либо видел. Использует OpenGL. Содержит множество настроек.

winlife

Неплохая, но достаточно старая (95 г.) программа.

Текущая версия: 1.0 от февраля 1995 г.

По возможностям немного уступает Life32. Понимает только свой формат файлов.

gllife

Игра "Жизнь" на OpenGL

Текущая версия: 1.0 от марта 2000 г.

Требует хорошую видеокарту, совместимую с OpenGL. Тестировалась разработчиком на NVidia TNT, GeForce, GeForce 2 и SGI 320.

Life screensaver

Хранитель экрана для Windows, представляющий собой реализацию "Жизни" Конвея.

Статьи

НАУКА И "ЖИЗНЬ"

Клеточные автоматы и игра «Жизнь»

Игра Конвея "Жизнь" - типичный пример клеточного автомата, как математического объекта, представляющего собой дискретную динамическую систему. По существу клеточные автоматы являются синтетическими мирами, поведение которых большей частью определяется простыми локально действующими правилами. В этих мирах пространство представляет собой равномерную сетку, каждая ячейка которой (клетка) содержит информацию о своем состоянии. Время - дискретно. Законы такого мира представляют собой небольшое количество правил, основные из которых описываются таблицей переходов, по которой клетка вычисляет свое новое состояние на каждом такте (минимальный отрезок времени) на основе своего состояния и состояний ее соседей.

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

Хорошим примером для ознакомления с принципами работы клеточного автомата является игра Джона Конвея "Жизнь". Индивидуум этой популяции представлен клеткой в состоянии 1, в то время как клетка в состоянии 0 представляет пустое пространство (для образности можно говорить о "живых" и "мертвых" клетках). Мерой течения времени служит смена поколений колонии, которая происходит по известным правилам.

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

На основе этого примера можно сформулировать общие правила построения клеточных автоматов:

1. Состояние клеток дискретно (обычно 0 и 1, хотя могут быть автоматы и с большим числом состояний).
2. Соседями являются ограниченное число клеток, часто это ближайшие клетки.
3. Правила, задающие динамику развития клеточного автомата, обычно имеют простую функциональную форму и зависят от решаемой проблемы.
4. Клеточный автомат является тактируемой системой, т.е. смена состояний клеток происходит одновременно.
5. Клеточные автоматы предоставляют большую свободу в выборе структуры и правил развития системы. Это позволяет моделировать на их основе или решать с их помощью самые разнообразные задачи.

Клеточные автоматы широко применяются для моделирования систем, для которых существенно пространственное взаимодействие между элементами системы. Существует много примеров таких моделей в биологии, информатике (включая системы телекоммуникации) и др. областях. В физике клеточные автоматы примененяются для анализа явлений переноса (теплопроводности, диффузии и вязкости), моделирования твердого тела.

Игра "Жизнь" и "компьютерное" представление о мире и Боге

Матюшкин И. В.,
mivmiv@aport.ru http://mivmiv.narod.ru/

1. Введение

В статье излагается спекулятивная гипотеза о материи, пространстве, времени и Боге, навеянная бурным развитием компьютерной техники за последние 20 лет. Отправной точкой служит одна сравнительно новая математическая теория, а именно теория клеточных автоматов (cellular automata). Ярким примером последней является игра "Жизнь", компьютерные реализации которой, начиная с 70-х годов и поныне, получили широкое распространение в среде аспирантов и ученых. К настоящему времени, с другой стороны, отшумели бурные дискурсии 20-30-х годов в среде физиков, ряд предсказаний теории нашли подтверждение в опытах с элементарными частицами в 60-80-х годах, некоторые гипотезы спорны и сейчас. Наиболее важными для наших целей являются: 1) явление рождения элементарных частиц в их столкновениях; 2) явление существования короткоживущих частиц; 3) гипотеза о дискретной природе пространства и времени, в частности, понятие "планковской длины".

Есть уже сейчас попытки связать клеточные автоматы с квантовой хромодинамикой, создана калибровочная теория решеток [1, Internet]. В свете предлагаемой гипотезы по-иному видятся основоположения квантовой механики и теории относительности. Хотелось бы привлечь внимание к этой тематике, однако в более общем виде [2], имевшем бы более непосредственное влияние на физику вообще и философию, в особенности на проблему отношений Бога и мира, какими они могут видиться в конце ХХ-го века.

2. Клеточные автоматы и правила игры "Жизнь"

Теория клеточных автоматов берет свое начало с сер.50-х годов, когда Дж. фон Нейман поставил перед собой задачу доказать возможность существования самовоспроизводящихся автоматов [1]. К классу клеточных автоматов относится игра Дж. Конвэя (J. Conway), созданная им в 1970г. Простота ее правил и богатство возникающих вариантов не уступают по красоте фрактальным образам Мандельброта.

В классическом варианте на разбитую на квадраты плоскость кладут фишки (аналог биологической клетки). Колония клеток на следующем ходу изменяется: 1) клетка гибнет, если ее окрестность (8 квадратов) перенаселена (более 4-х клеток) или пустынна (менее 3-х клеток); 2) клетка выживает, если число соседей равно 2,3,4; 3) клетка рождается, если число соседей равно 3. Соответственно можно предложить более сложные сценарии: сделать поле игры конечным (в коробке) или бесконечным, либо разбить плоскость на правильные шестиугольники, либо считать окрестность клетки только имеющие с ней общую сторону клетки (т.е не 8, а 4 соседние клетки), либо разделять клетки на молодые и старые, либо вообще сделать правила выживания асимметричными (сосед, например, справа имеет особое значение), либо, наконец, перенести арену борьбы в пространство (3-х мерная доска). Но даже классический случай дает пищу для размышлений: помимо устойчивых конфигураций типа блок (квадрат из четырех клеток), сигнальные огни (три клетки в линию) существуют движущиеся конфигурации, классическим примером которой является глайдер. Помимо этого энтиузиасты выявили такие интересные объекты, как "глайдерное ружье" (эта фигура испускает с периодичностью из себя глайдеры) ,"сад Эдема" (эта фигура не имеет для себя предшественника), r-пентамимо (завершает свою эволюцию через несколько десятков ходов в виде устойчивых фигур и шести глайдеров). Разумеется, с усложнением правил игры могут выявиться новые свойства (например, детерминированный хаос при переходе в трехмерье). Математически игру Конвэя можно представить булевым полем над двумерной решеткой

Рис. 1.(слева) Показана эволюция фигуры "глайдер", которая за 4 хода транслируется на 1 клетку по диагонали вниз. Рис. 2. (внизу)Показаны "сигнальные огни", совершающие колебания за 2 хода.

3. Формулировка гипотезы

Весьма примечательно, что сам Конвэй формально назвал скорость глайдера скоростью света В данном случае под скоростью понимается отношение суммы числа квадратов по вертикали и горизонтали, на которое переместилась фигура, к числу совершенных ходов. Скорость глайдера тогда равна 1/2 от максимальной скорости перемещения (1 квадрат за один ход). Аналогия "глайдер-фотон" ведет нас к дальнейшим обобщениям.

Итак, существуют абсолютное пространство и время, представленные соответственно индексами {i,j,k} (номер ячейки) и {t}(номер хода). Материальные характеристики физического объекта связаны с заполненностью (состоянием) ячеек. Во всяком случае дидактически можно отождествить массу тела с количеством заполненных ячеек, к нему относящихся. Многообразие устойчивых фигур игры "Жизнь" соответствует многообразию элементарных частиц в игре Природы, неустойчивые фигуры соответствуют короткоживущим или вообще еще не зарегистрированным частицам, а также тем, которые могли существовать только на заре становления Вселенной. Кстати, на автора в свое время произвел впечатление рассказ о парах виртуальных частиц в космическом вакууме, которые, не успев родиться, сразу умирают. Вселенная состоит из чудовищно гигантского числа заполненных и пустых попеременно ячеек. Большой Взрыв возник из фигуры, производящей из себя другие "летящие" фигуры (случай "глайдерного ружья", отчасти r-пентамимо). Вся эволюция мира есть образ доски игры "Жизнь", в которую играет или Природа, или Бог. Допустимо существование иных Вселенных с другими правилами игры, конгакт любого рода с которыми невозможен,- это другие "шахматные доски".

4. Физические следствия

Разберем физические следжствия гипотезы в отношении физики элементарных частиц и квантовой механики. Чему соответствуют такие эпитеты как "странность", "очарованность", "барионный заряд", вводимые для избежания действия запрета Паули? Чему соответствуют привычные нам понятия как "масса покоя", "электрический заряд"? Для ответа на этот вопрос зададим себе другой: какими характеристиками обладает фигура в игре Конвэя?

Целесообразно разделить эти характеристики на три группы:

• относящиеся к состоянию ячейки: размерность векторного поля, множество его значений (в классическом варианте Конвэя реализован простейший случай - размерность поля равна 1, мощность дискретного множества его значений-
• относящиеся к состоянию фигуры как самой по себе: период колебаний фигуры, среднее по периоду число заполненных клеток, направление движения (для сигнальных огней период равен 2, а среднее число непустых ячеек совпадает с текущим и равно 3; для глайдера имеем соответственно 4 и 5);
• относящихся к состоянию фигуры, взаимодействующей с окружением: среднее время жизни, сосуществование (случай "космического корабля" и "экскорта").

К первой группе достоверно нельзя рискнуть отнести ни одну из известных физических величин. Наиболее проста для сопоставления, кажется, вторая группа. Здесь вполне уместна школьная аналогия спина электрона, поляризации фотона с направлением вращения фигуры. Поскольку в любом физическом опыте имеется взаимодействие частицы и прибора (пусть даже и квантового), то у нас нет эмпирически надежного критерия отбора параметров второй и третьей группы. Третьей группе принадлежат, по-видимому, такие величины как "электрический заряд", "гравитационная и инертная масса", которые отвечают за характер взаимодействия частицы с переносчиком поля (фотоном в случае электрического поля, условно гравитоном- в случае гравитационного поля). К третьей группе, наверное, нужно отнести большинство квантовых чисел. Вообще говоря, представление об обменном механизме (через частицу- посредник) любого взаимодействия весьма хорошо согласуется с нашей гипотезой. Легко даже вообразить ситуацию сосуществования частиц А и Б (благодаря обмену частицей В) на доске Природы, но невозможности отдельного существования частицы А (на протяжении достаточного числа ходов). Это может принципиально объяснить неудачи опытов по обнаружению кварков в свободном состоянии (А,Б- кварки, В- глюон). В этой связи уместно вспомнить мысли Лейбница о сосуществовании вещей. Однако, проявления дальнодействующих сил наша гипотеза не может объяснить с подобающей легкостью. Достоин удивления сам факт проникновения электрического поля сквозь преграду вещества. Разрешение возникших трудностей лежит, по-видимому, в применении некоторого аналога принципа Гюйгенса-Френеля из оптики. Еще более удивителен принцип суперпозиции полей. Он обязан нарушаться в глубинах вещества и недрах звезд. Более того, там возможно нетривиальное взаимодействие переносчиков полей разного типа. В обычных условиях, когда, например, атом представляет собой практически пустую систему, вероятность "соударения" трех частиц-фигур одновременно (т.е в пределах 1-10 ходов) мала, удары можно считать последовательными, а их результаты складывающимися. Есть проблема, которая автору кажется трудноразрешимой в рамках предложенной гипотезы,- это непрерывность спектра электромагнитных волн. Предварительное объяснение может состоять в том, что акт испускания атомом фотона ведет к рождению не одного глайдера, а двух последовательно, через некоторое число ходов. "Дистанция" между ними определяет длину волны. Это наглядно объясняет эффект Доплера, однако, тогда что соответствует интенсивности света?

Также приобретает актуальность вопрос о тождественности частице самой себе: в отношении времени и пространства. Первый аспект более прост; так, 4 конфигурации глайдера-фотона могут трактоваться как состояния одной фигуры. Тем не менее, они еще не могут быть отождествлены с квантовыми состояниями; последние, скорее всего, соответствуют направленности движения или вращения фигуры. Второй аспект гораздо интереснее. Если элементарная частица состоит из тысячи ячеек в поперечнике, то небольшая асимметрия ее строения (или мини-спутник типа фигуры "блок" рядом) в виде, например, лишней заполненной ячейки где-то сбоку на данном ходу не окажет существенного влияния на способность частицы откликнуться на данного переносчика взаимодействия. На следующих ходах это уже может отразиться на отклик на другой переносчик. В строгом смысле мы будем иметь различные частицы. Предположение о нетождественности частицы самой себе ведет не только к логической погрешности (одним термином называют разные объекты), но и к оправданию принципа неопределенности. Действительно, то, в каких конфигурационных состояниях подойдут частицы-фигуры к моменту столкновения, определит путь протекания элементарной реакции. Идейно это объяснение принципа неопределнности близко к концепции скрытых параметров; здесь скрыты от нас конкретные положения фигур. Отметим, что важную роль в этих и последующих рассуждениях играет крупность элементарной частицы в сравнении с размером ячейки.

Теперь рассмотрим последствия в отношении теории относительности. Логичным продолжением вышесказанного будет образмерить размер одной ячейки планковской длиной 10^-33см. Если глайдер- это фотон, то наибольшая скорость физического объекта будет кратна или равна скорости света. Кроме того, существование такого предела с необходимостью вытекает из дискретности пространства и времени. Если такой предел есть в отношении безразмерных абсолютного пространства и времени, то он будет и в отношении размерных относительных. Отметим, что относительное пространство (измеряемое в м) по нашей гипотезе существует благодаря абсолютному (теоретически измеряемому в целых числах), а абсолютное время в корне отлично по смыслу от абсолютного пространства (ниже мы скажем нечто обратное). Во всяком случае , одно из следствий теории относительности не противоречит "компьютерной гипотезе".

Гораздо хуже обстоит дело с выполнением принципа относительности в галилеевых системах. В рамках нашей гипотезы, прежде всего, должна получить объяснение сама возможность непрерывности поступательных движений. В этих случаях все атомы и частицы их составляющие, хотя и совершают собственные движения, движутся с небольшой по меркам игры "Жизнь", но согласованной скоростью. Единственный выход состоит в том, что атом совершает движение как целое, т.е. лишь через много ходов гигантская фигура (как бы махина) транслируется на одну клетку в самоподобном виде. Направление движения этой большой фигуры определяется двумя обстоятельствами; 1) собственной случайной асимметрией 2) неравномерностью прихода переносчиков взаимодействий. В равномерном прямолинейном движении гораздо важнее первая причина. Данное объяснение эстетически довольно плохое. Еще одним, не слишком приятным следствием, является необходимость признать взаимозависимости вектора скорости фигуры и ее конфигурации. Это также еще одна сторона признания нетождественности частиц. Таким образом, мы возвращаемся к объяснению Лоренца опыта Майкельсона, при этом принцип относительности выступает не независимым физическим и философским постулатом, а лишь интересным следствием строения вещества. Лоренцево сокращение тогда отнюдь не кажущееся, а физическое, реальное по отношению к абсолютному пространству. Оно в свете гипотезы уже менее фантастично, чем думалось в начале века, но по-прежнему поразительно. Конечно, при этом сокращаются не "длины" ячеек, а, скорее всего, безразмерные расстояния между фигурами. Насколько изменяется сама конфигурация фигуры при этом неясно.

Что касается общей теории относительности, то гипотеза допускает взаимодействие гравитона и фотона (а оно более вероятно вблизи массивных тел!), но исключает всякое искривление пространства. Легко себе представить ограниченную Вселенную, где граничные в математическом смысле ячейки не изменяют своего состояния при любом номере хода. Тогда мир представляется как бы завернутым в капсулу. На начальном этапе развития Вселенной еще не могло существовать никаких известным нам физических законов и частиц. Обычные же частицы (фотон, протон, электрон) уникальны в том смысле, что соответствующие им фигуры обладают не только собственной устойчивостью, но и "выживаемостью" (лучше "самовоспроизводимостью") в столкновениях с другими же обычными частицами. Напрасно ждать в обычных условиях самопроизвольного распада протона, ибо число возможных комбинаций при столкновениях конечно. В этом смысле протон вечен, и некорректно описывать это в терминах "большого периода полураспада". В недрах звезд или при рождении Вселенной мы вправе ожидать противоположного.

5. Гносеологические следствия.

К чему должна стремиться физика? Она должна раскрыть правила игры Природы, т.е. параметры первой группы плюс уравнения итерационной процедуры. Этих правил немного, и они просты, подобно правилам игры Конвэя. Из них, используя всю мощь дискретной математики, физика должна получить все многообразие частиц (с указанием их конфигураций). Для наиболее распространенных частиц следует дать однозначное соответствие, руководствуясь известными законами сохранения (лептонного заряда, например) в элементарных реакциях. Все известные ныне законы квантовой механики (соотношение неопределенностей, уравнения Шредингера и Дирака, правило Гунда и т.д.) представляются некоторыми "теоремами" особого математического языка, который еще нуждается в переводе на язык "аксиом" игры. А.Пуанкаре в этом смысле правильно писал о связи нашего математического знания о многоугольниках с первичными аксиомами, понятиями и теоремами евклидовой геометрии [3, c.20]. Сложившаяся ситуация напоминает отношение ньютоновой механики и старого учения о теплоте, пока их не связала статистическая физика. Отличие лишь в том, что мы знаем основы термодинамики (квантовой механики), но не знаем механику (правила игры). Поэтому следует подчеркнуть, что "компьютерная" гипотеза никоим образом не отменяет и не стесняет уже имеющиеся понятия, подобно тому как современный физик не упрекает химика в том, что он оперирует "термодинамическим потенциалом Гиббса" или считает ядро атома неизменным. Самым трудным будет получить вывод всем известных "законов природы": закона сложения скоростей Галилея, законов механики, закона сохранения энергии и импульса. Заметим, что из "компьютерного опыта" (по наблюдению за трансформациями, например, процессом гибели, различных начальных конфигураций) мы знаем много случаев несохранения числа клеток фигуры; любопытно, что для глайдера (рис.1) число клеток ("масса") сохраняется равным 5. Итак, какими же должны быть "аксиомы", чтобы получить известные нам на данном этапе развития физики "теоремы"?

Весьма возможно, что при разрешении этой проблемы имеющиеся эмпирические данные не дадут однозначного ответа, т.е. будут существовать несколько альтернативных теорий. Расширить же опытную базу принципиально невозможно, поскольку фатально неутешительное качество приобретет разрыв масштабов миров объекта и субъекта, ставя предел познанию мира. Говорят, правда, что предполагаеый "конец науки" связан с недостижимостью огромных энергий в коллайдерах, но дело все же в гигантской разнице бытового размера в 1см и планковской длины (10^-33см). Есть, тем не менее положительное следствие. Дело в том, что аксиомы игры Природы будут сформулированы на простом, ясном человеческом языке в отличие от "корпускулярно-волнового дуализма" квантовой механики и "странности" элементарных частиц. Неправильно, однако, спрашивать о "физическом смысле" тех или иных натуральных чисел (божественного происхождения согласно Л.Кронекеру), присущих игре. Понятия "силы", "поле", "масса" например, приобретут всего лишь метафорическое значение. Может показаться странным после сложности современных разделов физики, что "аксиоматику" игры Природы возможно передать через доступный даже игрокам в шашки понятийный аппарат. Однако, здесь уместно вспомнить учение Канта об априорных формах человеческого рассудка (таблица категорий) [4]. А если принять во внимание эволюционную теорию Дарвина, казавшиеся Канту априорными формы чувственного восприятия и в самом деле могут дать нечто, касающееся действительной формы устройства мира. Это происходит потому, что последние формируют в психофизиологическом плане первые. Кстати, если пользоваться терминологией Канта, мир "мигающих" математических фигур является нам миром масс и зарядов; неподвижное абсолютное пространство и время предстают самими "вещами в себе", и лишь наши относительные размерные пространство и время соответствуют кантовским априорным формам чувственного восприятия.

То, что об этом мире "вещей в себе" можно все-таки сказать кое-что, правда, не более, чем в общем и туманном виде, покажут нам два соображения о количестве измерений (индексов) абсолютного пространства. Предварительно заметим, что самая простая причина того, что относительное пространство трехмерно, состоит в том, что и абсолютное пространство трехмерно. Первое соображение основывается на трех полусовпадениях: 26= число кубов в окрестности куба в 3-х мерной игре "Жизнь"= число букв латинского алфавита " 20-23= число аминокислот, кодирующих наши белки. Кириллица в этом отношении избыточная кодировка, ведь буквы й,ё,ъ мы редко используем. Число сортов "кирпичиков" ферментов, отвечающих за наше химическое взаимодействие с миром, чуть меньше- 23 (включая 3 "незаменимых "аминокислоты), но вспомним, что в нашем биосферном окружении нет некоторых химических элементов (He, Xe, U), следовательно отсутствует необходимость их опознать. Есть, правда, нейтрализующее возражение: 26-27 относится к числу независимых переменных в итерационной формуле, определяясь дефиницией окрестности ("связность") ячейки; так, вместо 8 соседей квадрата можно рассматривать 6 соседей правильного шестиугольника, и тогда пространство может иметь отличную от 3 размерность. Второе соображение проистекает из того, что всякая начальная конфигурация в классической игре "Жизнь" рано или поздно распадается на устойчивые фигуры. Лишь если размерность задачи больше или равна 3, то возможно явление детерминированного хаоса. Сходное положение имеет место для систем нелинейных дифференциальных уравнений без запаздывания.

6. Теологические следствия

Нельзя не удержаться от вопроса, уводящего нас в топкое место: что дальше? Здесь возможны две логически равнозначные альтернативы. Первая сводится к самодостаточному существованию ячеек Вселенной, делая ее еще более материальной. Условно говоря, Вселенная представляется в виде шестигранных пчелиных сот, где более плотный воск ограничивает мед. Соответственно возникают вопросы: какие физические взаимодействия или волны изменяют состояние ячейки из хода в ход? как суммируются воздействия от соседних ячеек?. На эти вопросы мы никогда не будем иметь ответа, и тем самым зайдем в тупик. Вторая альтернатива состоит в том, чтобы признать Вселенную сотворенной Богом, приписав последнему атрибут подлинной сущности. Обе возможности давно известны в философии и теологии, в особенности христианской. Интереснее, конечно, подробнее описать вторую.

Если есть Игра, то должен быть Игрок. Это рассуждение повторяет космологическое доказательство в форме Лейбница, который рассуждал так, исходя не от первопричины, а от логической причины "если А, то Б". Единственное, что мы делаем чуть более выпуклым, так это логическую причину существования абсолютного времени (совершения ходов). В несколько грубоватой, антропоморфной, свойственной нашему компьютеризированному миру, и потому ему более понятной форме опишем отношение Бога к миру.

Сидит скучающий, ценящий математический досуг Бог у своего божественного компьютера, возможности которого в миллионы раз больше самого мощного сервера, быстродействие и объем памяти его почти безграничны. Бог запускает свою авторскую программу, в диалоговом окне выбирает параметры-правила и начальную конфигурацию игры. Чтобы иметь возможность позже любоваться игрой, он сохраняет после каждого хода ее на жестком диске. Содержимое оперативной памяти представляет собой текущее состояние мира, адрес ячейки памяти- ее пространственный индекс, хранимый объект в ячейке памяти может быть битом, отображать вещественное или комплексное число. Процессор терпеливо выполняет операции в цикле for; по внешним признакам он весьма напоминает христианский Святой Дух. Иногда, при взгляде на монитор он видит какую-то интересную фигуру (первый атом золота, например), он прерывает исполнение программы, вырезает (Cut) или копирует (Copy) ее в буфер обмена для последующего сохранения в библиотеке или "галерее славы Игры". Попив кофе, взглянув на часы в нижнем правом углу экрана, он решает продолжить игру с того места, на котором остановился; излишне говорить о том, что никто из "существ" в оперативной памяти и не заметил заминки. Через некоторое свое, божественное время он решил улучшить сценарий, добавив (Paste) сконструированную им во время паузы фигуру, которая воспроизводит сама себя (первая ДНК). Такое происходит, правда, редко. Итак, каждый ход Бог-пользователь видит совершенствование всех фигур в целом, неудачные фигуры, "побарахтавшись" пару миллионов ходов, распадаются. Впрочем, Бог любит совершать чудеса, путем Copy-Paste превратив однажды воду в вино, или, отменив выполнение нескольких миллионов ходов в нескольких миллионах смежных клетках, остановил воды Красного моря перед избранным народом. И только Бог знает, когда он закончит игру, когда посчитает "галерею славы" завершенной (например, мозгом Эйнштейна). Тогда уже будет некому осознавать относительное время, ибо и абсолютного времени уже не будет. Счетчики программных циклов обнуляться, создастся новый лист (пункт меню File-New), и Бог сотворит "новое небо и новую землю", поместив туда копии экземпляров из "галереи славы". Таким образом, в программной реализации Игры, в которой Бог принимает активное участие, и не только в самом начале в качестве перводвижителя.

Данный образ иронически утрирован. Например, упомянутое здесь "божественное" время относится к подлинным "вещам в себе", а любые уточнения о нем являются пустыми, метафизическими, измышленными. Мир становится все более виртуальным, а Бог все более математически реальным. Осторожнее, правда, было бы говорить о Боге философов, и не о гипотезе, а некотором измышленном представлении. Тем не менее, можно сделать понятнее некоторые положения практической христианской теологии. Например, "у Бога тысяча лет, что один день, и один день, что тысяча лет" (смешение божественного и относительного времени). Выявляется бессмысленность вопроса о том, что делают души умерших в чистилище. Лишается абсурдности воскрешение именно телесное, а не чисто духовное. Наконец, показывается, что бессмертие тела не влечет за собой с необходимостью субстанциональное существование души (ахиллесова пята картезианцев). В этом случае ослабляется противоречие материализма с теологией. Мы отказываемся от представления Канта о трансцендентном субъекте, который ограничивается эмпирическими условиями мира явлений, и который позволял сохранить "и природу, и свободу" [4]. Это более соответствует данным физиологии. При абсолютной детерминации поведения человека, однако, действительно ли рушится свобода воли и понятие "греха"? Наколько верен этот кажущийся бесспорным вывод? Требует ли действительно христианство от человека невозможного? Наша гипотеза ведет к полному разделению сфер влияния морали ("моральности", по Канту) и природы. Бог предстает единственным абсолютным мерилом добра и зла, которое преломляется в каждой исторической эпохе и обществе по-разному, он является необходимым условием разрешения метафизической проблемы "бессмертия души"[4].

Сделаем последнее замечание. При условии гигантских резервов оперативной памяти нет особой разницы между цифрами 10¹⁰⁰ и 10²⁰⁰, поэтому можно одним индексом a задать четырехиндексный массив {i,j,k,t} (множество Z равномощно множеству Z⁴). В процессе игры он заполняется "послойно", в сторону увеличения t. Таким образом, Богу могут быть ведомы все времена, которые уже вневременны, включая и далекое будущее (если исключить в дальнейшем вмешательство Бога в ход игры). В такой интерпретации связанные итерационной формулой (а значит "пространственно") ячейки могут иметь далекие номера. Более того, итерационная формула может в принципе содержаить в качестве независимых аргументов t и далекие a1 , где a1 определено нетривиально: a1 =1*2*3*...*a. В этом случае стохастичность порождается уже в самой формуле, но она не доступна для анализа человеческому существу. Действительно, нелепым кажется предполагать такое "дальнодействие" между электроном атома моего тела и протоном в звезде a-Центавра.

7. Заключение

Предлагаемая "компьютерная" гипотеза, как нам кажется, отражает потенциально возможное в конце ХХ-го - начале ХХ1-го веков представление людей о мире и Боге. Важно было с единой "компьютерной" точки зрения посмотреть на сложившийся массив наработок по физике, теории познания, теологии, не углубляясь в частности. Автор не претендует на подлинную оригинальность изложенных базовых идей, скорее всего, подобное можно найти уже у пифагорейцев, но не является ли одной из существенных задач философии передавать символизм древних в символах современности, преподнося всю глубину их мироощущения в понятной нынешним людям "полиэтиленовой обертке"?

Список литературы:

1. Гарднер М. Крестики-нолики, М.: Мир, 1988г.
2. Матюшкин И.В. Игра "Жизнь" и новое представление о пространстве и времени// Тезисы докладов XLII научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук", М.: НИЧ МФТИ, 1999г.
3. Пуанкаре А. О науке М.: Наука., 1983г.
4. Кант И. Критика чистого разума., М.: Мысль, 1994г.
Дата написания: ноябрь 1999
Идея конца: 1998г.

Эффективная организация данных для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата Джона Хортона Конвея “Жизнь”

Чтобы не обременять читателя, в дальнейшем условимся называть этот автомат просто игрой Жизнь. О правилах этой игры написано немало, поэтому мы не будем останавливаться на них, а сразу перейдём непосредственно к теме этой статьи. Тем же, кто либо не знает правил, либо просто хочет прочитать ещё раз о них, можем порекомендовать книгу (1), с которой, пожалуй, начинали все “жизнелюбы”, или книгу (4).

Идея применения вычислительных машин для слежения за ходом игры – не нова. Сам Джон Хортон Конвей использовал компьютер для наблюдения за причудливыми конфигурациями своего детища. Без моделирующих программ увидеть большинство интереснейших превращений, происходящих по ходу игры, было бы просто невозможно. Некоторым вопросам написания таких программ и посвящена данная статья.

Итак, с точки зрения программирования, Жизнь – трудоёмкая, для компьютера, задача, так как требует довольно больших ресурсов машины на непрерывный пересчёт состояний моделируемого мира (под “миром”, здесь и далее, будет пониматься плоскость, разбитая на клетки, на которой рассматривается колония). В чём же этот пересчёт заключается? Фактически, на каждой итерации нужно разрешать отношение соседства между конкретными объектами, то есть, уметь узнавать, сколько у него соседних клеток. Эта статья и посвящена именно тому, как это сделать максимально эффективно (ясно, что вариант полного перебора мест гипотетической дислокации клеток мы рассматривать не будем, тем более, что его применение проблематично на “бесконечных” полях, которые и представляют основной интерес при моделировании процесса Жизни). Далее под “местами” будем понимать позиции, на которых могут стоять клетки, элементарную область в рассматриваемом мире (“A” на рисунке 1), а под “клетками” – места, в которых есть жизнь (“B” на том же рисунке).

“Объектами” будем называть “клетки” и “места”. Эту терминологию лучше запомнить, так как она будет постоянно использоваться.

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

Любой мало-мальски серьёзный проект начинается с продумывания и организации структур данных, необходимых при решении задачи. Первая дилемма, встающая перед нами – хотим мы использовать динамические или статические структуры для хранения информации о клетках. Под статическими структурами имеется в виду, конечно, массив. Очевидно, недостатков у этого метода представления данных – более чем достаточно. Хватит даже одного: размеры популяции (число клеток в ней) неизбежно будут ограничены. Зачем же он нужен? Метод, основанный на использовании массива, программируется, пожалуй, проще, чем любой другой. Иногда Жизнь реализуют в декоративных целях: неплохая экранная заставка – развитие случайно сгенерированной популяции на поле, скажем, в 1024 на 768 мест, то есть, по пикселю на место. Зачем в такой программе трудиться над списками или другими динамическими структурами? Кроме того, здесь – тривиальный способ ускорения разрешения отношения соседства – сортировка.

1. Сортировка

Итак, пусть нам дан массив на m элементов некоторой структуры, LifeCell, содержащей два информационных поля. Допустим, такой структуры:

struct LifeCell

{
int x,y;
};

Будем хранить в нём информацию о существующих клетках на данный момент времени. То есть, если место с координатами x0 и у0 является клеткой, то в массиве должен присутствовать элемент, имеющий поля со значениями x0 и y0. Пусть на данном шаге моделирования у нас будет заполнено n элементов. Так как размеры популяции, как правило, не постоянны во времени, то n будет меняться от итерации к итерации. Вот вам и очевидное ограничение: n не может превосходить m!

Как происходит разрешение отношения соседства для объекта с координатами x0, y0? Для него нам нужно найти в массиве все соседние клетки (смотрите рисунок 2), тогда остальные его соседи являются местами. Обращаем Ваше внимание на то, что такой поиск нужно производить не только для n клеток, которые содержатся в массиве, но и для всех окружающих их объектов, то есть именно, для ближайших восьми соседей, так как это – места гипотетического возникновения жизни. Таким образом, на каждой итерации придётся разрешать отношение соседства для 9*n объектов (n клеток, у каждой – 8 соседей).

Как сделать это максимально эффективно? Конечно, отсортировав массив по возрастанию (или по убыванию) одной из координат, скажем, по y. Тогда будет достаточно только пробежать в массиве интервал ячеек, для которых значения y-координат элементов будут заключены между y0-2 и y0+2. Остальные клетки рассматривать уже бессмысленно, так как они слишком далеки от нашего объекта. Затем нужно перейти к следующему объекту или следующей ячейке массива. Разрешать отношения соседства в строгом порядке, установленном расположением ячеек в массиве – очень рационально. Поступаем так: рассмотрели соседей клетки, содержащейся в ячейке массива с номером i, рассмотрели соседей её соседей – перешли к следующей (к (i+1)-ой). Тогда счётчик (индекс) обрабатываемой ячейки i поможет нам рассмотреть весь вышеописанный интервал и будет достаточно просто “пройтись” от i-ой ячейки вправо и влево по массиву до тех пор, пока y-координаты клеток не будет отличаться от y-координаты рассматриваемого объекта на два.

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

После того, как с соседями станет всё ясно, вносим в массив необходимые изменения, и, перед переходом на следующую итерацию, лишь сортируем его. Для этого можно использовать, например, алгоритм QuickSort, предложенный в 1962 году английским математиком Чарльзом Хоаром (его ещё можно встретить под названием “быстрая сортировка”). Для его изучения, можем порекомендовать книгу (2), где есть много интересной информации об алгоритмах сортировки вообще (на самом деле – и не только сортировки, а практически всех базовых алгоритмов, в том числе и упоминаемых далее в этой статье) и QuickSort, в частности.

Опыт показывает, что сортировка внутри групп с одинаковыми y-координатами по x-координатам даст ощутимый эффект лишь при достаточно больших размерах популяции. Тем не менее, иногда, это всё же имеет смысл и тогда по x-координатам стоит проводить поиск дихотомией (“двоичным поиском”). Описание этого алгоритма, как, кстати, и алгоритма QuickSort, можно найти, например, в книге (3).

От статических структур переходим к динамическим. Как Вы понимаете, сортировать список – не лучшая идея. Несмотря на то, что существует множество алгоритмов для этого, но сочетать динамические структуры, с тем же методом, который мы использовали для статических – не разумно, так как его реализация будет намного более сложной. Однако, справедливости ради, необходимо отметить, что трудоёмкость “ленточной сортировки” (метода упорядочивания списков) такая же, как и у QuickSort’а, то есть O(N*ln(N)), где N – число сортируемых элементов. Но к динамическим структурам применимо такое мощнейшее средство, как хеширование.

2. Стандартные принципы хеширования и их применение к Жизни

Хеширование (от английского “hash” – “размешивать”) служит для оптимизации задач обработки информации, а конкретнее, преимущественно, для интересующего нас поиска (для нас важна именно эта операция, ведь как бы мы не организовали хранение информации, по всему её объёму, придётся искать соседей некоторого объекта).

Метод хеширования позволяет производить это более эффективно. Его принцип заключается в разбиении всего набора данных на маленькие группы, с которыми быстрее оперировать. Для этого информационным полям конкретной структуры, сопоставляется значение некой функции. Так называемой, хеш-функции. Разбиение на группы, “размешивание” информации, происходит по признаку равенства этого значения (оно ещё называется ключом). Нужно стремиться к тому, чтобы группы были приблизительно одинаковыми по величине. Когда мы знаем содержимое полей структуры, которую хотим найти и можем произвести подсчёт ключа для неё, то после этого, искать точное совпадение требуемых полей нужно уже не по всему набору данных, а лишь в рамках группы, отвечающей конкретному полученному значению хеш-функции. В худшем случае, хеширование приведёт к обычному поиску полным перебором (справедливости ради надо отметить, что так будет лишь с точки зрения трудоёмкости, на практике получится ещё медленнее из-за “холостого прокручивания” механизма хеширования). Но для этого нужна поразительно неудачная хеш-функция, выдающая одинаковые значения ключа для всех объектов-структур, содержащихся в наборе данных, по которому производится поиск. Подробности об этом методе можно найти в, уже упоминавшейся в этой статье, книге (2).

Достаточно эффективный способ применения такого метода – организация массива указателей на списки. Каждый из этих списков содержит структуры, значения хеш-функции для которых одинаково (это – вышеописанные группы), а индекс ячейки массива, содержащей указатель на данный список, равен её значению (этот способ будет широко использоваться в следующих параграфах). Также, вполне благоприятен вариант, когда индекс равен некоей функции от её значения. Ведь, например, в языках C/C++ массивы индексируются от нуля, и если наша хеш-функция принимает целые значения от 7, то функция преобразования индекса должна будет вычитать из получающегося ключа семёрку. Впрочем, эту функцию преобразования, в таком случае, имеет смысл включить в процедуры подсчёта хеш-функции.
Итак, возвращаясь к нашему примеру, продолжим рассмотрение данных, хранящихся в объектах вышеописанного типа LifeCell. Теперь, когда нам понадобится посмотреть, является ли клеткой место (x0+1;y0-1), мы сосчитаем хеш-функцию от данных значений полей, а потом поищем информацию о ней не среди всех клеток, а среди лишь членов списка, для которых она имеет то же значение.

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

Очень часто в качестве хеш-функций применяются битовые операции. Пусть x, y и ключ занимают по одному байту, тогда последний можно по битам составить так, как показано на рисунке 3. Если целого байта под ключ жалко, то можно использовать четыре бита, как предложено на рисунке 4 (для обоих рисунков будем считать, что младший бит – слева). Конечно, эффективность этого метода зависит от набора данных, на котором он используется. Скажем, точки (255;0), (150;45), (166;37), (200;139) размешаются хеш-функцией, изображённой на рисунке 3 хорошо, все – в разные списки, а точки (85;239), (117;238), (87;171), (213;170) – все в один.

На самом деле, нет никаких принципиальных ограничений на используемые хеш-функции, кроме границ здравого смысла. Помимо побитовых преобразований, это могут быть просто математические функций или композиции тех и других. Но не надо слишком мудрствовать. Надеемся, например, синус суммы x и y вряд ли кто-нибудь будет использовать в качестве хеш-функции, по крайней мере, применительно к Жизни.

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

Изображённые на рисунках 3 и 4 модели получения ключа по полям LifeCell используют некие общие соображения теории хеш-функций, абстрагируясь от специфики задачи. Как было указано выше, есть наборы клеток, которые эти функции размешают крайне плохо. Давайте всё-таки вспомним, что мы моделируем именно Жизнь.

3. Более “Жизненное” хеширование

Зададимся двумя целыми параметрами a и b и матрицей указателей на списки mat (далее, говоря “хеш-таблица”, будем иметь в виду именно её) размера a на b. В качестве ключей хеширования (здесь их будет даже два) предлагается использовать остатки от деления x на a в первом случае и y на b, во втором. Вот примеры реализации таких хеш-функций для x и для y, соответственно:

int HashX(int x)

{
return x%a;
}

int HashY(int y)

{
return y%b;
}

Очевидно, что результатом выполнения первой функции будет целое число из отрезка от 0 до a-1, а второй – от 0 до b-1. Пусть, после одного такого вычисления мы получили f – как значения ключа для x, а g – для y некоторой точки (x0,y0). Тогда мы должны будем искать информацию о том, является ли место (x0,y0) клеткой в списке, на который указывает mat(f,g). На рисунке 5 приведён пример такого размещения, в котором положено a=8 и b=8, хотя, вообще говоря, a и b вполне могут быть (а скорее, даже, должны быть) не равны, что мы будем наблюдать в дальнейшем.

Так в чём же обещанное преимущество хеш-метода, описанного в этом параграфе, над общим, описанном в предыдущем? Дело в том, что этот метод – адаптивный, то есть он может повышать свою эффективность, в зависимости от конкретных данных, “переразмешивать” структуры вследствие анализа своей собственной работы.

4. Адаптивное хеширование

Как Вы уже, наверное, догадались, механизм “переразмешивания” основан на изменении a и b. Когда списки, “прицепленные” к разным ячейкам матрицы, слишком сильно отличаются по размеру, следует изменить параметры хеширования (a и b) и, как следствие, размеры нашей таблицы. Вернёмся снова к случаю, когда оба параметра равны восьми, рассмотренному нами в предыдущем параграфе. Клетки с координатами 1, 9, 17, … , и вообще, вида 1+8k (где k – некое целое число), в таком случае, попадут в один список (ещё раз взгляните на рисунок 5). Как нужно поменять a и b, чтобы исправить ситуацию? Посмотрите на таблицу №1.

Здесь приведены остатки от деления чисел указанного вида на целые числа от одного до двадцати четырех. Жёлтые строки не представляют для нас никакого интереса, так как изменение параметра хеширования на соответствующие им значения делителя не приведут к “переразмешиванию”, а сохранят текущую группировку информации, то есть, всё, что было в одном списке – в одном же и останется. Только количество списков уменьшится, вследствие их объединения прямо целыми группами (например, это произойдёт, если поменять значение a с 8 на 4). Остальные строки разделены на розовые и голубые зоны. Эти зоны представляют собой периоды значений хеш-функции (два соседних периода выделены разными цветами, для наглядности) если параметр размешивания принять равным соответствующему делителю. В рамках рассматриваемой нами задачи, ясно, что все значения хеш-функции внутри одного периода не повторяются, тогда длина периода и есть количество списков, на которые разобьётся группа, имеющая непомерно большое, в нашем понимании, число элементов. Если мы рассматриваем в данный момент хеширование по x-координате, а d – делитель, претендующий на то, чтобы стать параметром размешивания (для определённости – a), то это длина (обозначим её, как len), очевидно, равна max(a,d)/nod(a,d), где функция max возвращает максимум двух чисел, а nod – их наибольший общий делитель. Теперь мы можем просто сформулировать, что для жёлтых строк len=1.

Какое же d принять за новое значение a? Конечно, лучше – то, которому соответствует наибольшая len. Тогда, одним из критериев оптимального решения является то, чтобы nod(a,d)=1 или, проще говоря, чтобы a и d были взаимно простыми. Ясно, что можно найти сколь угодно большое d, удовлетворяющее этому условию. Вообще предел len, при d стремящемся к бесконечности, равен бесконечности, но с практической точки зрения нам бы не очень хотелось непомерно расширять mat. Поэтому “лучше, чтобы nod(a,d) равнялся единице”, так как тогда меньшим d будет соответствовать большая len.

Так всё-таки, в каких пределах лучше искать d? Наверное, самым правильным будет завести неких базовый уровень t, в окрестности которого найти d1 и d2, такие, что d1 < a , а d2 > a и оба “достаточно хорошо” переразмешают клетки. Потом выбрать из них то, которое ближе к t. Что значит “достаточно хорошо перемешивает”? Как уже не раз говорилось, это значит так, чтобы все группы были приблизительно равных размеров. Методы повышения эффективности установления этого мы можем обсудить.

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

Что такое, эти пресловутые, группы “приблизительно равных размеров”? Как понять, что построенная хеш-таблица требует “перетряхивания”? Предлагается следующий метод: при каждом её изменении, обусловленном событиями, происходящими с колонией, считать среднее арифметическое числа элементов в списке. Здесь можно воспользоваться тривиальным свойством среднего арифметического: если нам известно его значение An для n чисел, то, если добавить к набору чисел, для которого производится вычисление, ещё одно число q, то для n+1 числа An+1=(nAn+q)/(n+1). Например, можно написать это как-то так:

void AddValue(int q, float& A, int& n) // Функция, осуществляющая добавление к набору n чисел, по которому считалось среднее арифметическое A, числа q

{
A=(A*n+q)/(++n);
}

void Iteration()
{
float A=0; / Текущее значение среднего арифметического
int n=0; / Текущее количество значений. В терминах вышеприведённого текста, для данного n A представляет собой An
int q=0; / Добавляемое значение
< Код программы, в котором, в частности, как-то задаётся q>
AddValue(q, A, n); / Непосредственно добавление значения. Как правило, оно происходит в некотором цикле
< Код программы>
}

Пусть результат подсчёта среднего помещён в A. Так, если изначально задать некое целое положительное число r, то перестраивать хеш-таблицу следует, если число клеток в некотором списке в r раз больше, чем A. Для быстрейшей проверки этого соотношения имеет смысл представить mat не как матрицу указателей, а, например, как матрицу записей с двумя полями: одно из которых – указателей, а второе – длина списка, на который он указывает. Подсчитав сумму этих длин, можно заодно выяснить и число клеток на данном шаге, что может быть полезно (смотрите несколько абзацев выше) или намного более простым способом подсчитать A. Зачем же тогда нужен описанный выше способ определения среднего? Дело в том, что есть ещё один вариант, экономящий память, но теряющий в эффективности. Можно сравнивать r, умноженное на A, со значениями длин списков, полученными на следующей итерации (их всё равно нужно считать для следующего значения среднего арифметического). Таким образом, A, “отстаёт” на один шаг. Почему это вообще имеет смысл? Ответ лежит только в узко специфических особенностях Жизни по правилам Конвея (2 соседа, чтобы не умереть, 3, чтобы родиться) или близких к ним, но никак не что-то вроде 1, 6 и 7, чтобы умереть и 2, 3 и 5, чтобы родиться, Жизнь по которым даже представить трудно. Во-первых, это обусловлено периодичностью стационарных состояний, а во-вторых, тем, что “сфера влияния” клетки – её ближайшие соседи и за один шаг она не может “переместиться” дальше, чем на одно место. Таким образом, стоящая в списке, на который указывал mat(u,v) клетка, не попадёт никуда, кроме, как в один из восьми списков: mat(u,v+1), mat(u,v-1), mat(u+1,v+1), mat(u+1,v), mat(u+1,v-1), mat(u-1,v+1), mat(u-1,v) или mat(u-1,v-1). Думаете, игра не стоит свеч? Напрасно! Попробуйте. Конечно, намного эффективнее (или, по крайней мере, логичнее) рассматривать A с текущими значениями длин списков, но как промежуточный вариант это очень не плохо. А если Вы программируете Жизнь под DOS’ом, то это – просто способ сэкономить память ещё на несколько сотен клеток. Кроме того, это можно рассматривать просто, как расширение описываемого метода хеширования, вносящее дополнительную неопределённость в результат.

Константу r выбирайте также осторожно, чтобы слишком частые “перестройки” не затормаживали работу машины из-за большой трудоёмкости, а слишком редкие – из-за неэффективного поиска.

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

Наверное, у Вас возникает абсолютно справедливый вопрос: а какие a и b использовать при первом шаге программы? Да хоть уже не раз упоминавшиеся значения 8! А лучше – a=8, а b=7, чтобы первая же итерация с диагонально-растянутыми колониями не потребовала переразмешивания. Однако, метод адаптивный и mat всё равно будет перестраиваться под конкретную ситуацию на поле. Лучше выбирайте их не очень большими, помните, раз в итерацию Вам придётся пробегать матрицу размером a на b, делая, прямо скажем, не тривиальные операции. Поэтому и было упомянуто, что можно использовать t, как плавающую границу. Пример такого метода: задаться некоторым параметром w и считать t, не, как было предложено выше, как кубический корень из числа клеток, а как корень степени w, чтобы, варьируя w от 3 до “бесконечности”, удерживать t в разумных для используемого компьютера пределах. То есть так, чтобы пересчёт занимал время, не обременяющее пользователя. Однако, нужно иметь в виду, что чем больше a и b, тем быстрее, для хорошо размешанных данных, осуществляется поиск клетки.

Здесь приведён далеко не полных список возможных методов эффективной организации данных при программировании такой интереснейшей игры, как Жизнь. Кроме того, они немного адаптированы под статью. Ведь на практике, вместо массива структур с двумя полями, очевидно, лучше применять просто два массива. Однако, информация, представленная в этой статье, пожалуй, может послужить хорошей отправной точкой или, по крайней мере, поводом для размышлений. Автор с удовольствием будет общаться с теми, кто имеет, что сказать по данному вопросу или вообще, поводу алгоритмов реализации Жизни, форматов файлов, хеш-функций, логики построения, математики, или с теми, кто просто хочет пообщаться на тему клеточных автоматов в целом и Жизни, в частности. Может быть, кто-то реализовывал что-то подобное на практике или воспользовался вышеописанными советами при написании программ? Вообще, поделитесь, пожалуйста, впечатлениями о статье.

Список литературы:
# Гарднер М.Математические досуги. – М.: Мир, 1972, страницы 458-488;
# Ахромеева Т.С., Дородницын В.А., Еленин Г.Г., Курдюмов С.П., Малинецкий Г.Г., Потапов А.Б., Самарский А.А. Компьютеры и нелинейные явления: Информатика и современное естествознание / Под редакцией Самарского А.А. – М.: Наука, 1988, страницы 5-43;
# Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построения и анализ. – М.: МЦНМО, 2000, страницы 135-180, 213-236;
# Романовский И.В. Дискретный анализ. – СПб.: центр издательских систем Санкт-Петербургского Государственного Института Точной Механики и Оптики, 1998, страницы 50-54, 94-95;
# КЛЕТОЧНЫЙ АВТОМАТ СОЗДАЕТ МОДЕЛЬ МИРА И МИР ВОКРУГ СЕБЯ

Брайан Хэйес,
"В МИРЕ НАУКИ"

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

Идея автомата с клеточной структурой почти также стара, как и идея электронно-вычислительной машины. Первые исследования были проведены в начале 50-х годов Дж. фон Нейманом (следует учесть важный вклад в эти разработки С. Улама). Первоначальная цель фон Неймана состояла в создании простой системы, способной воспроизводить саму себя подобно живому организму. Наиболее известный клеточный автомат - игра "Жизнь", придуманная в 1970 г. Дж. Конвеем, как ясно из названия, также имеет биологический аспект: клетки рождаются, живут или умирают в зависимости от локальной плотности популяции.
В более поздних работах, посвященных клеточным автоматам, исследования приняли несколько другое направление. Конфигурации локально взаимодействующих клеток рассматриваются как потенциально важные модели физических систем - от снежинок до ферромагнетиков и Галлактики. Они применимы также к вопросам кибернетики и вычислительной математики, как практическим (как следует организовать сеть взаимодействующих ЭВМ?), так и теоретическим (каков самый крайний предел мощности вычислительной машины?). Возможно, наиболее интригующим является тот факт, что клеточный автомат может рассматриваться как "числовая вселенная", которая сама по себе достойна исследования, даже если отвлечься от ее полезности как модели реального мира.
Возрождение интереса к клеточным автоматам было отмечено созданием рабочей группы по данной теме год назад в Лос-Аламосской национальной лаборатории. Был опубликован сборник работ (около 20 статей) в журнале "Physics D" и отдельным выпуском в издательстве "North-Holland". Почти все, что содержиться в этом сборнике, основано на работах обсуждавшихся на специальном симпозиуме в Лос-Аламосе.
Для характеристики клеточного автомата полезно выделить четыре его аспекта. Во-первых, расположение клеток образует некоторую геометрическую структуру. Для модели роста снежинок достаточна двумерная шестиугольная схема, но в большинстве других случаев выбирается прямоугольная решетка, состоящая из квадратов. Легко можно построить трехмерную (и даже с большим числом измерений) схему, но гораздо труднее ее себе представить. Недавно поразительные открытия были сделаны с простейшей одномерной схемой: простой цепочкой клеток.
Далее при заданной схеме необходимо определить ту окрестность, которую данная клетка изучает при вычислении своего следующего состояния. В случае двумерных прямоугольных схем особое внимание уделяется окрестностям двух видов. Фон Нейман рассматривал четыре ближайших соседа каждой клетки: на севере, юге, востоке и западе; это множество клеток теперь называют окрестностью фон Неймана. Окрестность, включающую эти четыре соседние клетки и четыре клетки, прилегающие к исходной по диагоналям, называют окрестностью Мура (в честь Э. Мура). Ясно, что окрестности пересекаются и данная клетка входит сразу в несколько окрестностей. В некоторых случаях считают, что центральная клетка - та клетка, которая производит вычисления, - сама входит в свою окрестность.
Третий фактор, который следует рассматривать при описании клеточного автомата, - это число состояний, которое может принимать клетка. Фон Нейман построил самовоспроизводящуюся систему, составленную из клеток с 29 возможными состояниями, однако большинство автоматов гораздо проще. Имеется огромный диапазон для изменений даже у двоичных автоматов, у которых клетка имеет два возможных состояния. Состояния могут быть представлены как 1 или 0 (включено или выключено, живое или мертвое).
Наконец, первоисточник изменений в мире клеточных автоматов - это огромное число возможных правил для определения будущего состояния клетки исходя из теперешней конфигурации ее соседей. Если k - число состояний, которое может принимать каждая клетка, а n - число клеток, входящих в окрестность, то существует k^k^n возможных правил. Так, для двоичного автомата с окрестностью фон Неймана (где n = 4) существует более чем 65000 возможных правил; для окрестности Мура (где n = 8) имеется 10^77 правил. Однако лишь малая их часть когда-либо изучалась.

В игру "Жизнь" играют на прямоугольной решетке из клеток с двумя состояниями и с окрестностью Мура и дополнительным усложнением, согласно которому центральная клетка тоже считается членом своей окрестности. Другими словами, при каждом шаге эволюции системы каждая клетка проверяет состояния восьми своих соседей и свое собственное. Согласно правилам, установленным Конвеем, если центральная клетка жива, то она будет жить в следующем поколении, когда две или три клетки из ее окрестности живы. Если найдутся три живые клетки в рассматриваемой окрестности, то центральная клетка будет живой в следующем поколении независимо от ее теперешнего состояния. Во всех других случаях центральная клетка либо умирает, либо остается мертвой.
Прелесть игры "Жизнь" состоит в ее непредсказуемости. Некоторые схемы полностью умирают; многие другие образуют устойчивые конфигурации либо циклические конфигурации с периодом в несколько поколений. Однако за прошедшие годы было найдено много очень интересных начальных состояний, таких, как "скользящая пушка", которая порождает нескончаемый поток снарядов. Исследование игры "Жизнь" в настоящее время продолжается. Последние достижения были описаны Мартином Гарднером в книге "Wheels, Life, and Other Mathematical Amusements". Здесь же я рассмотрю другие клеточные автоматы, свойства которых только начинают исследовать.
Среди множества возможных правил перехода лишь немногие интересны сами по себе. Например, правило, устанавливающее, что данная клетка будет "включена" тогда и только тогда, когда клетка слева от нее включена, определяет эволюцию, которую очень легко предсказать: любая начальная схема сохраняет свою конфигурацию, но сдвигается на одну клетку вправо на каждом временном шаге. Подкласс правил, называемых счетными, или суммирующими, по-видимому, содержит образцы почти всех встречающихся типов клеточных автоматов. При правилах такого рода новое состояние клетки зависит только от числа соседей в данном состоянии, но не от их положения. Многие автоматы, основанные на таких правилах, были изучены членами группы информационной механики лаборатории вычислительной математики в Масачусетском технологическом институте. В эту группу входят Э. Фредкин, Н. Марголус, Т. Тоффоли и Дж. Вишняк.
Одно из простейших счетных правил - это правило четности, которое приписывает клетке значение 1, если нечетное число соседей находится в состоянии 1, и значение 0 в других случаях. Любая начальная конфигурация повторяется четыре раза, затем эти четыре копии в свою очередь повторяются и т.д.
Другий класс счетных правил - это правила "голосования", при которых центральной клетке приписывается значение 1, как только число единиц в ее окрестности превышает некоторое пороговое значение. В докладе на Лос-Аламосском симпозиуме Вишняк отметил, что по правилам такого типа получаются модели фильтрации (просачивания) и образования активных центров - очень важных явлений в физике твердого тела и других областях науки. Термином "фильтрация" обозначают образование непрерывного пути через некоторое пространство; например, когда металл распределен в изолирующей матрице, проводимость материала зависит от вероятности образования непрерывной цепочки атомов металла. Точно также передача инфекционного заболевания возможна только при наличии непрерывающейся последовательности восприимчивых индивидов. Образование активных центров - процесс, на котором основаны рост кристаллов, кипение жидкости и другие подобные явления.
Одно из правил перехода, приводящее к фильтрации, присваивает центральной клетке значение 1 только тогда, когда значения по меньшей мере трех клеток из пяти - т.е. окрестности фон Неймана плюс центральная клетка - равны 1. Развитие фильтрации очень сильно зависит от исходной концентрации единиц. Если концентрация меньше половины, то непрерывная цепочка единиц, заполняющих схему, по-видимому, не образуется в ходе эволюции. При концентрации 1/2 и больше появляются цепочки, но вся решетка ими не заполняется; в заключительном устойчивом состоянии остаются "островки" нулей. Образование кристаллов, при котором схема прочно заполняется единицами, наблюдается в том случае, когда правило изменяется и требуется лишь две из пяти единиц в окрестности. Критическая концентрация равна 0,0822....

Вишняк и другие ученые из группы Массачусетского технологического института подчеркивают, что клеточный автомат имеет статус, отличный от статуса других физических моделей. Наиболее распространенным средством построения математической модели мира издавно служило дифференциальное уравнение, которое описывает изменения некоторой величины как функцию координат и времени. Например, уравнения Максвелла дают изменения электромагнитного поля от точки к точке и от одного момента времени к другому. Все величины в таких уравнениях являются непрерывными (они гладко изменяются), с другой стороны, клеточный автомат - полностью дискретная система. Пространством является не континуум, а клеточная схема; время разбивается на последовательность дискретных шагов, а клетки автомата могут иметь лишь конечное число состояний, в то время как величина поля принимает значения из непрерывной области значений.
Разумеется, реальные пространство и время и многие физические переменные величины рассматриваются как непрерывные, а не дискретные (по крайней мере в наиболее распространенных областях исследований). Однако из этого не следует, что дифференциальные уравнения по своей природе позволяют построить более совершенную модель реального мира. Когда уравнения должны быть решены численно, как при моделировании с помощью ЭВМ, непрерывные переменные могут быть вычислены приблизительно с некоторой конечной точностью; на самом деле они представляются дискретными величинами. При использовании клеточных автоматов дискретность выступает в явном виде, и их временная эволюция может быть вычислена точно; здесь приближения не нужны. Кроме того, в этом случае можно в большей степени использовать возможности цифровых вычислительных машин.
...

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

Существует особый класс клеточных автоматов, называемых обратимыми. Из любого начального состояния на любое число временных шагов допускается эволюция обратимого автомата, а затем автомат останавливается и запускается обратным ходом, после чего он возвращается в свое точное начальное состояние. Конфигурации образованные типичным обратимым автоматом, качественно отличны от конфигураций, свойственных необратимому автомату. В частности, если конфигурация вначале случайна, то она и стремится остаться случайной - самоорганизующейся структуры не возникает.
Необходимым условием обратимости является детерминированность правила перехода в обоих направлениях, вперед и назад, т.е. каждое возможное состояние окрестности должно иметь единственное предыдущее состояние и единственное последующее состояние. Игра "Жизнь" необратима, потому что предыдущий этап какого-нибудь состояния нельзя определить однозначно; например, если текущее состояние клетки - "мертва", в предыдущем поколении она могла иметь любое число "живых" соседей, отличное от трех. Систематический способ создания обратимых правил перехода был изобретен Фредкином, а позднее исследован Марголусом. Суть этого метода - заставить следующее состояние клетки зависеть от двух предыдущих состояний окрестности. Состояние в момент t+1 дается некоторой функцией окрестности в момент t минус та же функция в момент t-1. Тогда обращение производится непосредственно: состояние в момент t-1 должно даваться состоянием в момент t минус состояние в момент t+1.
...

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

Классические статьи о "Жизни"

Серия переводных статей Мартина Гарднера, которая является чуть ли не единственным систематическим изложением основ Игры "Жизнь" на русском языке.
Статьи