Что такое алгоритм в компьютерной игре
Игровая технология – это очень обширная группа методов и приёмов организации педагогического процесса в форме игры.
Из всего многообразия логико-математических обучающих игр мы для своей работы выбрали игры, знакомящие детей со структурой алгоритма.
Вложение | Размер |
---|---|
domnina.doc | 33.5 КБ |
Предварительный просмотр:
Применение игр с алгоритмами для развития логического мышления в работе со старшими дошкольниками
Автор: Домнина Альфия Рифатовна,
воспитатель ГБДОУ детский сад №62
Приморского района Санкт-Петербурга
В настоящее время, в дошкольных образовательных программах появилось много описаний игр и упражнений, по-новому развивающих такую функцию мышления как умение действовать по правилам, действовать последовательно.
Эта игра дает ребенку две необходимые способности:
1) выполнение правил в игре всегда связано с воспроизведением воображаемой ситуации. Воображение тоже связано со смыслом.
2) игра с правилами учит общаться. Ведь большинство игр с правилами — это игры коллективные. В них встречаются два рода отношений. Это отношения соревновательного типа — между командами, между партнерами, у которых прямо противоположная цель (если один выиграет, то другой проиграет), и отношения подлинного сотрудничества — между участниками одной команды.
Реализация задач социально-коммуникативного развития дошкольников направлена на приобретение опыта в различных видах детской деятельности .
• Игровая деятельность дает ребенку почувствовать себя равноправным членом общества. В игре у ребенка появляется уверенность в собственных силах, в способности получать реальный результат.
• Познавательная деятельность обогащает опыт ребенка, стимулирует развитие познавательных интересов, рождает и закрепляет социальные чувства.
• Коммуникативная деятельность (общение) объединяет взрослого и ребенка, удовлетворяет разнообразные потребности ребенка в эмоциональной близости с взрослым, в его поддержке и оценке.
Социально-коммуникативное развитие направлено:
- на усвоение норм и ценностей, принятых в обществе, включая моральные и нравственные ценности;
- развитие общения и взаимодействия ребенка с взрослыми и сверстниками;
- становление самостоятельности, целенаправленности и саморегуляции собственных действий;
- развитие социального и эмоционального интеллекта, эмоциональной отзывчивости, сопереживания, формирование готовности к совместной деятельности со сверстниками, формирование уважительного отношения и чувства принадлежности к своей семье и к сообществу детей и взрослых в Организации;
- формирование позитивных установок к различным видам труда и творчества;
- формирование основ безопасного поведения в быту, социуме, природе.
Игровая технология – это очень обширная группа методов и приёмов организации педагогического процесса в форме игры.
Из всего многообразия логико-математических обучающих игр мы для своей работы выбрали игры, знакомящие детей со структурой алгоритма.
Игры, знакомящие детей с алгоритмами, по-новому развивают такую функцию мышления как умение действовать по правилам, формируют умение планировать свои действия, строго придерживаться определенных правил, а также умение выражать свои действия адекватными языковыми средствами. Они открывают хорошие возможности для раннего внедрения в обучение простейших идей информатики, формируют дисциплину ума и операционный стиль мышления.
Алгоритм - описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике.
Игра - ведущий вид деятельности ребенка дошкольного возраста. Главное изменение в поведении состоит в том, что желания ребенка отходят на второй план, и на первый план выходит четкое выполнение правил игры.
Перед тем как приступить к изучению алгоритмов, необходимо определиться в очень важном понятии - исполнитель. В данном случае под исполнителем мы будем понимать ребёнка-исполнителя, который не сам разрабатывает алгоритм а, получает его в готовом виде и затем исполняет
Понятие алгоритма не есть для нас что-то новое и необычное. Встречаются они в нашей повседневной жизни почти на каждом шагу. Так, утром мама перед уходом в школу дает ребёнку такую инструкцию: "Когда придешь со школы, сразу пообедай и не забудь вымыть посуду. После этого подмети пол, купи в магазине молоко и хлеб. Сделав покупки, погуляй часок и начинай выполнять домашнее задание". Эта инструкция состоит из последовательности отдельных указаний, которые определяют ваше поведение. Это и есть - алгоритм.
Для старших дошкольников в игре главное - отношения между людьми, игровые действия производятся ими не ради самих действий, а ради стоящих за ними отношений. Поэтому 5-летний ребенок никогда не забудет «нарезанный» хлеб поставить перед куклами и никогда не перепутает последовательность действий - сначала обед, потом мытье посуды, а не наоборот. Для детей 5-6-летнего возраста характерно воспроизведение логики реальных действий людей; содержанием игры являются предметные действия.
Таким образом, учитывая актуальность и современность темы «Алгоритмы» в обучении дошкольников и проанализировав содержание предлагаемых известными педагогами игр и упражнений, мы решили применять их в своей работе, предполагая, что это повысит развивающий эффект занятий по математике и информатике.
Игровая карта имеет обычно фиксированный размер. Способ представления разных частей поверхности разными цветами - земли зеленой, пустыни желтой, рек и моря - голубыми, и различных их комбинаций относится к стандартным возможностям 3D-библиотек и поэтому здесь рассматриваться не будет. Попытки вылететь за границы карты либо не разрешены в игре, либо предоставляют возможность лететь, пока есть топливо, но кроме голой поверхности вы не увидите никаких новых предметов.
Основным в игре является массив объектов, участвующих в миссии. Структура отдельного объекта уже упоминалась выше. Он обязательно содержит свои координаты, отсчитываемые от одного из углов карты. Каждый момент времени, когда ваш самолет изменил свои трехмерные координаты, происходит проверка видимости каждого из объектов массива. Для этого после вычисления двумерного образа его угловой размер сравнивается с минимальным ограничивающим значением для необходимости отображения на экране.
Важным моментом в имитаторах этого рода является моделирование стрельбы. Как и в играх типа Arcade появляются новые динамические объекты типа “пуля”. Но в зависимости от типа вооружения в этих структурах появляется новое поле - идентификатор цели. Это необходимо для самонаводящихся ракет, которые должны динамически изменять свою траекторию, преследуя мишень. Еще несколько полей будут характеризовать дополнительные параметры оружия, такие как дальность стрельбы, поражающая способность и т.д.
Некоторые игровые объекты, атакующие самолет героя, программируются иначе. Они в реальности не выстреливают снаряды, живущие в игре, а действуют по иному алгоритму. Когда ваш самолет попадает в поле их контроля, то по заданным вероятностям, меняющимся в зависимости от уровня, просто определяется сам факт поражения вашего истребителя и размеры ущерба. Это, конечно, сопровождается визуальными эффектами - кабина дрожит, экран заволакивают клубы дыма, и звуковыми - грохот взрывов. Например:
Для моделирования движения самолетов противника используются специальные алгоритмы преследования, иногда простые, иногда сложные. Вообще тема поведения различных объектов в игре заслуживает отдельного разговора, относящегося к алгоритмам искусственного интеллекта.
Некоторые имитаторы, делающие упор на боевые схватки с противником, не уделяют большого внимания реалистичности управления самолетом. В то же время в некоторых играх вам потребуется тщательно изучить многостраничное руководство, и иногда настоящие летные инструкции к реальному самолету, чтобы научиться отрывать истребитель от земли и не разбиваться при посадке. Моделирование реалистичного движения самолета достаточно сложно. Надо учитывать массу специфической информации, хорошо знать физику полета и подробные характеристики имитируемых машин. Но все усилия по созданию реалистичных имитаторов, как правило, окупаются сторицей. Сегодня хорошие имитаторы продаются сотнями тысяч копий, и интерес к новым играм этого жанра постоянно возрастает.
Главный объект-самолет содержит поля своих текущих координат, скорость и направление движения, текущее вооружение и техническое состояние различных систем.
Мы приведем алгоритм простого имитатора боевого самолета.
- Выбрать очередную миссию, проинициализировать все начальные значения в игре, установить игровым объектам их координаты и характеристики. Начать полет.
- Переместить самолет, изменить вид из кабины.
- Опросить клавиатуру или джойстик. Если человек ничего не делает, то перейти к п.6.
- Если человек управляет самолетом, то внести коррективы в скорость, направление движения и т.д.
- Если герой выстрелил, то добавить объект “пуля” в список динамических объектов.
- Просканировать список динамических объектов.
Для объектов типа самолет противника: переместиться по алгоритму маневрирования, по заданному закону распределения вероятности вести огонь по самолету героя;
Для наземных объектов типа танк: если самолет героя в зоне обнаружения, то начать огонь по случайному закону;
Для объектов типа пуля: переместиться в новую точку в соответствии с возможностью автоматического преследования;
Если она не пуста, то:
- если в ней поражаемая цель, то изменить характеристики цели (нанести технический урон, вычеркнуть из списка объектов);
- вычеркнуть себя из списка динамических объектов.
- Перейти к п.2.
- Соответствие самолету-прототипу по геометрическим размерам, общему виду (пропорциям), камуфляжу, маркировке, расположению приборов и оборудования в кабине.
- Разнообразие имитируемых самолетов соответствующего исторического периода.
- Соответствие прототипам самолетов противника по внешнему виду, составу вооружения, летным характеристикам.
- Сложность и насыщенность воздушной обстановки.
- Сложность и насыщенность наземной обстановки (объекты своих войск и цели противника).
- Реалистичность изображения наземных целей.
- Логическая последовательность и сложность заданий.
- Специальные (нетиповые) задачи.
- Исторические задания.
- Дружественность интерфейса пользователя при планировании заданий, возможность настройки опций.
- Звуковая имитация.
- Музыка.
- Оцифрованная речь.
- Увлекательность игрового пространства.
- Общая привлекательность графики.
- Простота освоения.
- Проинициализировать все начальные значения в игре, создать текущий уровень лабиринта.
- Опросить клавиатуру или джойстик. Если человек ничего не делает, то перейти к п.5.
- Если передвижение героя, то
- вычислить новые координаты;
- если передвижение вперед возможно, то передвинуть героя, проверить достижение цели и наличие в новой точке других объектов (ключ, платформа, монстр и т.д.) При наличии сделать необходимые действия.
- иначе восстановить старые координаты;
- Если герой выстрелил, то добавить объект “пуля” в список динамических объектов.
- Просканировать список динамических объектов. Для тех, у кого подошла периодичность действия:
Для объектов типа платформа: вычислить новые координаты, переместиться;
Для объектов типа монстр : вычислить новые координаты, переместиться, проверить наличие жертвы в новой точке, при необходимости совершить нужное действие;
Для объектов типа пуля : переместиться в новую точку. Если она не пуста, то: - если в ней поражаемая цель, то изменить характеристики цели (понизить запас энергии, вычеркнуть из списка объектов); вычеркнуть себя из списка динамических объектов.
- Перейти к п.2.
- Задание начальных условий.
- Проверка возможности хода.
- Выполнение хода и оценка позиции.
- Проверка условия конца игры.
- Простая реализация.
- Высокая скорость работы игровых функций.
- Для добавления правил игры необходимы весь исходный код программы и компилятор.
- Необходимо знание языка программирования, на котором написана программа.
- Возможность создания любого количества игр, не изменяя исход-ный код программы.
- Высокая скорость работы функций, реализованных в модулях.
- Необходимость знания языка программирования, программу на котором можно скомпилировать в модуль.
- Нужен интерфейс для взаимодействия с модулями.
- Количество возможных игр не ограничено.
- Не требует средств разработки и каких-либо компиляторов.
- Язык должен быть очень простым и обучение программированию на нем не должно занимать много времени. (В язык могут быть встроены функции, облегчающие какие-либо часто встречающиеся операции (например, функции, подсчитывающие количество идущих подряд клеток определенного цвета).
- Требуется изучение специального языка.
- Язык может уступать по функциональности распространенным языкам высокого уровня.
- Скорость работы значительно ниже, чем при использовании скомпилированного кода, т.к. тратится дополнительное время на интерпретацию.
- Не требуется специального обучения программированию.
- Функции, составленные из блоков, удобно редактировать.
- \(p\) – текущая позиция;
- \(p_i\) – все позиции, доступные из позиции \(p\);
- \(F(p)\) – выигрыш игрока в позиции \(p\).
- Простая реализация.
- Гарантированно будут рассмотрены все ходы.
- alpha – верхняя граница;
- beta – нижняя граница;
- \(F_(p,alpha,beta)\) – функция, вычисляющая оценку позиции \(p\) методом альфа-бета отсечений.
- \(F_(p,alpha,beta) \le alpha\), если \(F(p) \le alpha\)
- \(F_(p,alpha,beta) = F(p)\), если \(alpha < F(p) < beta\)
- \(F_(p,alpha,beta) \ge beta\), если \(F(p) \ge beta\)
- В большинстве случаев значительно уменьшается количество рассматриваемых позиций при переборе.
- Реализация легко получается из реализации алгоритма мини-максного дерева.
- Результат не хуже, чем при полном переборе позиций.
- Высокий уровень игры при большом количестве разыгрываемых случайных партий.
- Хорошо поддается распараллеливанию.
- Линейная сложность.
- Хорошие ходы могут не попасть в случайную выборку.
- Для сильной игры требуется производительный компьютер.
Самым сложным в этом жанре компьютерных игр является моделирование реальных характеристик самолета, требующее использования достаточно сложных математических методов, грамотное и эффективное использование трехмерных библиотек, а также в ряде случаев моделирование разумного поведения самолетов противника. Попробуем рассмотреть приемы программирования тех или иных деталей авиаимитаторов более подробно. Сначала выделим те критерии оценки, которые относятся к работе дизайнеров, художников, сценаристов и музыкантов, но не программистов:
Теперь рассмотрим проблемы, возникающие при программировании других характеристик имитаторов.
Игры класса Аrcade охватывают огромную область, имеющую лишь один объединяющий признак, - высокие требования к спинному мозгу. Поэтому практически невозможно описать и проанализировать один алгоритм на всех. В самом деле, что общего между PipeDream и Принцами Персии? Поэтому здесь можно выделить, например, одну большую группу, в которой главный герой перемещается по бесчисленным лабиринтам замков или космических кораблей, дерется на мечах или стреляет из бластера в тучи мерзких существ, выскакивающих из всех дыр и дверей, перепрыгивает ямы и ловушки и подбирает различные полезные или вредные предметы, которые могут пригодиться в дальнейшем или просто приносят очки. Конечная цель здесь бывает различной в игровом смысле - или спасти принцессу, или Вселенную, или найти Волшебную чашу, но внутри игры конечной целью является, как правило, нахождение хорошо спрятанного объекта. Эта группа имеет название “Платформы и лестницы”.
Отметим только, что возможен несколько более общий случай, когда герой передвигается не только по горизонтали и вертикали, как при виде сбоку, но и по вертикали и горизонтали как при виде сверху. Этот тип путешествия в лабиринтах тоже встречается в ряде компьютерных игр.
Итак, рассмотрим возможные структуры данных в типичных platforms & ladders- играх. Во-первых, это сам лабиринт. Он представляется трехмерным массивом (LxNxM). Первое измерение - это список из L уровней, отличающихся друг от друга конфигурацией лабиринтов и их сложностью. Второе и третье измерения описывают двумерный массив размером NхM, определяющий конкретную структуру L-го лабиринта. В реальности параметры M и N могут определять как длину и ширину при виде сверху, так длину и высоту при виде сбоку.
Конкретный элемент массива определяет наличие в месте (i,j) стены и прочих персонажей игры. Для визуализации лабиринта используется специальная таблица связей значений элементов этого массива с кодами спрайтов, служащих для отображения этого элемента на экране. Экран представляет собой прямоугольную матрицу, каждый элемент которой соответствует некоторому элементу игрового массива со сдвигом от начала в зависимости от местоположения героя. Как правило, на экране присутствует не весь лабиринт, а только его маленькая часть. Хотя это может показаться удивительным, но "ВСЕ" игры этого жанра построены именно так.
Хотя герой вроде бы может передвигаться в стороны на 1-2 пиксела, а квадраты изображения имеют размеры не менее 20 пикселов, но здесь нет ошибки. Дело в том, что спрайт героя на экране может быть привязан к точным координатам, но перемещение его по внутреннему массиву программы происходит по дискретным координатам. Если герой смещен относительно подъемника на 5 пикселов, то попытка подняться вверх либо ни к чему не приведет, либо поставит героя "ТОЧНО" в центр лестницы (ее новых позиций в массиве). Вы можете убедиться в этом самостоятельно. Этот принцип является основополагающим и фундаментальным для большинства компьютерных игр, таких как военные, RPG и многих других. Мы еще встретимся с этой идеей в дальнейшем.
Отображение экрана (крайне условное, так как на практике происходит предварительное формирование образа экрана в буфере, подготовительные анимационные процедуры и т.д.) выглядит так:
где SpriteNum - массив, элементами которого являются номера спрайтов, а индексами - значения элементов массива, описывающего лабиринт. Процедура DrawScreenCell получает номера ячейки (I,J) в координатах элементов экрана и рисует соответствующий спрайт. Например, если массив с координатами (50,32) имеет значение 5, что соответствует стене, то в таблице SpriteNum пятым элементом может быть значение 12. По значению 12 процедура DrawScreenCell в позиции экрана (50*CELL_WIDTH,32*CELL_HEIGHT) выведет прямоугольник стены. Вообще таблица SpriteNum нужна только для экономии места, потому что многим элементам лабиринта соответствуют одни и те же изображения. Например, стенам простым и фальшивым (см.ниже).
Координаты экрана, наложенные на массив (CurrentScreen.Left, Top, Right, Bottom) перемещаются вместе с героем при каждом его шаге, либо при его приближении к границам экрана.
Для свободного элемента пространства обычно выбирается значение 0. Стены могут принимать значения подчас из достаточно широкого диапазона, например, обычные и скользкие поверхности, причем это отличие отдельных частей может быть только внутренним, а на экране игрок не обнаружит разницы, пока герой не встанет на такую поверхность. Это достигается элементарными проверками типа
Иногда появляются экзотические элементы типа трамплинов, пружин и т.д. Внутренне они ничем не отличаются от тех же скользких поверхностей.
Каждый конкретный код стены напрямую привязывается к его изображению на экране. Некоторые диапазоны значений соответствуют одному изображению, некоторые значения индивидуальны. Например, наклонный пол записан в ячейках игрового поля (5,5),(6,6),(7,7). На экране каждый из этих элементов отображается в виде наклонного участка.
Помимо стен, возможны и другие типы статических элементов. Это в первую очередь лестницы как точки перехода на другой уровень или подъема по вертикальному лабиринту. Они, как и стены, могут иметь ряд кодирующих значений для отличия по внешнему виду, например, лестница со ступеньками, вход в тоннель или висящая веревка.
В многих играх присутствует такой элемент стен как движущиеся платформы. Несмотря на свою принадлежность к типу стен, внутри программы они относятся к совсем другому типу движущихся объектов. Об этом будет сказано ниже.
Двери и ключи или рычаги для их открытия программируются схожим образом. Точка массива со значением “дверь” кодируется двумя значениями. Первое из них соответствует положению “дверь закрыта”, второе - “дверь открыта”. В исходном состоянии игры некоторые из дверей открыты, некоторые закрыты. Состояние “открытости” может как отображаться на экране, так и быть неотличимым от “закрытости”. Когда герой оказывается в точке массива со значением “дверь”, то производит проверка ее открытости или наличия у героя “ключа” для этой двери.
Кнопки или рычаги также принимают два значения в зависимости от их положения. Когда герой нажимает на кнопку, то может открыться дверь, которая пока не видна на экране.
В больших и сложных играх связи между различными кнопками и дверями гораздо сложнее. Там необходимо дополнительно хранить таблицы взаимосвязей между конкретными кнопками, рычагами и открываемыми ими дверями. В качестве элементов таких массивов выступают координаты кнопок и соответствующие им координаты двери (или дверей).
Интересными декоративными элементами являются невидимые или фальшивые стены. Первые отображаются пустым местом, но не дают герою продвигаться дальше. Для этого при проверке возможности перемещения героя в некотором направлении включается дополнительная проверка на наличие впереди невидимой стены. Для фальшивых стен все наоборот. Они отображаются на экране тем же спрайтом, что и настоящие, но не мешают герою проходить сквозь них. При этом они могут как оставаться на месте, так и исчезать. Для этого служат проверки типа:
Если стена остается на месте, то, очевидно, ничего делать не надо.
Также фиксируется начальное расположение предметов, помогающих или мешающих герою. Это могут быть различные виды оружия (лук, копье, меч), просто сюрпризы с очками, дополнительные жизни или предметы, позволяющие быстрее передвигаться. Они носят объединяющее название PowerUp. Их распределение может либо задаваться сценаристом изначально с помощью редакторов лабиринтов, входящих в обязательный инструментарий при создании подобных игр, либо быть случайным, тогда каждому из предметов ставится в соответствие некоторая величина вероятности появления в свободном месте.
Допустим, если вы хотите разместить примерно пять жизней в лабиринте размером 50 х 50, то исходный текст будет выглядеть примерно так:
Конечно, в реальности жизней может получиться 3 или 6, но в среднем при большом числе повторов игры их будет 5.
При случайном распределении стен следует использовать вероятности появления в одной точке от 0.4 до 0.6. При этом при значении 0.4 лабиринт будет слишком пустым, а при 0.6 - невозможным для прохода. Значение около 0.55 близко к оптимальному.
Пример заполнения лабиринта случайными стенами:
Особо кодируется выход из лабиринта. Его расположение можно задать случайно, но рекомендуется более осторожно отнестись к его местоположению, чтобы он не очутился прямо около героя в начале игры. Около выхода обычно специально размещают более сильного монстра-“босса”.
Ключевым является главный объект “ГЕРОЙ”. Помимо координат его местонахождения он содержит ряд дополнительных характеристик. Это в первую очередь запас энергии или количество жизней, наличие и тип вооружения, запас боеприпасов, а также найденные предметы и очки. Герой передвигается с помощью стрелок или джойстика. Процесс реализации перемещения очевиден. К текущим координатам героя прибавляется соответствующее смещение и для новых координат производятся разнообразные проверки на предмет наличия помех (стен), проваливания в ямы, нахождения различных предметов и т.д. Если передвижение по выбранному направлению невозможно, то восстанавливаются старые координаты.
Достаточно сложным является процесс реализации стрельбы как героя, так и его противников. Для объектов, управляемых программой, прежде всего необходимо подбирать соответствующие значения периодичности стрельбы и точности выстрела. В играх, где после момента выстрела не существует паузы до момента поражения героя (то есть герой не может уворачиваться от выстрелов), дальнейший процесс обработки выстрела несложен. Без проверки всех событий игры рисуется траектория выстрела, проверяется поражение цели, и она либо поражается (вычеркивается из игры или понижается ее энергия), либо выстрел прошел мимо. После этого изображение на экране восстанавливается, и продолжается обычный ход событий. Если же герой может уворачиваться от летящих в него пуль и прочих предметов, то задача усложняется. После выстрела создается динамический объект пули, включаемый в список динамических объектов. Он характеризуется скоростью, направлением движения и типом (копье, лазерный луч и т.д.) Тип нужен для корректного определения размера поражения цели.
Сам алгоритм platforms & ladders-игр похож на алгоритмы из многих других типов игр. Попробуем его описать.
Конечно, современные platforms & ladders-игры во многом сложнее приведенного нами алгоритма. Они представляют собой, как правило, сложное сочетание лабиринтной идеологии с крутыми аркадными вставками, менеджментом, но основа их остается неизменной. Многие разновидности и новые версии известных игр являются, по сути, старыми играми с новыми картинками спрайтов и измененным количеством персонажей с различными характеристиками. Сложность этого типа игр сегодня заключается практически только в оптимальном подборе параметров, придумыванию хорошего сюжета и качественного дизайна.
Сегодня появляются новые игры этого жанра, например, DOOM. Качественным их отличием от себе подобных является увеличение числа измерений до трех. Правда, это не сильно меняет структуру программы. Хотя герой теперь имеет возможность перемещаться не дискретно - по квадратам, а непрерывно, то есть как и в реальной жизни, перемещаться в любую доступную точку помещения, но по сути ничего не меняется. Конечно, исчезает базовый массив, описывающий структуру лабиринта, а задача проверки столкновения героя со стенами ложится на программу, но принцип остается схожим. Теперь программа содержит только описания координат стен и их толщин и проверяет допустимость координат героя:
Соответственно появляется по аналогии с списком динамических объектов и список статических объектов (PowerUp List). При этом на каждом шаге героя проверяется его близость к тому или иному предмету и при необходимости совершается соответствующее действие. Некоторые предметы надо специально брать, для чего служит специальная клавиша. Но в целом структура базового алгоритма не меняется. Введение третьего измерения по сути аналогично новым уровням игры, когда подъем наверх имитирует переход на другой уровень или вход в другой лабиринт в обычных играх этого типа. На самом деле создатели игр типа DOOM исповедуют оба подхода. Например, в игре Terminator:Rampage фирмы Bethesda Softworks с 3-Д графикой, практически идентичной Id Software, положение героя тоже дискретно, а расположение комнат и коридоров на каждом из уровней заложены в массив 100х100 элементов. Но на внешнем виде игры этот нюанс никак не сказывается.
В статье рассмотрены способы создания универсальной компьютерной программы, играющей в логические игры («Крестики-нолики», «Реверси» и т.п.). Также проведен анализ некоторых универсальных алгоритмов выбора оптимального хода.
Программа должна состоять из двух частей: алгоритма выбора оптимального хода для игрока-компьютера и набора функций, определяющих правила игры (рассматриваться будут только антагонистические игры).
Антагонистическая игра (или игра с нулевой суммой) - некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны.
Рассмотрим каждую часть отдельно.
Предварительный просмотр:
Искусственный интеллект - одно из направлений развития современного программного обеспечения. Мы довольно часто сталкиваемся с ним в повседневной жизни, в том числе и при работе с компьютером. Например: компьютерная программа играет в шахматы, шашки, карты и другие интеллектуальные игры, причем не хуже профессиональных игроков в эти игры. При всем этом эти программы имеют сравнительно небольшой объем. Например, шахматная программа может занимать объем всего 70-80 килобайт. При этом возникает вопрос: каким образом относительно несложной компьютерной программе удается довольно хорошо играть в интеллектуальные игры, причем довольно часто выигрывать? Для того, чтобы ответить на этот вопрос следует поразмыслить над тем, как мы сами играем в шахматы или шашки.
Сложно дать однозначное определение игры в шахматы, даже шахматисты не могут объяснить, по какому алгоритму они играют. Во-первых, шахматист использует то, что мы называем опытом. Во-вторых, он руководствуется здравым смыслом, основываясь на правилах и цели игры. И, в-третьих, он опирается на уже известные ему различные комбинации игры, то есть на такие ситуации, в которых он знает точно, какой ход выполнять. Конечно же, эти принципы не объясняют полностью способ игры, способ принятия решений, но он довольно точно описывает основные принципы интеллектуальных игр.
Теперь подумаем, как можно применить эти принципы для написания компьютерной программы, которая могла бы играть в одну из интеллектуальных игр. Современные компьютеры не обладают возможностью самообучения, поэтому компьютер не может самостоятельно приобретать опыт деятельности в какой-либо сфере. Опыт человека также не может помочь компьютеру, так как его сложно переложить на язык программирования. Понятие "здравый смысл" настолько абстрактно для программирования, что его практически невозможно учесть при написании программы. Соответственно, "алгоритм" применяемый человеком абсолютно не подходит для компьютера.
С первого взгляда кажется, что можно внести в компьютер все возможные комбинации игры и ходы для каждой из них, но это абсолютно нереально. Если для такой несложной игры, как крестики-нолики количество всех комбинаций составляет
"всего" 362 880, то для шахмат это число уже 1 461 501 000 000 000 000 000 000 000 000 000 000 000 000 000 000 комбинаций. Даже для введения трехсот тысяч комбинаций следует потратить очень много времени, а что уж говорить о шахматах с их бесчисленным количеством комбинаций, да и перебор этих комбинаций может занять очень много времени.
Принципы разработки алгоритмов для интеллектуальных игр.
Исходя из вышеперечисленного следует, что для реализации на компьютере следует использовать такой алгоритм, который бы сочетал в себе компактность, высокую скорость работы, возможность реализации на компьютере и при всем этом не должен уступать человеку в логике и тактике. Разработать такой алгоритм - на первый взгляд очень сложная задача, но на самом деле он не так сложен. Для того чтобы понять, как разрабатывать этот алгоритм следует поставить себя на место компьютера. Во-первых, обсудим основные отличия между человеком и компьютером:
Обладает естественным интеллектом, способен принимать решения в сложных ситуациях
Работает очень быстро, но только по программе. Имеет очень большой объем памяти.
Как видно из этого сравнения, алгоритм интеллектуальной игры для реализации его на компьютере должен точно регламентировать выбор того или иного хода. Но как же определить, какой ход является правильным в данной ситуации? Логично, что этот ход должен быть одним из возможных в данное время. То есть для начала нужно определить, какие из ходов возможны в данный момент. Также искомый ход должен быть наиболее выгодным в данной ситуации. Поэтому если вычислить определенный показатель выгодности хода, то из всех ходов можно выбрать наиболее выгодный. Этот показатель выгодности хода можно выразить числом, но как же его вычислить? Оказывается, это не так сложно. Он должен вычисляться из нескольких факторов. Например, для шахмат это могут быть возможность взять те или иные фигуры, продвинуться по полю доски в сторону противника. Проанализировав все эти факторы и присвоив различным ситуациям, возникающим при выполнении данного хода различные "оценки" и сложив результаты по нескольким факторам, мы получим тот самый искомый показатель выгодности хода. Затем следует выбрать ход с наибольшим показателем выгодности и привести его в действие, что с программной точки зрения выполнить абсолютно несложно. Таким образом, мы получили универсальный алгоритм для интеллектуальных игр, причем доступный для его реализации на компьютере. В общей записи этот алгоритм выглядит следующим образом:
2. Способы описания правил.
В программе алгоритм получает сведения о правилах игры через вызов специальных функций. Пример набора функций, достаточного для большинства логических игр:
Для обеспечения универсальности, функции должны поддерживать выбор правил для разных игр. Правила могут быть представлены разными способами.
1. Набор функций для каждой игры описывается вместе с остальными функциями (алгоритмом выбора хода и т.п.) и компилируется в один исполняемый файл.
2. Подключение набора функций в виде внешнего модуля (например, DLL).
Большинство шахматных программ подключается к шахматным оболочкам в виде внешних модулей (для взаимодействия обычно используется специальный протокол UCI - Universal Chess Interface).
3. Реализация программы как интерпретатора языка программирования. Каждая функция описываются в виде программы, которую можно интерпретировать и которая может получать доступ к игровым переменным. При вызове функции программа интерпретируется с заданными параметрами (номер игрока, координаты хода и т.п.) и, если требуется, возвращает не-которое значение (выигрыш игрока, возможность хода и т.п.).
Пример программы на интерпретируемом языке, описывающей правила игры “Крестики-нолики” на поле 3х3:
4. Правила создаются при помощи визуального редактора. Наборы действий для каждой функции могут собираться из большого числа стандартных блоков, которые могут отображаться в удобном для пользователя виде.
Такой подход использует среда разработки Scratch, разработанная в MIT.
Схема из блоков может быть автоматически преобразована в программный код, который может интерпретироваться, либо компилироваться в программный модуль.
Недостаток: высокая сложность реализации подхода.
Это был краткий обзор универсальных алгоритмов выбора оптимального хода и способов определения правил для логических антагонистических игр.
Данная статья была опубликована в сборнике “Энергия и талант молодёжи - залог развития наукоёмких производств. Сборник научных трудов XII Областной научно-практической конференции молодых учёных. - Т. 1 - Псков: Издательство ППИ, 2010.
Искусственный интеллект - одно из направлений развития современного программного обеспечения. Мы довольно часто сталкиваемся с ним в повседневной жизни, в том числе и при работе с компьютером. Например: компьютерная программа играет в шахматы, шашки, карты и другие интеллектуальные игры, причем не хуже профессиональных игроков в эти игры. При всем этом эти программы имеют сравнительно небольшой объем. Например, шахматная программа может занимать объем всего 70-80 килобайт. При этом возникает вопрос: каким образом относительно несложной компьютерной программе удается довольно хорошо играть в интеллектуальные игры, причем довольно часто выигрывать?
Вложение | Размер |
---|---|
iskusstvennyy_intellekt.doc | 76.5 КБ |
1. Алгоритм выбора оптимального хода
Алгоритм должен быть универсальным (не зависеть от правил игры) и обеспечивать хороший уровень игры. Первый рассматриваемый алгоритм, удовлетворяющий этим условиям – алгоритм минимаксного дерева.
Игрок в текущей позиции пытается сделать все возможные ходы и максимизировать свой выигрыш, а также минимизировать выигрыш другого игрока. Перебор позиций проводится при помощи поиска в глубину (depth-first search, DFS) до достижения некоторой заданной глубины \(d\) или конца игры.
Если позиция p является терминальной, то для нее определена функция \(f(p)\), определяющая выигрыш игрока, которому принадлежит ход в этой позиции.
Позиция называется терминальной, если из нее нет разрешенных ходов (достигнуты конец игры или необходимая глубина перебора).
Выигрыш игрока будет равен:
если позиция \(p\) – терминальная, иначе
Недостаток: требуется проверять все возможные ходы и при увеличении глубины перебора количество рассматриваемых позиций растет экспоненциально.
Количество перебираемых вариантов можно уменьшить, если прекращать поиск точной оценки хода, когда стало известно, что этот ход не может стать лучше, чем один из ходов, рассмотренных ранее[1].
Алгоритм альфа-бета отсечений при вычислении оценки позиции иcпользует верхнюю и нижнюю допустимые границы.
Функция Fab должна удовлетворять условиям:
Недостаток: сложность алгоритма остается такой же, как и при полном переборе позиций (экспоненциальной). Существуют случаи, когда выигрыш от оптимизации незначителен или отсутствует.
Сравнение количества перебранных позиций для первых 10 ходов в игре «Реверси» на поле 8х8 при использовании алгоритмов минимаксного дерева и альфа-бета отсечений (глубина перебора 6 позиций, программа играет против человека, человек делает ход первым)
Номер хода | Минимаксное дерево поиска (полный перебор) | Перебор с использованием альфа-бета отсечений |
---|---|---|
1 | 16 251 | 1 015 |
2 | 61 730 | 1 712 |
3 | 568 484 | 10 948 |
4 | 1 083 976 | 14 325 |
5 | 1 624 623 | 13 598 |
6 | 2 412 356 | 18 287 |
7 | 1 847 605 | 15 328 |
8 | 5 389 480 | 30 807 |
9 | 4 870 334 | 22 508 |
10 | 3 390 729 | 21 994 |
Альтернативой алгоритму минимаксного дерева является использование метода Монте-Карло.
Метод Монте-Карло - общее название группы численных методов, основанных на получении большого числа реализаций случайного процесса, вероятностные характеристики которого совпадают с аналогичными величинами решаемой задачи.
В нашей задаче (поиск оптимального хода): для текущей позиции \(p\) выбираются все возможные позиции \(p_i\) и с каждой из этих позиций разыгрывается большое количество случайных партий. Позиция, для которой соотношение побед и поражений будет наилучшим, выбирается для следующего хода.
Например, одна из сильнейших программ для игры в го, «MoGo», использующая этот метод, запускалась на компьютере производительностью 15 Терафлопс[3] (для сравнения, производительность процессора Intel Core i7-975 0.06 Терафлопс[2], а производительность суперкомпьютера СКИФ МГУ 47,17 Терафлопс[4]).
График зависимости количества выигранных партий в игру «Реверси» на поле 8х8 для программы, использующей метод Монте-Карло с разным числом разыгрываемых случайных партий, играющей против программы, использующей алгоритм альфа-бета отсечений с глубиной перебора 6 позиций.
Читайте также: