Автоматы. Клеточные автоматы. Библиотека Numpy Составитель Ямилева А. М. кафедра ввтиС

• Название: Библиотека Numpy Составитель Ямилева А. М. кафедра ввтиС
• Анкор: Автоматы
• Дата: 01.11.2022
• Размер: 400.19 Kb.
• Имя файла: Клеточные автоматы.pptx
• Тип: Документы; #765678

Библиотека Numpy

Составитель: Ямилева А.М.

кафедра ВВТиС

Пример использования numpy

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

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

• Клеточный автомат — это модель однородного пространства с некоторыми клетками. Каждая клетка может находиться в одном из нескольких состояний и иметь некоторое количество соседей. Задаются правила перехода из одного состояния в другое в зависимости от текущего состояния клетки и её соседей.

• В 1970 году Джон Конвей придумал игру «Жизнь» («Genesis»), основанную на клеточном автомате, ставшую довольно популярной и повлиявшую на развитие многих точных наук.
• Пространство «Жизни» — бесконечное поле клеток.
• Каждая клетка имеет 8 соседей (сверху, снизу, справа, слева и по диагонали). Клетка может иметь два состояния: живая (на клетке стоит фишка) и мёртвая (фишки нет).

Джон Хортон Конвей

(род. 26 декабря 1937)

Правила игры «Жизнь»

• Время дискретно и считается поколениями.
• Всё начинается с начальной расстановки фишек (0 поколение), в дальнейшем рассматривается эволюция клеточного пространства в 1, 2, 3 и т. д. поколении.
• Процессы смерти и рождения происходят одновременно, после чего строится следующее поколение.
• Если клетка была живой, то она выживет, если у неё 2 или 3 соседа. Если соседей 4, 5, 6, 7 или 8, то она умирает от перенаселённости, если 0 или 1 — то от одиночества.
• Новая клетка рождается в поле, у которого есть ровно 3 соседа.

Правила игры «Жизнь»

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

Начало игры «Жизнь»

population = np.array( [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=np.uint8)

Зададим поле 10 x 10, в центр которого поместим конструкцию, известную как «глайдер». Живые клетки обозначаются единицей, а мёртвые — нулём.

Поле имеет тип uint8. Каждый его элемент занимает ровно 1 байт и является целым беззнаковым (unsigned) числом в диапазоне от 0 до 255.

Подсчет соседей

• Для моделирования бесконечности в обоих направлениях, замкнём поле само на себя – создадим тор.
• Определить количество соседей можно с помощью циклического сдвига.

neighbors = sum([ np.roll(np.roll(population, -1, 1), 1, 0), np.roll(np.roll(population, 1, 1), -1, 0), np.roll(np.roll(population, 1, 1), 1, 0), np.roll(np.roll(population, -1, 1), -1, 0), np.roll(population, 1, 1), np.roll(population, -1, 1), np.roll(population, 1, 0), np.roll(population, -1, 0) ])

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 1 1 1 0 0 0 0]

[0 0 0 1 1 2 1 0 0 0]

[0 0 1 3 5 3 2 0 0 0]

[0 0 1 1 3 2 2 0 0 0]

[0 0 1 2 3 2 1 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

Матрица соседей

Генерация новой популяции

Выполним на матрице логическую операцию: «у клетки 3 соседа».

[[False False False False False False False False False False]

[False False False False False False False False False False]

[False False False False False False False False False False]

[False False False False False False False False False False]

[False False False True False True False False False False]

[False False False False True False False False False False]

[False False False False True False False False False False]

[False False False False False False False False False False]

[False False False False False False False False False False]

[False False False False False False False False False False]]

neighbors == 3

Генерация новой популяции

Выполним на матрице логическую операцию: «если у клетки 2 соседа и она была "жива" в текущем поколении».

population & (neighbors == 2)

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 1 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

Генерация новой популяции

Выполним на матрице следующую операцию: «если у клетки 3 соседа, то в следующем поколении на этом месте будет клетка; а если 2 соседа, то клетка будет при условии, что она была "жива" в текущем поколении».

population = (neighbors == 3) | (population & (neighbors == 2))

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 1 0 1 0 0 0 0]

[0 0 0 0 1 1 0 0 0 0]

[0 0 0 0 1 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

Эволюция глайдера

Проследим эволюцию глайдера на протяжении 4 поколений.

def next_population(population): neighbors = sum([ np.roll(np.roll(population, -1, 1), 1, 0), np.roll(np.roll(population, 1, 1), -1, 0), np.roll(np.roll(population, 1, 1), 1, 0), np.roll(np.roll(population, -1, 1), -1, 0), np.roll(population, 1, 1), np.roll(population, -1, 1), np.roll(population, 1, 0), np.roll(population, -1, 0) ]) return (neighbors == 3) | (population & (neighbors == 2))

population = np.array(…) # здесь должно быть стартовое поле

for _ in range(5): print(population, '\n') population = next_population(population)

Эволюция глайдера

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 1 0 0 0 0 0]

[0 0 0 0 0 1 0 0 0 0]

[0 0 0 1 1 1 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 1 0 1 0 0 0 0]

[0 0 0 0 1 1 0 0 0 0]

[0 0 0 0 1 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 1 0 0 0 0]

[0 0 0 1 0 1 0 0 0 0]

[0 0 0 0 1 1 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 1 0 0 0 0 0]

[0 0 0 0 0 1 1 0 0 0]

[0 0 0 0 1 1 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

[[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 1 0 0 0 0]

[0 0 0 0 0 0 1 0 0 0]

[0 0 0 0 1 1 1 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]

[0 0 0 0 0 0 0 0 0 0]]

Визуализация эволюции

Если еще импортировать библиотеку matplotlib и использовать функцию matshow вместо печати, появятся наглядные диаграммы – картинки.

from matplotlib import pyplot as plt

def next_population(population): neighbors = ... return (neighbors == 3) | (population & (neighbors == 2))

population = np.array(…) # здесь должно быть стартовое поле

for _ in range(5): plt.matshow(population) population = next_population(population)

Визуализация эволюции

Практическая работа

• 1. Реализовать пример из презентации. Сгенерировать 8-12 поколений и отрисовать их на одном графике (figure) matplotlib, используя subplot - получится матрица рисунков.
• 2. Увеличить стартовое поле до 50*50 и реализовать случайное заполнение стартового поля с некоторой вероятностью жизни в клетке. Протестировать на значениях вероятности 10-60% с шагом 5%.
• 3. Поменять клеточный автомат на один из следующих и повторить исследование в п.2:
• "Ассимиляция": рождение при 3, 4, 5 соседях, выживание при 4, 5, 6, 7 соседях
• "Коралл": рождение при 3 соседях, выживание при 4, 5, 6, 7, 8 соседях
• "Пятна": рождение при 3, 6, 7, 8 соседях, выживание при 2, 3, 5, 6, 7, 8 соседях
• "Коагуляция": рождение при 3, 7, 8 соседях, выживание при 2, 3, 5, 6, 7, 8 соседях
• "Города за стенами": рождение при 4, 5, 6, 7, 8 соседях, выживание при 2, 3, 4, 5 соседях
• "Лабиринт": рождение при 3 соседях, выживание при 1, 2, 3, 4, 5 соседях
• "Амеба": рождение при 3, 5, 7 соседях, выживание при 1, 3, 5, 8 соседях