Игра Дж. Конвея "Жизнь" и SimPy

Моделирование динамики биологических систем — занятие очень увлекательное, а иногда и полезное. И польза от этого, может иметь вполне фундаментальное научное значение. Примером такой поучительной модели по праву можно назвать игру "Жизнь" Джона Конвея, предложенную вначале 70-х годов прошлого столетия (тысячелетия :).

В чем, собственно, интерес и значение данной игры?! Рассмотрим правила игры "Жизнь", чтобы подробней разобраться в ее ценности.

Игра жизнь: Simpy

Основу игры "Жизнь" составляют следующие незамысловатые правила:

  • Место действия этой игры —  размеченная на клетки поверхность или плоскость; при этом возможны  варианты — безграничного, ограниченного, или замкнутого ареалов; далее при моделировании мы рассмотрим случай ограниченного ареала;
  • Каждая клетка на поверхности может находиться в двух состояниях: быть «живой» или быть «мёртвой» (пустой).
  • Игра начинается с задания начального распределения "живых" клеток на заданном ареале, при этом следующее поколение рассчитывается на основе предыдущего по правилам:
    • в пустой (неживой) клетке, имеющей в качестве соседей три живые клетки, зарождается жизнь;
    • если у живой клетки в соседстве есть две или три живые клетки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»);
  • Игра прекращается, если на поле не останется ни одной «живой» клетки, если при очередном шаге ни одна из клеток не меняет своего состояния (складывается стабильная конфигурация) или если конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация).

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

Игра жизнь, интересная конфигурация

На данном gif-рисунке черными квадратами обозначены "живые" клетки; с течением времени — картинка меняется — текущая конфигурация живых клеток порождает новые конфигурации, и они весьма нетривиальны!

Несмотря на то, что правила игры вполне могут интерпретироваться, как реалистичные, ценность игры заключается в том, что простые правила могут являться источником таких сложных конфигураций. Этот пример очень поучителен. Представим себе, что мы не знаем этих "простых" правил и наблюдаем данную меняющуюся со временем конфигурацию "в природе". Здесь и не долго поверить в какой-то высший смысл в динамике такой системы, а в действительности — смысл-то может быть очень простым! Это, на мой взгляд, один из важнейших выводов данной игры, предостерегающий исследователя от желания искать тайный смысл, а в первую очередь попытаться объяснить наблюдаемое простыми вещами.

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

Существует большое число реализаций данной игры, и не составляет труда загрузить уже готовое решение; более того, использование SimPy для данной цели — не совсем подходящее решение (или по крайней мере в моей реализации), приводящее к большому объему "ненужной" вычислительной работы программы. Положительным моментом, однако, является то, что SimPy позволяет иначе взглянуть на игру, описать ее как совокупность параллельно запущенных событий, которые описывают поведение каждой клетки в отдельности.

# -*- coding: utf-8 -*-

# Будем приобщаться к стилю Python 3...
from __future__ import print_function
from itertools import product
from copy import deepcopy

# Импорт среды SimPy
import simpy

# Инициализация среды моделирования
env = simpy.Environment()

class Cell(object):
    '''Клетка пространства с 2-мя состояниями: state=True -- присутствует жизнь в клетке,
    state=False -- жизнь в клетке отсутствует; 
    '''
    def __init__(self, x, y, state=False):
        self.x = x
        self.y = y
        self.state = state

    def count_neighbors(self, pool):
        '''Подсчитывает число соседних клеток, в которых присутствует жизнь.'''
        return len([1 for z in set(self.ij_keys()).intersection(set(pool.keys())) if pool[z].state])

    def run(self, pool):
        c = self.count_neighbors(pool)
        if c == 2: 
            pass
        elif c==3:
            self.state=True
        else:
            self.state = False
    
    def ij_keys(self):
        '''Возвращает список соседних клеток к текущей'''
        i, j = self.x, self.y
        return [(i+1, j), (i, j+1), (i-1, j), (i, j-1), (i+1, j+1), (i+1, j-1), (i-1, j+1), (i-1,j-1)]

Класс Cell описывает отдельно взятую клетку и имеет метод run, который изменяет ее состояние в соответствии с правилами игры. Рассмотрим далее все клетки некоторой ограниченной области pool (данная переменная будет содержать все клетки из ограниченной области, поведение которых мы будем моделировать).
 

pool = {}  # Здесь будут храниться клетки
# Добавим во множество отслеживамых клеток все клетки c координатами -2..3
for x,y in product(range(-2, 4), range(-2, 4)):
    pool.update({(x, y): Cell(x, y)})
# Формат pool - прост: (положение клетки): клетка; положение клетки
# ключ словаря, ключ -- пара, характеризующая положение клетки


# Добавим несколько живых клеток, иначе никакой динамики не будет
init1 = Cell(0, 0, state=True)
init2 = Cell(0, 1, state=True)
init3 = Cell(0, 2, state=True)
init4 = Cell(1, 2, state=True)
pool.update({(0, 0): init1, (0, 1): init2, (0, 2): init3, (1, 2):init4})

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

# Основная функция, которая описывает эволюций множества клеток; на каждом шаге
# для каждой клетки провряются правила образования жизни конвея
# в соответствии с этими правилами изменяется статус клеток (присутствует\отсутствует жизнь
def pool_updater():
    while True:
        # нужно сделать полную копию набора клеток, 
        # и оценивать близость и наличие жизни только по этому
        # набору. Иначе изменение каждой клетки будет влиять на
        # результаты трансформирования соседних
        _pool = deepcopy(pool)
        for key in pool.keys():
            __pool = deepcopy(_pool)
            pool[key].run(__pool)
        # Шаг закончен, перейти к следующему, изменив время на единицу
        yield env.timeout(1)    

Заключительным этапом будет отрисовка результатов вычислений.

# Отрисовываем результаты, если установлен matplotlib

try:
    from pylab import *
    def plot_pool(pool):
        x=[]
        y=[]
        for item in pool.keys():
            if pool[item].state:
                x.append(pool[item].x)
                y.append(pool[item].y)
        scatter(x, y, marker='o')
    plot_pool(pool)
    show()
except ImportError:
    # Пакет matplotlib не установлен -- отдыхаем...
    pass

При запуске 

данного варианта (4,4 KB)

  скрипта можно получить набор png файлов, которые описывают нашу популяцию живых клеток с течением времени. Для удобства набор картинок лучше преобразовать в gif-анимацию (если установлен пакет ImageMagick это нетрудно сделать выполнив convert -delay 120 -loop 0 *.png animated.gif). В результате, получим следующее:

Игра жизнь, Matplotlib, SimPy

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

blog comments powered by Disqus