Бюджетное учреждение профессионального образования

Ханты-Мансийского автономного округа - Югры

«Нижневартовский Социально-Гуманитарный колледж»

Программирование и информационные технологии.

Реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.

Работу выполнил:

Студент 2 курса, 214П группы

Ганжа Сергей Алексеевич

Руководитель работы:

Окунцев Павел Владимирович

Оглавление

Введение.        

Глава 1. Среда разработки клеточного автомата.        

1.1. Клеточный автомат.        

1.2. Игра «Жизнь».        

Глава 2. Код программы и реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.        

Заключение        

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

Введение.

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

Актуальность исследования:

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

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

С помощью клеточного автомата «Жизнь» возможно усовершенствование и проведение исследований по "Искусственной жизни" (Artificial Life), а это уже разработка в дальнейшем искусственного интеллекта. 

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

Актуальность создания искусственного интеллекта в настоящее время связана со сложностью проблем, которые приходится решать современному человечеству. К таким проблемам можно отнести освоение космоса, прогнозирование природных катаклизмов и антропогенного воздействия на окружающую среду, создание сложнейших инженерных проектов, использование современной техники в медицине и многие научные исследования. [6]

Проблема:

Проблема сознания заключается в парадоксальной ситуации: мы, разумные существа, обладаем сознанием, оно у нас есть, но мы не знаем что такое сознание. Мамардашвили, определяя эту ситуацию, писал: «Сознание - это парадоксальность, к которой невозможно привыкнуть». Раскрывая особенность парадоксальности сознания, он указывал на две трудности в изучении сознания. Первая состоит в том, что само понятие «сознание» является предельным философским понятием, таким как понятие «бытие». А такого рода понятия не поддаются классическому родовидовому определению. Другая трудность проистекает из того, что сознание «весьма странное явление, которое есть и которое в то же время нельзя ухватить, представить как вещь». Однако есть еще одно обстоятельство, делающее проблему сознания особенно сложной [2].

Объект исследования является использование методов и алгоритмов прогнозирования на основе компьютерного имитационного моделирования и разработка клеточного автомата «Жизнь».

Предмет исследования: изучение высокоуровневых языков программирования Basic-семействах и совершенствование навыков работы в коммерческом игровом движке Blitz3D при разработке клеточного автомата «Жизнь».

Цель: разработка клеточного автомата «Жизнь», а также построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.

Задачи исследования:   

1. Изучить работы по данной теме, опубликованные в научных изданиях.
2. Разработать микромодель с установленными правилами на основе клеточного автомата.
3. Реализовать клеточную модель в виде компьютерной программы.
4. Провести ряд  экспериментов с приложением, иллюстрируя различные процессы, происходящие на разных участках клеточного автомата «Жизнь».

Глава 1. Среда разработки клеточного автомата.

Basic-семейство высокоуровневых языков программирования. Бейсик был придуман в 1963 году преподавателями Дартмутского Колледжа Джоном Кемени и Томасом Куртцом и реализован командой студентов колледжа под их руководством. Со временем, когда стали появляться другие диалекты, этот «изначальный» диалект стали называть Dartmouth BASIC [1].

Blitz3D - коммерческий игровой движок, разработанный Марком Сибли, а также среда разработки с языком Blitz BASIC и скриптовый язык для создания игр. Язык содержит 588 конструкций, позволяющих создать двух- и трёхмерное игровое пространство. С помощью него можно создавать небольшие игры, используя большое количество библиотек, написанных членами сообществ по программированию на Blitz3D [6].

1.1. Клеточный автомат.

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

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

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

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

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

Отметим основные свойства классической модели клеточных автоматов.

1. Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама;
2. Однородность системы. Ни одна область решётки не может быть отличена от другой по каким-либо особенностям правил и т.п. Однако на практике решётка оказывается конечным множеством клеток (ведь не возможно выделить неограниченный объём данных).
3. Множество возможных состояний клетки - конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций. Отметим, что оно не мешает использовать клетки для хранения чисел с плавающей точкой при решении прикладных задач.
4. Значения во всех клетках меняются единовременно, в конце итерации, а не по мере вычисления. В противном случае порядок перебора клеток решётки, при совершении итерации, существенно влиял бы на результат. Необходимо отметить, что на практике, при решении определённых задач, возникает потребность в том, чтобы отказаться от последних трёх свойств.

Клеточный автомат состоит из набора объектов (ячеек), обычно образующих регулярную решетку.

Состояние отдельно взятого i-го объекта (или ячейки) в момент времени n характеризуется некоторой переменной, которая может быть целым, действительным или комплексным числом, либо представлять собой набор из нескольких чисел.

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

Клеточные автоматы можно разделить на:                 

1. Детерминированные;
2. Вероятностные;
3. Подвижные;
4. Неподвижные;
5. Однородные;
6. Неоднородные.

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

Это позволяет моделировать на их основе или решать с их помощью самые разнообразные задачи:

1. моделирование химических и физических процессов, 
2. проведение исследований по "Искусственной жизни" (Artificial Life) 
3. исследование биологических процессов 
4. моделирование распространения слухов 
   и т.д.[12]

1.2. Игра «Жизнь».

Игра «Жизнь»- клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Она может эмулировать универсальную машину Тьюринга. Таким образом возможно построить автомат, в котором глайдеры (сочетания клеток, движущиеся по сетке как единое целое) будут выполнять некоторые вычисления[13].

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

• "Соседи" клетки - клетки, располагающиеся в непосредственной близости от данной;
• количество ходов, прошедших от начала игры;
• свойства самой клетки и т.д.

Правила игры:

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

Джон Конвей много экспериментировал с этими параметрами и остановился на следующем:

• Соседями клетки являются все восемь клеток, имеющих либо общую сторону, либо общую вершину.
• Клетка рождается, если количество соседей равно 3.
• Клетка умирает, если количество соседей либо больше 3 (перенаселение), либо меньше 2 (одиночество).

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

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

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

Остальные триплеты (без учета ориентации) исчезают на первом же ходу.

Первые три конфигурации на втором ходу погибают. Относительно третей конфигурации заметим, что любой диагональный ряд клеток с каждым ходом с каждого конца по клетке. Четвертая конфигурация на втором ходу переходит в устойчивую конфигурацию "Блок". Пятая конфигурация является циклической - она повторяет себя каждые 2 хода - "Мигалка" [3].

Фигуры:

1. Устойчивые фигуры: фигуры, которые остаются неизменными
2. Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений
3. Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением
4. Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура
5. Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур
6. Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами [12]

Примеры конфигураций [11]:

Глава 2. Код программы и реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.

SeedRnd MilliSecs()

Const mt$="Клеточный автомат ЖИЗНЬ"

Const mw=325

Const mh=200

Dim a(mw,mh)

Dim b(mw,mh)

Global li

Global t

AppTitle mt$

Graphics 1024,768,32,2

fnt=LoadFont("Arial",32,0,0,0)

SetFont fnt

model_r()

While Not KeyDown(1)

        Color 0,90,150

        Rect 0,0,1024,768

        model_n()

        model_s()

        Text 20 ,640,"N"

        Text 100,640,li

        Text 20 ,670,"T"

        Text 100,670,t

        Rect 10,10,1004,720,0

        Rect 10,10,1004,620,0

        If KeyHit(57) Then model_r()

Wend

Function model_s()

        Color 0,255,0

        For y=1 To mh

                For x=1 To mw

                        If a(x,y)=1 Then Rect 20+x*3,20+y*3,2,2

                Next

        Next

End Function

Function model_n()

For y=1 To mh

        For x=1 To mw

                bx1=x-1

                bx2=x+1

                If x=1  Then bx1=mw

                If x=mw Then bx2=1

                by1=y-1

                by2=y+1

                If y=1  Then by1=mh

                If y=mh Then by2=1

                ss=a(bx1,by1)+a(x,by1)+a(bx2,by1)+a(bx1,y)+a(bx2,y)+a(bx1,by2)+a(x,by2)+a(bx2,by2)

                If ss<2 Then b(x,y)=0

                If ss>3 Then b(x,y)=0

                If ss=3 Then b(x,y)=1

        Next

Next

li=0

For y=1 To mh

        For x=1 To mw

                a(x,y)=b(x,y)

                If a(x,y) Then li=li+1

        Next

Next

t=t+1

End Function

Function model_r()

        t=0

        For y=1 To mh

                For x=1 To mw

                        If Rand(100)>50 Then a(x,y)=1 Else a(x,y)=0

                Next

        Next

End Function

Программа представляет собой следующий интерфейс:

Клетки размножаются, согласно правилам игры. Эта игра показывает эволюцию из клетки в какой-либо организм.

Программу можно усложнять, добавляя в нее новые правила

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

Заключение

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

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

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

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

Отметим еще одно применение клеточных автоматов - сжатие данных (или просто шифрование). Пусть нам дано некое расположение значений, содержащихся в клетках в пространстве автомата. Пусть через k шагов получается конфигурация, которая каким-то образом может быть преобразована в файл. Если затраты на хранение получившейся системы клеток больше, чем на то, что нам необходимо значит произошло сжатие.

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

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

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

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

Клеточные автоматы можно использовать при составлении генетических алгоритмов.

Таким образом, действительно, клеточные автоматы нашли и находят широкое применение во многих сферах человеческой деятельности, многие из которых стало возможным решить только с помощью компьютера [3].

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

1. BASIC http://progopedia.ru/language/basic/
2. «Шаг за шагом» создание искусственного интеллекта гашева Светлана http://lib.znate.ru/docs/index-216414.html 
3. Методическое пособие по информатике для 10-11 классов Лицея прикладных наук.
4. www.aiportal.ru
5. Методы искусственного интеллекта для принятия решений и прогнозирования поведения динамических систем http://cyberleninka.ru/article/n/metody-iskusstvennogo-intellekta-dlya-prinyatiya-resheniy-i-prognozirovaniya-povedeniya-dinamicheskih-sistem 
6. https://ru.wikipedia.org/wiki/Blitz_BASIC 
7. Статья на научно-популярном портале GeniusLand
8. https://habrahabr.ru/post/237629/
9. Клеточные автоматы с последовательным перебором возможных состояний. Аппаратная реализация и использование для моделирования нейронных сетей и других структур параллельных вычислений. http://dmitry.bancorp.ru/caslops/
10.  Клеточный автомат https://ru.wikipedia.org/wiki/Клеточный автомат
11.  http://theoryandpractice.ru/posts/7857-golenkov
12.  Лектор – Склярова Елена Александровна Курс: Элементы http://rushkolnik.ru/docs/114/index-2849629.html 
13.  Игра «Жизнь»  https://ru.wikipedia.org/wiki/Жизнь_(игра)