Разработка подхода к программированию "искусственного интеллекта" в позиционных играх на основе игры "Точки" - Дипломная работа

С развитием компьютерной техники и информационных систем во всех сферах человеческой деятельности появляются задачи, решение которых требуют создания систем, частично или полностью заменяющих специалиста, а так же позволяющих имитировать различные ситуации и процессы реального мира для выработки стратегий действия в этих ситуациях. Такие системы позволят решать множество задач в экономике и управлении, политике и военном деле. Как показывает практика, моделью ситуаций реального мира являются позиционные игры. Разработки «искусственного интеллекта» (ИИ) для позиционных игр, а именно, для шахмат ведутся с конца 50-х годов XX века. Для игр типа шахмат и шашек данные алгоритмы являются весьма эффективными, но методы и технология разработки такого «искусственного интеллекта» достаточно примитивна и мало интересна, так как скорость перебора зависит лишь от мощности компьютера.В ходе работы были поставлены следующие базовые задачи: Разработать программу для игры в «Точки». Решение поставленных базовых задач заключается в следующем: Разработана программа, поддерживающая процесс игры в «Точки» для двух игроков и возможное подключение вместо одного или двух игроков модулей ИИ. Игра «Точки» представляет собой упрощенный вариант японской игры «Го». Точки и территория, окруженная другим игроком, считается захваченной. Недостаток алгоритма перебора дерева ходов очевиден, поэтому для создания качественного искусственного интеллекта нужен новый подход, который бы учитывал то, что ситуация в игре гораздо более «непрерывна», «локально обусловлена»: каждый ход влияет на небольшую окрестность поля.искусственный интеллект точка играПроектной частью дипломной работы является расширяемая программа игры в «Точки» для двух игроков, разработанная на языке Компонентный Паскаль в среде BLACKBOX Component Builder. Структура программы состоит из отдельных модулей, взаимодействующих друг с другом (Рисунок 2.1) В этом модуле реализована основная логика игры - хранение ходов, расчет захваченных областей и их границ. Данный модуль включает в себя процедуры по отрисовке основных элементов поля, цветовой настройке поля.В этом модуле реализованна основная логика программы, включающая в себя различные функции для создания модели игровой ситуации. Игра - указательный тип записи, имеющие следующие поля: поле-: Поле; - двумерный динамический массив типа Узел. игроков-: INTEGER - количество игроков, для которых создается игра. ход-: INTEGER - номер текущего хода. статистика-: Статистика - структура данных, хранящая в себе количество пленных точек и захваченную территорию. (и: Игра) Сделать_ход (x, y, игрок: INTEGER), NEW - метод у типа Игра. У типа Область имеется поля: игрок-: INTEGER - какому игроку принадлежит область; Имеет следующие поля: точка_игрока-: INTEGER - указывает, какому игроку принадлежит поставленная точка. поставлена_на_ходе-: INTEGER - поле хранит в себе номер хода, на котором была поставлена точка_игрока. была_в_плену-: BOOLEAN - принимает одно из двух состояний в зависимости от игровой ситуации, которым определяется статус точки.По полю во все направления распространяется волна, причем каждая пройденная волной клетка помечается как клетка, в которой волна есть, т.е. она доступна для волны (не является внутренней для области). Волна расширяется, пока имеется такая возможность, т.е. имеются доступные клетки, не занятые волной. Процедура имеет параметры x, y - координаты точки, игрок - какой игрок делает ход. Расчет областей и границ выполняется, начиная с последнего игрока, сделавшего ход, так как на практике возникает ситуация, когда у одного игрока имеется область, в которой находится пересечение, не занятое точкой ни одного игрока. В цикле проверяем, соответствует ли точка [i, j] условию того, что в этой точке нет волны, но волна может быть и ей есть откуда прийти (волна рядом).Отображения являются универсальным элементом BLACKBOX Framework, так как большинство команд выполняются над отображениями, окна показывают отображения, отображения могут быть загружены и выгружены, с помощью отображений проводится взаимодействие с пользователем и отображения могут быть внедрены в другие отображения.Основным типом в модуле ТОЧКИГРАФИКА является тип View (Листинг 2.17). Тип View представляет собой набор элементов (полей), необходимых для отрисовки основных элементов игрового поля. Поле «игра» имеет тип Игра.Игра, который импортирован из модуля ТОЧКИИГРА и необходим для доступа к таким полям, как «поле», «игроков», «статистика».В Компонентном Паскале отрисовкой вьюшки занимается связанная с типом процедура Restore (Листинг 2.18). В результате выполнения процедуры Restore будет отрисовано игровое поле (Рисунок 2.9). Это статистика для каждого игрока, клетчатое поле, точки свободные и захваченные, последний ход для каждого игрока, курсор, номер текущего хода и его координаты. Процедура Рисовать_статистику выполняет рисование на игровом поле информации о количестве захваченных точек и территории для каждого игрока (Рисунок 2.10). Процедура Ри

Содержание

Введение

1. Аналитическая часть

1.1 Характеристика и анализ решаемых задач

1.2 Позиционная игра «Точки». Правила игры

1.3 Особенности игры «Точки»

1.4 Актуальность разработки "искусственного интеллекта" для позиционных игр

1.5 Анализ существующих подходов программирования "искусственного интеллекта"

1.6 Концепция позиционного "искусственного интеллекта"

2. Проектная часть

2.1 Проектирование и разработка общей структуры системы

2.1.1 Модель игровой ситуации

2.1.2 Алгоритмы

2.2 Графика

2.2.1 Описание типа View

2.2.2 Отрисовка основных элементов поля

2.2.3 Алгоритм рисования границ

2.3 Реализация сохранения и воспроизведения игры

2.3.1 Сохранение

2.3.2 Воспроизведение

2.4 Проектирование позиционного «искуственного интеллекта» (ИИ)

2.4.1 Реализация решающей части

2.4.2 Направления развития решающей части

3. Технико-экономическая часть

3.1 Характеристики программы для игры в «Точки»

3.2 Расчет затрат на создание игры

3.3 Расчет поступления денежных средств от реализации компьютерной игры «Точки»

3.4 Расчет срока окупаемости затрат на разработку компьютерной игры «Точки»

4. Безопасность жизнедеятельности

4.1 Помещение и освещение

4.2 Рабочее место

Заключение

Литература

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

Как показывает практика, моделью ситуаций реального мира являются позиционные игры. Следовательно, целесообразно вести поиски решения данных задач именно на основе позиционных игр. Разработки «искусственного интеллекта» (ИИ) для позиционных игр, а именно, для шахмат ведутся с конца 50-х годов XX века. За это время компьютерная техника все более совершенствовалась, и алгоритмы программ, соответственно, усложнялись. Однако до сих пор такие программы основаны на алгоритмах перебора. Для игр типа шахмат и шашек данные алгоритмы являются весьма эффективными, но методы и технология разработки такого «искусственного интеллекта» достаточно примитивна и мало интересна, так как скорость перебора зависит лишь от мощности компьютера.

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

В качестве основы для исследования выбрана игра «Точки», которая является упрощенным вариантом классической японской игры Го. До сих пор не существует систем, играющих в Го лучше, чем начинающий игрок. Существующие реализации играющей части так же, как и в шахматах, основаны на переборе дерева вариантов, но перебор в Го («Точки») усложняется значительно большей величиной дерева. В реализованных системах просчеты ведутся лишь на три-четыре пары ходов. Это еще раз доказывает то, что перебор дерева вариантов и его последующие модификации не являются эффективными для решения задачи создания систем принятия решений. Для создания эффективной системы принятия решений требуется создание концепции позиционного «искусственного интеллекта».

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