Название работы: Реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.
Фамилия и имя автора: Ганжа Сергей.
Краткое название образовательное организации: БУ «Нижневартовский социально-гуманитарный колледж».
Город: Нижневартовск.
Актуальность исследования: Тема клеточных автоматов очень актуальна, т.к. может привести к разгадкам многих вопросов в окружающем мире. Например: игра "Жизнь" была применена для анализа социально-экономических схем и применялась к вопросу о спиралевидности большинства галактик.
Клеточные автоматы применимы не только в математике, физике, биологии. Теория клеточных автоматов наиболее перспективно прилагаема к вопросу о разработке самовосстанавливаемых электронных цепей и других науках.
С помощью клеточного автомата «Жизнь» возможно усовершенствование и проведение исследований по "Искусственной жизни" (Artificial Life), а это уже разработка в дальнейшем искусственного интеллекта.
Проблема создания искусственного интеллекта не такая современная, как кажется, поскольку человек с древних времён стремился упростить свою жизнь, переложив часть своих обязанностей на специальные приспособления. Раньше этот вопрос ограничивался созданием машин или роботов, способных выполнять тяжёлую физическую работу. Но с развитием науки человек всё чаще стал задумываться о создании машины, способной выполнять и умственную работу.
Актуальность создания искусственного интеллекта в настоящее время связана со сложностью проблем, которые приходится решать современному человечеству. К таким проблемам можно отнести освоение космоса, прогнозирование природных катаклизмов и антропогенного воздействия на окружающую среду, создание сложнейших инженерных проектов, использование современной техники в медицине и многие научные исследования.
Объект исследования является использование методов и алгоритмов прогнозирования на основе компьютерного имитационного моделирования и разработка клеточного автомата «Жизнь».
Предмет исследования: изучение высокоуровневых языков программирования Basic-семействах и совершенствование навыков работы в коммерческом игровом движке Blitz3D при разработке клеточного автомата «Жизнь».
Цель исследования: разработка клеточного автомата «Жизнь», а также построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.
Задачи исследования:
1. Изучить работы по данной теме, опубликованные в научных изданиях.
2. Разработать микромодель с установленными правилами на основе клеточного автомата.
3. Реализовать клеточную модель в виде компьютерной программы.
4. Провести ряд экспериментов с приложением, иллюстрируя различные процессы, происходящие на разных участках клеточного автомата «Жизнь».
Вложение | Размер |
---|---|
statya.docx | 138.04 КБ |
Бюджетное учреждение профессионального образования
Ханты-Мансийского автономного округа - Югры
«Нижневартовский Социально-Гуманитарный колледж»
Программирование и информационные технологии.
Реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.
Работу выполнил:
Студент 2 курса, 214П группы
Ганжа Сергей Алексеевич
Руководитель работы:
Окунцев Павел Владимирович
Оглавление
Глава 1. Среда разработки клеточного автомата.
Глава 2. Код программы и реализация клеточного автомата «Жизнь» в среде разработки Blitz3D.
Клеточный автомат представляет собой совокупность пространства, поделенного на клетки, в каждой из которых содержится некое значение, и правил, задающих закон преобразования при совершении шага. Это пространство может быть как плоскостью, так и любым N-мерным пространством. Действие происходит с помощью моделирования искусственного интеллекта.
Актуальность исследования:
Тема клеточных автоматов очень актуальна, т.к. может привести к разгадкам многих вопросов в окружающем мире. Например: игра "Жизнь" была применена для анализа социально-экономических схем и применялась к вопросу о спиралевидности большинства галактик.
Клеточные автоматы применимы не только в математике, физике, биологии. Теория клеточных автоматов наиболее перспективно прилагаема к вопросу о разработке самовосстанавливаемых электронных цепей и других науках.
С помощью клеточного автомата «Жизнь» возможно усовершенствование и проведение исследований по "Искусственной жизни" (Artificial Life), а это уже разработка в дальнейшем искусственного интеллекта.
Проблема создания искусственного интеллекта не такая современная, как кажется, поскольку человек с древних времён стремился упростить свою жизнь, переложив часть своих обязанностей на специальные приспособления. Раньше этот вопрос ограничивался созданием машин или роботов, способных выполнять тяжёлую физическую работу. Но с развитием науки человек всё чаще стал задумываться о создании машины, способной выполнять и умственную работу.
Актуальность создания искусственного интеллекта в настоящее время связана со сложностью проблем, которые приходится решать современному человечеству. К таким проблемам можно отнести освоение космоса, прогнозирование природных катаклизмов и антропогенного воздействия на окружающую среду, создание сложнейших инженерных проектов, использование современной техники в медицине и многие научные исследования. [6]
Проблема:
Проблема сознания заключается в парадоксальной ситуации: мы, разумные существа, обладаем сознанием, оно у нас есть, но мы не знаем что такое сознание. Мамардашвили, определяя эту ситуацию, писал: «Сознание - это парадоксальность, к которой невозможно привыкнуть». Раскрывая особенность парадоксальности сознания, он указывал на две трудности в изучении сознания. Первая состоит в том, что само понятие «сознание» является предельным философским понятием, таким как понятие «бытие». А такого рода понятия не поддаются классическому родовидовому определению. Другая трудность проистекает из того, что сознание «весьма странное явление, которое есть и которое в то же время нельзя ухватить, представить как вещь». Однако есть еще одно обстоятельство, делающее проблему сознания особенно сложной [2].
Объект исследования является использование методов и алгоритмов прогнозирования на основе компьютерного имитационного моделирования и разработка клеточного автомата «Жизнь».
Предмет исследования: изучение высокоуровневых языков программирования Basic-семействах и совершенствование навыков работы в коммерческом игровом движке Blitz3D при разработке клеточного автомата «Жизнь».
Цель: разработка клеточного автомата «Жизнь», а также построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.
Задачи исследования:
Basic-семейство высокоуровневых языков программирования. Бейсик был придуман в 1963 году преподавателями Дартмутского Колледжа Джоном Кемени и Томасом Куртцом и реализован командой студентов колледжа под их руководством. Со временем, когда стали появляться другие диалекты, этот «изначальный» диалект стали называть Dartmouth BASIC [1].
Blitz3D - коммерческий игровой движок, разработанный Марком Сибли, а также среда разработки с языком Blitz BASIC и скриптовый язык для создания игр. Язык содержит 588 конструкций, позволяющих создать двух- и трёхмерное игровое пространство. С помощью него можно создавать небольшие игры, используя большое количество библиотек, написанных членами сообществ по программированию на Blitz3D [6].
Клеточный автомат представляет собой совокупность пространства, поделенного на клетки, в каждой из которых содержится некое значение, и правил, задающих закон преобразования при совершении шага. Это пространство может быть как плоскостью, так и любым N-мерным пространством. Действие происходит с помощью моделирования искусственного интеллекта [12].
Интеллект - в широком смысле вся познавательная деятельность человека, в более узком - мышление, а также способность рационального познания в отличие от таких, например, душевных способностей, как чувства, воля, интуиция, воображение и т.п.
Как правило, рассматриваются автоматы, где состояние определяется самой клеткой и ближайшими соседями. В качестве решетки обычно рассматривается кубическая решетка.
Клеточный автомат можно представить, как регулярную решетку (или "таблицу") ячеек ("клеток"), каждая из которых может находиться в конечном числе возможных состояний, например 0 или 1. Состояние системы полностью определяется значениями переменных в каждой клетке. Важными особенностями клеточных автоматов являются следующие:
Отметим основные свойства классической модели клеточных автоматов.
Клеточный автомат состоит из набора объектов (ячеек), обычно образующих регулярную решетку.
Состояние отдельно взятого i-го объекта (или ячейки) в момент времени n характеризуется некоторой переменной, которая может быть целым, действительным или комплексным числом, либо представлять собой набор из нескольких чисел.
Рассматриваемые состояния ячеек изменяются синхронным образом через дискретные интервалы времени в соответствии с локальными вероятностными правилами, которые могут зависеть от состояния переменных в ближайших соседних узлах. Эти правила не меняются со временем.
Клеточные автоматы можно разделить на:
Клеточные автоматы предоставляют большую свободу в выборе структуры и правил развития системы.
Это позволяет моделировать на их основе или решать с их помощью самые разнообразные задачи:
Игра «Жизнь»- клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Она может эмулировать универсальную машину Тьюринга. Таким образом возможно построить автомат, в котором глайдеры (сочетания клеток, движущиеся по сетке как единое целое) будут выполнять некоторые вычисления[13].
Представим себе некоторое однородное пространство, состоящее из клеток. Каждая клетка обладает несколькими состояниями, которые могут зависеть от следующих параметров:
Правила игры:
Джон Конвей много экспериментировал с этими параметрами и остановился на следующем:
В процессе игры популяция непрестанно претерпевает необычные, нередко очень красивые и всегда неожиданные изменения. Иногда первоначальная колония организмов вымирает, но, в большинстве своем, исходные конфигурации либо переходят в устойчивые и перестают изменяться, либо переходят в колебательный режим. Наблюдается тенденция к приобретению симметрии конфигурациями, которых на первый взгляд, никак не назвать симметричными.
Для начала условимся классифицировать конфигурации по следующим параметрам:
1) По количеству клеток в комбинации: единичная клетка, дуплет, триплет и т.д.
2) По перспективе развития: развивающиеся, стабильные, вымирающие.
3) По расположению клеток относительно друг друга.
Очевидно, что конфигурация, состоящая из одной клетки, как и любая пара клеток, расположенных по горизонтали, вертикали, или диагонали, погибает на первом же ходу, поэтому рассмотрим простейшие конфигурации, состоящие из 3 клеток, и проследим их эволюцию в течение нескольких ходов.
Остальные триплеты (без учета ориентации) исчезают на первом же ходу.
Первые три конфигурации на втором ходу погибают. Относительно третей конфигурации заметим, что любой диагональный ряд клеток с каждым ходом с каждого конца по клетке. Четвертая конфигурация на втором ходу переходит в устойчивую конфигурацию "Блок". Пятая конфигурация является циклической - она повторяет себя каждые 2 хода - "Мигалка" [3].
Фигуры:
Примеры конфигураций [11]:
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].
Рисуем лошадь акварелью
Сила слова
Лиса и волк
Как напиться обезьяне?
Ребята и утята