Файл: Интеллектуальные системы.pdf

111 lastmove[i]=move if move==0: location[i][0]-=1
# Доска ограничена if location[i][0]<0: location[i][0]=0 if move==1: location[i][0]+=1 if location[i][0]>max[0]: location[i][0]=max[0] if move==2: location[i][1]-=1 if location[i][1]<0: location[i][1]=0 if move==3: location[i][1]+=1 if location[i][1]>max[1]: location[i][1]=max[1]
# Если противник захвачен в плен, вы выиграли if location[i]==location[1-i]: return i return -1
Программа возвращает 0, если выиграл первый игрок, 1 – если второй, и –1 – в случае ничьей. Попробуйте создать две случайные программы и заставить их сыграть между собой: import gp p1=gp.makerandomtree(5) p2=gp.makerandomtree(5) gp.gridgame([p1,p2])
Программы ещё не подвергались эволюции, поэтому, скорее все- го, они будут проигрывать, делая два хода подряд в одном направле- нии. В идеале эволюционировавшая программа должна понять, что так делать нельзя.
Круговой турнир
Следуя идеологии коллективного разума, надо было бы проверять пригодность программ в игре против людей и соответственно прово- дить эволюцию. Было бы замечательно учесть при разработке «умной» программы поведение тысяч людей. Но при большой популяции и многих поколениях пришлось бы сыграть десятки тысяч игр, в боль- шинстве своём с очень слабыми противниками. На практике это нере-

112 ализуемо, поэтому сначала мы разовьём программы, заставив их со- стязаться друг с другом на турнире.
Функция tournament принимает на входе список игроков и орга- низует игру каждого из них со всеми другими, отслеживая, сколько раз каждая программа проиграла. За проигрыш программе начисляется два очка, за ничью – одно. def tournament(pl):
# Массив для подсчета проигрышей losses=[0 for p in pl]
# Каждый игрок встречается со всеми другими for i in range(len(pl)): for j in range(len(pl)): if i==j: continue
# Кто выиграл? winner=gridgame([pl[i],pl[j]])
# Два очка за поражение, одно за ничью if winner==0: losses[j]+=2 elif winner==1: losses[i]+=2 elif winner==-1: losses[i]+=1 losses[i]+=1 pass
# Отсортировать и вернуть результаты z=zip(losses,pl) z.sort( ) return z
В конце функция сортирует результаты и возвращает их вместе с программами, которые потерпели меньше всего поражений. Именно эта информация необходима функции evolve, чтобы организовать эво- люцию, поэтому функция tournament может использоваться в качестве аргумента evolve, следовательно, у вас всё готово для выбора про- граммы-победителя. Выполните в интерактивном сеансе следующие команды (на это может уйти заметное время): import gp winner=gp.evolve(5,100,gp.tournament,maxgen=50)

113
Игра с человеком
Вы получили в ходе эволюции программу, которая победила всех своих кибернетических соперников. Теперь самое время сыграть с ней самому.
Класс humanplayer: class humanplayer: def evaluate(self,board):
# Получить мою позицию и позиции других игроков me=tuple(board[0:2]) others=[tuple(board[x:x+2]) for x in range(2,len(board)-1,2)]
# Нарисовать доску for i in range(4): for j in range(4): if (i,j)==me: print 'O', elif (i,j) in others: print 'X', else: print '.', print
# Показать ходы, для справки print 'Ваш последний ход %d' % board[len(board)-1] print ' 0' print '2 3' print ' 1' print 'Введите ход: ',
# Вернуть введенное пользователем число move=int(raw_input( )) return move
Начинайте игру в интерактивном сеансе: import gp gp.gridgame([winner,gp.humanplayer( )])
. O . .
. . . X
Ваш последний ход -1

114 0
2 3 1
Введите ход:
Если программа хорошо эволюционировала, то победить её будет довольно трудно. Ваша программа почти наверняка научилась не хо- дить два раза подряд в одном направлении, поскольку это влечёт не- медленную гибель, но то, в какой мере она освоила другие стратегии, зависит от конкретного прогона evolve.
Содержание отчёта:
1. Титульный лист.
2. Цель лабораторной работы.
3. Скриншоты результатов работы программы
Контрольные вопросы

1. Что такое генетическое программирование?
2. Что такое генетический алгоритм?

3. Что такое мутация?
4. Что такое скрещивание?
Список литературы
1. Тоби Сегаран. Программируем коллективный разум.
2. Марк Лутц. Изучаем Python.

115
Лабораторная работа №11. Игра «Жизнь»
Цель работы: Ознакомиться с игрой «Жизнь»
Введение
Игра "Жизнь", придуманная американским математиком Дж. Ко- нуэем, уже несколько десятков лет привлекает к себе пристальное внимание. Созданы десятки программ, реализующих эту игру чуть ли не на всех типах компьютеров, написаны тысячи статей, десятки сай- тов в Интернете посвящены этой игре.
Для игры "Жизнь" вам не понадобится партнёр - в неё можно иг- рать и одному. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний живых организмов. По этой причине "Жизнь" можно отнести к быстро развивающейся категории так называемых "модели- рующих игр" - игр, которые в той или иной степени имитируют про- цессы, происходящие в реальной жизни.
Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения фишек (организмов), расставленных по раз- личным клеткам доски, проследить за эволюцией исходной позиции под действием "генетических законов" Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подби- рал свои правила и долго проверял их "на практике", добиваясь, чтобы они по возможности удовлетворяли трём условиям:
1. не должно быть ни одной исходной конфигурации, для кото- рой существовало бы простое доказательство возможности неограниченного роста популяции;
2. в то же время должны существовать такие начальные конфи- гурации, которые заведомо обладают способностью беспре- дельно развиваться;
3. должны существовать простые начальные конфигурации, ко- торые в течение значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих трёх способов: полностью ис- чезают (либо из-за перенаселённости, т. е. слишком большой плотности фишек, либо, наоборот, из-за разрежённости фи- шек, образующих конфигурацию); переходят в устойчивую конфигурацию и перестают изменяться вообще или же, нако- нец, выходят на колебательный режим, при котором они со-

116 вершают некий бесконечный цикл превращений с определён- ным периодом.
Короче говоря, правила игры должны быть такими, чтобы пове- дение популяции было достаточно интересным, а главное, непредска- зуемым.
Генетические законы Конуэя удивительно просты. Прежде чем мы их сформулируем, обратим внимание на то, что каждую клетку доски (которая, вообще говоря, считается бесконечной) окружают во- семь соседних клеток: четыре имеют с ней общие стороны, а четыре другие - общие вершины. Правила игры (генетические законы) сводят- ся к следующему:
1. выживание. Каждая фишка, у которой имеются две или три соседние фишки, выживает и переходит в следующее поколе- ние;
2. гибель. Каждая фишка, у которой оказывается больше трёх со- седей, погибает, т. е. снимается с доски, из-за перенаселённо- сти. Каждая фишка, вокруг которой свободны все соседние клетки или же занята только одна клетка, погибает от одино- чества;
3. рождение. Если число фишек, с которыми граничит какая- нибудь пустая клетка, в точности равно трём (не больше и не меньше), то на этой клетке происходит рождение нового "ор- ганизма", т. е. следующим ходом на неё ставится одна фишка.
Важно понять, что гибель и рождение всех "организмов" проис- ходят одновременно. Вместе взятые, они образуют одно поколение или, как мы будем говорить, один "ход" в эволюции начальной конфи- гурации.
Начав игру, вы сразу заметите, что популяция непрестанно пре- терпевает необычные, нередко очень красивые и всегда неожиданные изменения. Иногда первоначальная колония организмов постепенно вымирает, т. е. все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится очень много поколений. В большинстве своём исходные конфигурации либо переходят в устой- чивые (последние Конуэй называет "любителями спокойной жизни") и перестают изменяться, либо навсегда переходят в колебательный ре- жим. При этом конфигурации, не обладавшие в начале игры симмет- рией, обнаруживают тенденцию к переходу в симметричные формы.

117
Обретённые свойства симметрии в процессе дальнейшей эволюции не утрачиваются, а симметрия конфигурации может лишь обогащаться.
Конуэй высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти. Иначе говоря, любая конфигурация, состоящая из конечного числа фишек, не может перейти в конфигурацию, у которой число фишек превосходило бы некий конечный верхний предел. Это, наверное, наиболее глубокая и самая сложная задача, возникающая в игре "Жизнь". В своё время
Конуэй предлагал премию в 50 долларов тому, кто до конца 1970 г. первым докажет или опровергнет его гипотезу. Опровергнуть предпо- ложение Конуэя можно было бы, например, построив конфигурацию, к которой, следуя правилам игры, всё время приходилось бы добавлять новые фишки. К ним можно отнести, в частности, "ружьё" (конфигу- рацию, которая через определённое число ходов "выстреливает" дви- жущиеся фигуры вроде "глайдера") или "паровоз, пускающий дым из трубы" (движущаяся конфигурация, оставляющая за собой "клубы дыма").
Задание
1) Нарисовать указанные на рис. 1 конфигурации. Описать их поведение (например, записать шаг, на котором конфигурация переходит в устойчивое состояние, исчезает, возвращается в исходное состояние и т.д.). Описание сопроводить скриншо- том.
Рис. 39 2) Нарисовать линию из 5 горизонтальных клеток. Описать их поведение (например, записать шаг, на котором конфигурация

118 переходит в устойчивое состояние, исчезает, возвращается в исходное состояние и т.д.). Описание сопроводить скриншо- том.
3) Проделать п.2 для линий, состоящих из 6, 7, … 20 клеток.
4) Нарисовать конфигурацию, изображённую на рис.2. Сделать скриншот финальной конфигурации.
Рис. 40 5) Поэкспериментируйте с разными конфигурациями.
Содержание отчёта:
1. Титульный лист.
2. Цель лабораторной работы.
3. Скриншоты результатов работы программы
Контрольные вопросы:

1. Что такое игра «Жизнь»?
2. Условия, которым должны удовлетворять правила Конуэя
3. Правила игры (генетические законы) игры.

119
Лабораторная работа №12. Построение графа экспертной системы
Цель работы: Научиться строить графы экспертной системы
Введение
Назначение экспертных систем заключается в решении достаточ- но трудных для экспертов задач на основе накапливаемой базы знаний, отражающей опыт работы экспертов в рассматриваемой проблемной области. Достоинство применения экспертных систем заключается в возможности принятия решений в уникальных ситуациях, для которых алгоритм заранее не известен и формируется по исходным данным в виде цепочки рассуждений (правил принятия решений) из базы зна- ний. Причём решение задач предполагается осуществлять в условиях неполноты, недостоверности, многозначности исходной информации и качественных оценок процессов.
Экспертная система является инструментом, усиливающим ин- теллектуальные способности эксперта, и может выполнять следующие роли:
 консультанта для неопытных или непрофессиональных поль- зователей;
 ассистента в связи с необходимостью анализа экспертом раз- личных вариантов принятия решений;
 партнёра эксперта по вопросам, относящимся к источникам знаний из смежных областей деятельности.
Экспертные системы используются во многих областях, среди ко- торых лидирует сегмент приложений в бизнесе.
Домашнее задание студентам для подготовки к выполнения лабо- раторной работы
Изучить по лекциям и учебной литературе особенности построе- ния графов экспертных систем.
Порядок выполнения лабораторной работы
Задание

120
Построить граф работы экспертной системы для выбранной предметной области (предметную область «Автосервис» использовать нельзя). Использовать связи «И» и «ИЛИ». В графе должно содер- жаться минимум 15 правил различной сложности. Правил с одним условием в условной части – не более 5.
Содержание отчёта
1. Титульный лист.
2. Цель лабораторной работы.
3. Граф работы экспертной системы.
4. Перечень правил в формате «Если… то…».
Контрольные вопросы

1. Что такое экспертная система?
2. Какие виды экспертных систем Вы знаете? Их основные осо- бенности?
3. Назовите области применения экспертных систем.
Список литературы
1. Пальмов С.В. Конспект лекций по дисциплине «Интеллекту- альные системы и технологии».
Список использованной литературы
1. Материалы сайта basegroup.ru
2. Тоби Сегаран. Программируем коллективный разум.
3. Марк Лутц. Изучаем Python.
4. Справочные материалы аналитической системы Deductor.