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

Пусть конфликтуют традиционные виды: "крестики" и "нолики". Тогда состояние клетки клеточного пространства может быть следующим:

• клетка свободная (s);
• в клетке активный крестик (X);
• в клетке пассивный крестик (x);
• в клетке активный нолик (O);
• в клетке пассивный нолик (o).

Активные могут захватывать свободные и чужие клетки, пассивные - нет. Смысл этого станет ясен позже.

Крестики и нолики "ходят" попеременно.

Ход крестиков.

Просматриваются все клетки пространства, но свое состояние на данном ходе могут изменить только клетки с состояниями s, X, o. Для данной клетки анализируются 8 соседних и проводится подсчет количества соседних активных крестиков kx и количества активных ноликов ko.

Если данная клетка в состоянии X, то:

если kx+ko>=p2 (слишком много активных соседей) или kx<=p1 (слишком мало активных "своих"), то клетка становится пассивной - x;

в противном случае, т, е. при невыполнении неравенств, клетка остается в X.

Если клетка не в X, то:

если kx>p1, то клетка переходит в X (достаточно много своих активных соседей);

в противном случае состояние клетки не меняется.

Ход ноликов.

Просматриваются все клетки пространства, но свое состояние на данном ходе могут изменить только клетки с состояниями s, O, x. Для данной клетки анализируются 8 соседних и проводится подсчет количества соседних активных крестиков kx и количества активных ноликов ko.

Если данная клетка в состоянии O, то:

если kx+ko>=p2 (слишком много активных соседей) или kx<=p1 (слишком мало активных "своих"), то клетка становится пассивной - o;

в противном случае, т, е. при невыполнении неравенств, клетка остается в O.

Если клетка не в O, то:

если ko>p1, то клетка переходит в O (достаточно много своих активных соседей);

в противном случае состояние клетки не меняется.

Здесь p1=2 и p2=7 - пороги, значения которых пришлось подбирать.

При таком алгоритме активные клетки съедают свободные и чужие пассивные клетки, оставляя за собой свои пассивные - занимают пространство. Пассивные клетки сами свое состояние не меняют. Их состояние могут изменить только активные клетки-соседи противоположной стороны. При столкновении активных происходит "бой", результат которого зависит от конкретной конфигурации клеток. Если в пространстве будут активные клетки только крестиков или только ноликов, то процесс скоро закончится тем, что будут заняты все свободные клетки одной из сторон.

Если будут активные клетки двух сторон, то ситуация меняется коренным образом. На рисунках показаны результаты моделирования описанного алгоритма для разных шагов процесса. Здесь каждый шаг включает один ход крестиков и один ход ноликов. На рисунках серый цвет - клетки s, белый - X, черный - O, светло-серый - x, темно-серый - o. Пространство без границ, в виде тора, 100 на 100 клеток.

На первом рисунке изображена начальная конфигурация, шаг 1. Были введены четыре крестообразные структуры X и четыре крестообразные структуры O. С них начался процесс.

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

На третьем рисунке изображен 40-й шаг. Конфликты ширятся, идет взаимный захват клеток. Начальная конфигурация угадывается с большим трудом.

На четвертом рисунке показан 150-й шаг. Образовалась сложная разветвленная структура, которая продолжает интенсивно "перемешиваться". О начальной конфигурации ничто не напоминает. Свободных клеток уже нет.

Можно выделить два ценных свойства нового алгоритма:

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

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

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

Экранная заставка: если расцветить изображение клеток, то получается интересная, динамичная цветная картина, которая буквально завораживает.

При кодировании информации: начальное состояние процесса можно взять в качестве "ключа" - используем уникальность процесса. Затем выбираем состояния процесса (или его части) по мере его развития. Так, получим необходимые "буквы" алфавита, которыми закодируем сообщение. При приеме сообщения достаточно знать ключ и правило выбора букв.

Возможно использование алгоритма для моделирования волновых процессов в физике и химии.

Владимир АПОРОВИЧ,
vladimir.aparovich@tut.by