ИНТЕЛЛЕКТУАЛЬНАЯ ИГРА GAME OF LIFE / ЭВОЛЮЦИЯ В РОССИИ.
ПРЕДЕСЕССОРЫ И ПРЕДСТАНДАРТНЫЕ СОСТОЯНИЯ.

Щеглов Г. П.
доцент, канд. техн. наук, доцент

Тульский государственный университет, Россия, г. Тула

Представляется обратная классическому алгоритму Конвея - задача поиска предшественников заданной фигуры. Излагается тема исследования предесессоров и предстандартных состояний в активной Game of Life...

Ключевые слова: Конвей, Life, активная, игра, правила, предшественник, предесессор, целеполагание, стандартные образования, спортизация.

Литературные ассоциации - Рей Бредбери, И грянул гром.
Малейшее вмешательство в ход истории рушит все последующее.
Наступите на мышь – и вы сокрушите пирамиды. Не наступайте на мышь!

Неинституализированная интеллектуальная игра Game of Life - гениальное изобретение /1970/ Джона Хортона Конвея (John Horton Conway)[1]. В России известна как Жизнь/Эволюция, последнее в переводе /1971/ журнала Наука и жизнь [2].

Игра представляет собой zero-game одного пассивного "игрока" и сводится к наблюдению за происходящими на бесконечном клетчатом поле преобразованиями фигур составленных из одноцветных фишек.

Авторское развитие [3, 4, 5] классической Игры - поиск предшественников, алгоритмические расширения в цвете и объеме, игры в полу- и ограниченном пространстве...

Одно из направлений - исследование предстандартных состояний при игре в активную Эволюцию, поиск предшественников (предесессоров) различных порядков наперед заданных образований.

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

Предесессоры в игре Эволюция/Жизнь - тема объединяет направление поиска предшественников произвольно наперед заданных конфигураций как в классической Game of Life, так ее расширениях, а также определение предстандартных ситуаций, т.е. тех конфигураций, которые ведут впоследствии к стандартным, в соответствии с целеполаганием - при игре в активную Эволюцию.


Ри. 1. Схема предесессоров текущей конфигурации.

Предшественник данной фигуры F⁰ есть фигура F^-1 , при применении к которой законов эволюции она переходит в фигуру F⁰. Решение этой задачи есть трудоёмкий процесс, для чего, как и ранее, можно использовать ПК. Существуют два пути решения этой проблемы: а) логический, или эвристический; и б) стохастический.

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

Для выполнения первого предположения нужно создать соответствующие условия, а именно: если число соседей у фишки в предыдущем F^-1 поколении равно 1 или 0, то в данном поколении она умирает от одиночества; если больше 3, то в данном поколении она умирает от перенаселённости.

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


Рис. 2. Фигура квадрат 3х3 и ее предшественник.

Текущее поколение F⁰ можно представить в виде двумерной матрицы размером m x n. Поколение F^-1 есть двумерная матрица размером как минимум ( m+1)x( n+1). Задача – найти такое F^-1, чтобы при применении преобразования - прямого алгоритма Конвея, получить исходное поколение.

Ограничениями в данной задаче являются связи a_ij текущего и исходного поколений. Представленные соображения можно развить для случаев F^-2, F^-3…

Соответственно, необходимо иметь в виду, что двумерные матрицы, представляющие соответствующие F, будут как минимум иметь размеры не меньшие ( m+2)x( n+2), ( m+3)x( n+3)…

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

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


Рис. 3. Поиск предшественника (в центре) R-пентамино.

Предстандартные состояния как раздел темы Предесессоры в игре Эволюция/Жизнь. Рассматриваются предстандартные ситуации, т.е. те конфигурации, которые ведут впоследствии к стандартным, в соответствии с целеполаганием - при игре в активную Эволюцию.

Целеполагание в игре - это стабилизация непредсказуемо изменяющейся ситуации на поле посредством сведения игрового паттерна к стандартным образованиям - фигурам блок, улей, бот, плот, корабль...; системам фигур полуогни, огни светофора, двойной блок, пасека... Более полный перечень - см. публикации автора.

В табл. выделена примерная схема направлений развития генерации при реализации такого целеполагания. Отметим, присутствие в индексе нуля (например, F23,0) показывает, что фигура образована вследствие пассивного, естественного хода, т.е. без акта введения-выведения фишки на данном (здесь - втором) этапе преобразований.


Рис. 4. Схема развития конфигураций активной Эволюции.

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

Последовательность преобразования Ц2 >> блок (верхний рис., то же Ц2 >> Ц3 >> улей.



Схема двух светофоров. Если огни светофора - это вовокупность 4-х светофоров, то два - это т.н. полуогни светофора. Т.о., имея последнее, или нечто, приводящее к этому, см. рис. ниже, получаем Ц7 и, в последующем, пасеку.

Последовательность развития схемы двух светофоров.



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

Одним из такого рода исключений является R-пентамино. Целесообразно пресечь неуправляемое развитие фигуры посредством процедуры ее симметрирования и последующего сведения к стандарту.



Комментарий. 1. Удаляется асимметричный элемент слева (выделено). 2. Здесь можно удалить элемент справа >> светофор (вес 3). Но, кажется, лучше - пассивный ход... 3. Удаление фишки слева (выделено) приводит на следующем ходу к стандарту улей (вес 6). 3а. Если не проявлять активность по п. 3, то к 9 ходу имеем огни светофора (вес 12).

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

Принцип симметрии.



Некоторые из таковых дают двойное, симметричное относительно определенной оси рождение, что предпочтительнее, нежели одиночное.

Ряд 1. Добавление фишки здесь (помечено) приводит к блоку (вес 4). Ряд 2. Предпочтительнее такое добавление фишки (помечено), которое вначале приводит к светофору, и, далее, к улью (вес 6).

Продолжение следует... Подробнее по теме см. разд. Предесессоры в меню сайта...