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

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

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

.1.2 Алгоритмы

.2 Графика

.2.1 Описание типа View

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

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

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

.3.1 Сохранение

.3.2 Воспроизведение

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

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

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

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

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

.2 Расчёт затрат на создание игры

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

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

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

.1 Помещение и освещение

.2 Рабочее место

Заключение

Литература

Введение

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

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

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

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

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

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

.1 Общая характеристика и анализ решаемых задач

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

В ходе работы были поставлены следующие базовые задачи:

Разработать программу для игры в «Точки».

Разработать каркас для организации игрового ИИ.

Разработать базовый игровой ИИ.

Решение поставленных базовых задач заключается в следующем:

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

Разработаны отдельные компоненты анализа, оценки и прогнозирования игровой ситуации по разным критериям.

Реализован базовый игровой ИИ, имеющий дальнейшие перспективы развития.

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

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

Рисунок 1.1. Пример игровой ситуации

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

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

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

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

Кроме того, «искусственный интеллект» необходим в области компьютерных стратегических и онлайн игр.

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

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

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

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

Если говорить о прикладных системах принятия решений, то в них применяются разного рода специализированные математические модели, которые не применимы в выбранной задаче (например, теория позиционных игр, связанных с преследованием цели).

Программ игры в «Точки», которые имеют «искусственный интеллект», существует мало. Все те, которые известны нам, организованы на базе перебора на дереве вариантов, играют на уровне игрока-новичка, страдают «стратегической слепотой» и не имеют качественных возможностей для совершенствования.

.6 Концепция позиционного «искусственного интеллекта»

В ходе исследовательской работы сложилась концепция позиционного искусственного интеллекта для игры «Точки». Она заключается в том, что искусственный интеллект должен опираться на ряд независимых модулей, которые будут классифицировать ходы и последовательности ходов по различным эвристическим оценкам. Такие эвристики будут опираться на статус точки, который она приобретет в момент хода. Например: ход может стать частью окружения; ход является смежным с существующей группировкой точек; ход является оборонительным, ход препятствует планам противника и т.п. (Рисунок 1.2)

Рисунок 1.2. Пример эвристик

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

Программно каркас для ИИ имеет разъёмы и стандарт обмена данными для подключения разных модулей эвристического анализа. Подключаемый модуль анализирует каждое место возможного хода по какому-то эвристическому признаку и записывает результат на «центральную доску». После работы всех таких модулей выполняется процедура общего оценивания над доской, присваивающая каждому ходу одну численную оценку.

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

Направлениями постепенного усовершенствования данной системы являются:

увеличение арсенала модулей эвристического анализа и схем их совместного включения;

экспериментальный подбор логики выведения общей оценки для хода;

выбор хода не только на основе простой численной оценки.

Кроме того, имеется направление радикального развития системы: снятие «стратегической слепоты» путем применения полевых алгоритмов, разработка онлайн-версии игры для отработки ИИ в «живом окружении», а так же разработка многопользовательской стратегической онлайн-игры по мотивам «Точек» (проект развлекательного характера).

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

искусственный интеллект точка игра

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

Проектной частью дипломной работы является расширяемая программа игры в «Точки» для двух игроков, разработанная на языке Компонентный Паскаль в среде BlackBox Component Builder. Структура программы состоит из отдельных модулей, взаимодействующих друг с другом (Рисунок 2.1)

Рисунок 2.1. Структура программы

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

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

Сохранение и загрузка с проигрыванием игры реализованы в модуле ТочкиХранение.

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

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

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

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

Рассмотрим основные типы данных, используемые в модуле ТочкиИгра (Листинг 2.1).

Листинг 2.1 - Интерфейс модуля ТочкиИгра

Игра - указательный тип записи, имеющие следующие поля:

поле-: Поле; - двумерный динамический массив типа Узел.

игроков-: INTEGER - количество игроков, для которых создается игра.

ход-: INTEGER - номер текущего хода.

статистика-: Статистика - структура данных, хранящая в себе количество пленных точек и захваченную территорию.

(и: Игра) Сделать_ход (x, y, игрок: INTEGER), NEW - метод у типа Игра. Вызывается, в частности, в модуле ТочкиГрафика. (при щелчке мышки по полю области игры).

Область - указательный тип записи, являющийся определяющим типом для поля область- и поля граница- в записи Узел.

У типа Область имеется поля:

игрок-: INTEGER - какому игроку принадлежит область;

точек_противника: INTEGER - сколько точек противника находится в области игрока.

Узел - тип записи, для определения игрового поля (Листинг 2.2).

Листинг 2.2 - Описание типа Поле

Имеет следующие поля:

точка_игрока-: INTEGER - указывает, какому игроку принадлежит поставленная точка.

поставлена_на_ходе-: INTEGER - поле хранит в себе номер хода, на котором была поставлена точка_игрока.

была_в_плену-: BOOLEAN - принимает одно из двух состояний в зависимости от игровой ситуации, которым определяется статус точки.

Новая_игра - процедура фабрика с параметрами:

ш, в: INTEGER - размеры игрового поля.

игроков: INTEGER - количество игроков, для которых создается игра.

.1.2 Алгоритмы

Наиболее интересными видами алгоритмов в программной реализации модели игровой ситуации игры «Точки», являются волновые алгоритмы. На двумерной клетчатой матрице (поле), есть «занятые» и «свободные» пересечения. Цель алгоритма - выделить замкнутые области на поле. По полю во все направления распространяется волна, причем каждая пройденная волной клетка помечается как клетка, в которой волна есть, т.е. она доступна для волны (не является внутренней для области). Волна расширяется, пока имеется такая возможность, т.е. имеются доступные клетки, не занятые волной.

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

После того, как создана новая игра, игроки поочередно ставят точки. За каждый новый ход отвечает процедура Сделать_ход. Процедура имеет параметры x, y - координаты точки, игрок - какой игрок делает ход.

Прежде всего проверяются предусловия того, что точка с координатами x, y свободна и номер игрока допустимый ( Листинг 2.3)

Листинг 2.3 - Процедура Сделать_ход

Если эти условия выполняются, то поставленная точка становится точкой игрока, сделавшего ход, а в поле и.поле[x,y].поставлена_на_ходе присваивается номер текущего хода. Номер текущего хода увеличивается.

Затем вызывается процедура Перерасчёт (Листинг 2.4).

Листинг 2.4 - Процедура Перерасчёт

В процедуре Перерасчёт сначала происходит выполнение процедуры Очистить_области для игрового поля (Листинг 2.5).

Листинг 2.5 - Процедура Очистить_области

После выполнения этой процедуры у каждой точки игрового поля отсутствуют области и границы.

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

Рисунок 2.2. Область с пустым пересечением

Рисунок 2.3. Новая ситуация

Расчет областей происходит в процедуре Рассчитать_области (Листинг 2.7)

Листинг 2.7 - Процедура Рассчитать_области

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

Начинаем распространение волны процедурой Начать_волну (Листинг 2.8).

Листинг 2.8- Процедура Начать_волну

Процедура Начать_волну расставляет признаки волны по краям поля, там, где нет точки игрока.

Первый цикл проверяет верхнюю и нижнюю полосы пересечений, второй - правую и левую.

Затем, выполняем распространение волны по центральной части поля (Листинг 2.9). Процедура Ход_волны выполняется до тех пор, пока волне некуда будет расширяться.

Листинг 2.9 - Распространение волны по центральной части поля

Рассмотрим подробнее процедуру Ход_волны (Рисунок 2.10).

Суть её заключается в том, чтобы проверить точки центральной области поля и распространить в них, если возможно, волну. Для этого принимаем, что волна расшириться дальше не может (расширение := FALSE). В цикле проверяем, соответствует ли точка [i, j] условию того, что в этой точке нет волны, но волна может быть и ей есть откуда прийти (волна рядом). Волна рядом, если в одном из соседних пересечений волна уже есть. (Листинг 2.11)

Если условие проверки выполняется, то данная точка доступна для волны, произошло расширение.

Листинг 2.10 - Процедура Ход_волны

Листинг 2.11 - Процедура Волна_рядом

Итак, вышеописанным способом находятся наружные области игроков. За определение того, какие точки принадлежат рассчитанным областям, отвечает процедуру Найти_области (Листинг 2.12).

В процедуре Найти_неопределенную линейным поиском по матрице ищем точки, область которых ещё неизвестна (Листинг 2.13). Для очередной внутренней точки (где нет волны), у которой ещё нет области, создаем новую область (Листинг 2.14).

Далее в процедуре Заполнить_область происходит «растаскивание» области на смежные точки. Перебираются все точки поля, кроме крайних (крайними считаются верхнее и нижнее, а так же левое и правое пересечение линий поля). Если в данной точке волны нет (точка внутренняя) и у этой точки нет области, то происходит просмотр соседних точек, у которых есть область. Если рядом нашлись точки, имеющие область, то неопределенная внутренняя точка принимает значение области, как у соседней точки с определенной областью. Дальнейшее распространение волны идет от той точки, область которой определилась. Заполнение области происходит, пока волне есть куда распространяться (есть точки без области) (Рисунок 2.4).

Листинг 2.12. Процедура Найти_области

Листинг 2.13. Процедура Найти_неопределенную

Листинг 2.14 - Процедура Новая_область

Рисунок 2.4 Распространение волны внутри области

Рассмотрим, как происходит расчет границ в игре. (Листинг 2.15). У граничной точки области нет, но рядом с этой точкой есть точка или несколько точек, у которых есть область. Циклом по центральной части поля проходим по точкам, у которых есть область (т.е точки внутренние). Как только находим такую внутреннюю точку, ищем рядом граничные точки (Рисунок 2.5).

Граничные точки должны быть именно того игрока, для которого ищем границу. Как только такие точки найдены, присваиваем им в качестве границы область игрока. (Листинг 2.16). В граничный узел может входить две границы: граница[0] и граница[1]. Например, в игре бывают ситуации, когда одна и та же точка игрока входит в разные границы областей (Рисунок 2.6).

Листинг 2.15 - Расчет границ

Рисунок 2.5- Поиск границ

Листинг 2.16 - Процедура Добавить_границу

Рисунок 2.6 - Точка, имеющая две границы

.2 Графика

В среде BlackBox Component Builder создаваемые графические объекты называются отображениями (вьюшками) и являются подтипом абстрактного типа Views.View. Отображения являются универсальным элементом BlackBox Framework, так как большинство команд выполняются над отображениями, окна показывают отображения, отображения могут быть загружены и выгружены, с помощью отображений проводится взаимодействие с пользователем и отображения могут быть внедрены в другие отображения.

Рассмотрим модуль ТочкиГрафика.

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

Основным типом в модуле ТочкиГрафика является тип View (Листинг 2.17).

Листинг 2.17 - Тип View

Тип View представляет собой набор элементов (полей), необходимых для отрисовки основных элементов игрового поля.

Поле «игра» имеет тип Игра.Игра, который импортирован из модуля ТочкиИгра и необходим для доступа к таким полям, как «поле», «игроков», «статистика».

Поле «последние_ходы_игроков» необходимо для пометки последней поставленной точки каждого игрока (Рисунок 2.7). Данное поле представляет собой массив типа Ход, в котором хранятся координаты поставленных точек.

Рисунок 2.7. Последние ходы игроков

Поле «карандаш» хранит положение курсора мыши, который перемещается по игровому полю и показывает, какой игрок должен сделать ход (Рисунок 2.8).

Рисунок 2.8 - Карандаш (курсор)

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

В Компонентном Паскале отрисовкой вьюшки занимается связанная с типом процедура Restore (Листинг 2.18).

Листинг 2.18 - Процедура Restore

В результате выполнения процедуры Restore будет отрисовано игровое поле (Рисунок 2.9). Оно включает в себя несколько элементов. Это статистика для каждого игрока, клетчатое поле, точки свободные и захваченные, последний ход для каждого игрока, курсор, номер текущего хода и его координаты. Рассмотрим подробнее, как происходит рисование этих элементов.

Рисунок 2.9. Игровое поле

Процедура Рисовать_статистику выполняет рисование на игровом поле информации о количестве захваченных точек и территории для каждого игрока (Рисунок 2.10).

Рисунок 2.10. Статистика

В процедуре сначала происходит задание параметров для текста: шрифт, его размер, стиль и ширина символа. Затем для каждого игрока выполняется отображение его статистики (Листинг 2.19)

Листинг 2.19 - Процедура Рисовать_статистику

Процедура Рисовать_сетку отвечает за рисование клетчатого поля. (Рисунок 2.11).

Рисунок 2.11. Клетчатое поле

В первом цикле рисуются горизонтальные линии, а во втором - вертикальные (Листинг 2.20)

Листинг 2.20 - Процедура Рисовать_сетку

Процедура Рисовать_последние_ходы выполняет рисование овала вокруг последней поставленной каждым игроком точки (Рисунок 2.12) (Листинг 2.21).

Рисунок 2.12. Последние ходы игроков

Листинг 2.21 - Процедура Рисовать_последние_ходы

Интересным алгоритмом, включающим в себя вызов подпроцедур, является рисование точек. Рассмотрим процедуру Рисовать_точки (Листинг 2.22). Проходим циклом по полю и рисуем каждый его узел (Листинг 2.23).

Листинг 2.22 - Процедура Рисовать_точки

Листинг 2.23 - Процедура Рисовать_узел

Узлы - это все точки поля (свободные и захваченные). У свободной точки нет области или точка принадлежит области своего игрока (Рисунок 2.13). Иначе считается, что точка захвачена (Рисунок 2.14).

Рисунок 2.13. Красные точки, находящиеся в окружении, принадлежат области своего игрока

Рисунок 2.14. Точка захвачена

В процедуре Рисовать_узел вызываются подпроцедуры рисования свободной и занятой точек (Листинг 2.24, Листинг 2.25).

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

Листинг 2.24 - Процедура Рисовать_свободную

Листинг 2.25 - Процедура Рисовать_взятую

Далее рассмотрим процедуру Рисовать_карандаш, она отвечает за отрисовку курсора мыши при наведении на клетчатое поле (Листинг 2.26). Курсор представляет собой перпендикулярное пересечение двух диагональных отрезков (Рисунок 2.8). Отрезки рисуются с помощью функции DrawLine заданного цвета, для игрока, который должен сделать очередной ход.

Листинг 2.26 - Процедура Рисовать_карандаш

Ещё одним компонентом, носящим информационный характер, является так называемый статус - номер очередного хода с координатами (Рисунок 2.15). Его рисование реализовано в процедуре Рисовать_статус (Листинг 2.27).

Рисунок 2.15. Статус

Также как в процедуре Рисовать_статистику, в процедуре Рисовать_статус сначала происходит задание параметров текста. Затем функцией IntToString номер хода переводится в символьный тип. Координаты зависят от положения курсора на клетчатом поле и, также как номер хода, переводятся в символьный тип. После этого происходит рисование строки статуса функцией DrawString.

Листинг 2.27 - Процедура Рисовать_статус

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

Одним из интересных алгоритмов реализации игры «Точки» является алгоритм рисования границ. Алгоритм реализован в процедуре Рисовать_границы (Листинг 2.28). Данная процедура состоит из подпроцедур с тремя циклами.

В первом цикле перебираются все пересечения, кроме крайних (горизонтальных и вертикальных); если у точки есть граница, то вызываются процедуры Вверх_вправо и Вниз_вправо, которые рисуют границы (в случае, когда там есть граничная точка) по следующим направлениям: вверх, диагонально вверх-вправо, вправо и вниз, диагонально вниз-вправо, вправо, соответственно (Рисунок 2.16). Защиту от рисования «ненужных» диагоналей обеспечивает процедура проверки Внутренняя_клетка. Данная процедура проверяет диагональные точки, образующие границы. Когда эти парные диагональные точки принадлежат одной области, они образуют так называемую внутреннюю клетку (Рисунок 2.17)

Во втором цикле перебираются точки верхнего и нижнего горизонтальных пересечений. Если в верхнем горизонтальном пересечении находится точка с границей, то для нее вызывается процедура Вниз_вправо. Для нижнего горизонтального пересечения, в аналогичном случае, вызывается процедура Вверх_вправо (Рисунок 2.18). Рисование границы происходит до того узла, где есть граничная точка.

Третий цикл в процедуре Рисовать_границы предназначен для отрисовки границ по правой боковой стороне клетчатого поля. Когда там есть граничная точка, то выполняется процедура Вверх, которая рисует границу вверх, если в этом узле тоже находится граничная точка (Рисунок 2.19). Для левой боковой стороны граница будет прорисована процедурой Вниз_вправо.

Использование такого метода рисования границ позволяет избежать проверок границ клетчатого поля.

Листинг 2.28 Процедура Рисовать_границы

Рисунок 2.16. Рисование границ для точек центральной части поля

Рисунок 2.17. Внутренняя клетка

Рисунок 2.18. Рисование границ для точек верхней и нижней части поля

Рисунок 2.19. Рисование границ для точек боковой части поля

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

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

.3.1 Сохранение

Рассмотрим, как происходит сохранение игры. После щелчка мыши в командном листе по коммандеру ТочкиКоманды. Сохранить_историю в модуле ТочкиКоманды вызывается процедура Сохранить_историю (Листинг 2.29).

Листинг 2.29. Процедура Сохранить_историю

В переменную «история» заносятся связанные списки ходов с координатами точек. Это происходит с помощью функции История, реализованной в модуле ТочкиХранение.

Затем из того же модуля вызывается процедура В_текст, которая и реализует запись содержимого переменной «история» в текстовую форму (Листинг 2.30).

Листинг 2.30. Процедура В_текст

Результатом выполнения процедуры Сохранить_историю будет являться текстовая вьюшка с номерами ходов и их координатами (Рисунок 2.20).

Рисунок 2.20. Сохраненная история

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

История игры воспроизводится путем считывания сохраненных ходов из текстовой вьюшки. Загрузка происходит после нажатия коммандера с командой Загрузить_историю. Происходит вызов процедуры (Листинг 2.31).

Листинг 2.31 - Процедура Загрузить_историю

Прежде всего считываются сохраненные размеры игрового поля (ш, в) и количество игроков (игроков).

Далее в переменную «история» помещается результат процедуры. Из_текста модуля ТочкиХранение - список считанных ходов.

Затем создается новая игра со считанными параметрами ш, в, игроков и открывается игровое поле. В диалоговом окне можно задать, на сколько ходов вперед или до какого хода проиграть игру (Рисунок 2.21).

Рисунок 2.21. Воспроизведение игры

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

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

В ходе дипломного проекта программно был реализован каркас ИИ для позиционной игры «Точки». Разработанный каркас основан на концепции позиционного «искусственного интеллекта» и имеет разъёмы, а также стандарт обмена данными для подключения разных модулей эвристического анализа. Подключаемый модуль анализирует каждое место возможного хода по какому-то эвристическому признаку и записывает результат на «центральную доску». После работы всех таких модулей выполняется процедура общего оценивания над доской, присваивающая каждому ходу одну численную оценку.

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

В первую очередь выполнена сборка и испытание описанного каркаса с некоторыми простыми модулями анализа (на сомкнутость - прямую и диагональную, на защиту от разрыва диагональной линии противником - и т. п.) (Рисунок 2.22).

Рисунок 2.22. Эвристики: классы ходов

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

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

Направлениями постепенного усовершенствования данной системы являются:

а) увеличение арсенала модулей эвристического анализа и схем их совместного включения;

б) экспериментальный подбор логики выведения общей оценки для хода;

в) выбор хода не только на основе простой численной оценки.

Кроме того, имеется направление радикального развития системы: разработка онлайн-версии игры для отработки ИИ в «живом окружении», а также разработка многопользовательской стратегической онлайн-игры по мотивам «Точек» (проект развлекательного характера).

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

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

Компьютерная игра «Точки» - программа, предназначенная для игры в одноименную популярную логическую игру.

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

Компьютерная игра «Точки» разработана на языке Компонентный Паскаль в среде BlackBox Component Builder. Программа позволяет играть в игру как двум игрокам, так и против компьютера. Реализована функция сохранения и проигрывание игры. Программа обладает удобным, простым и оригинальным интерфейсом, позволяющим легко производить настройки по изменению размеров игрового поля, его цвета, а так же изменение цвета точек игроков.

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

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

Расчет себестоимости разработки программы производится по формуле (3.1).

, (3.1)

где С - себестоимость программы, руб.;

Зр - заработная плата разработчика, руб. и отчисления на социальное страхование, руб.;

Рэ - расходы на эксплуатацию оборудования, руб.;

Нр - накладные расходы (50% от основной заработной платы разработчика), руб.

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

, (3.2)

где Зо - основная заработная плата программиста за время разработки программы, руб.;

Здоп - дополнительная заработная плата, руб. (принять 12% от основной);

Осоц - отчисления на социальное страхование, руб. (26 % от суммы Зо и Здоп).

Заработная плата программиста за период разработки программы вычисляется по формуле (3.3)

, (3.3)

где Сч - заработная плата за один час работы специалиста, руб.;

Тпр - время, затраченное на создание программы, час.;

Тпр может быть технически обоснованным и определяться на основе нормативных документов или опытно - статистически.

Расчет стоимости 1 часа работы программиста производится по формуле (3.4).

, (3.4)

где Зпм - заработная плата программиста за месяц, (8000 руб.);- количество рабочих дней в месяце, дни (22 дня);

8 - продолжительность рабочего дня, час.

Расходы на эксплуатацию оборудования вычисляются по формуле (3.5).

, (3.5)

где Сэн - стоимость электроэнергии, руб.;

Ао - сумма амортизации за время разработки программы, руб.;

Срем - стоимость ремонта оборудования, руб.;

Зоп - заработная плата обслуживающего персонала за время разработки программы, (руб.)

Стоимость электроэнергии вычисляется по формуле (3.6).

, (3.6)

где Мпр - электроэнергия, потребляемая вычислительной машиной, кВт/час;

Тм - машинное время, затраченное на создание программы, час. (принять 50% от Тпр);

Сквт/ч - стоимость одного квт/ч, (2,28 руб.)

Сумма амортизации за период разработки программы вычисляется линейным методом по формуле (3.7).

, (3.7)

где На - годовая норма амортизации, % рассчитывается по формуле (3.8);

, (3.8)

Соб - стоимость оборудования, руб.;

Тн - нормативный срок службы, год;

Фд - годовой фонд рабочего времени оборудования, час. Определяется по формуле (3.9).

 = ((365-С-В-Пр)*8-ППр*1) * S * (1-а/100), (3.9)

где 365 - количество календарных дней в году;

С, В, Пр - количество нерабочих дней в году: субботних, воскресных и праздничных;

8 - длительность смены, ч;

S - количество смен работы оборудования в сутки;

а - процент потерь времени на ремонт оборудования (принять а = 3-5%)

Стоимость ремонта оборудования за период создания программы определяется по формуле (3.10).

, (3.10)

где Нр - величина отпускаемых средств на ремонт вычислительной техники относительно стоимости этой техники, % (принять 2-4%);

Соб - стоимость оборудования, руб.

Заработная плата обслуживающего персонала за время разработки программы рассчитывается по формуле (3.11).

, (3.11)

где Зоп.о - основная заработная плата обслуживающего персонала за выполненную работу, руб.;

Зоп.доп - дополнительная заработная плата обслуживающего персонала, руб. (10% от основной);

Осоц - отчисления на социальное страхование, руб. (26% от основной и дополнительной заработной платы)

Основная заработная плата обслуживающего персонала за время разработки программы определяется по формуле (3.12).

где n - количество обслуживаемых ПЭВМ, шт.;

Зоп.год - годовая заработная плата обслуживающего персонала по категориям работников, руб.

Трудоемкость программы может определяться либо по нормативам, либо по экспертным оценкам, то есть на основании опытно-статистических данных специалистов-программистов, дающих пессимистические, оптимистические оценки. Вычисляется ожидаемая длительность работ по формуле (3.13).

, (3.13)

где Тож - применяемая для расчета трудоемкость программы Тпр, дни;

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

Таблица 3.1

Ожидаемая длительность работ на этапе проектирования программы

Примечание: звездочкой помечены работы, производимые с помощью ЭВМ.

В результате расчета на разработку программы было затрачено 86 дня, из них с использованием ЭВМ - 65 дней. Учитывая, что число часов работы в день равно 8, на разработку программы было затрачено 688 часа, из них 520 часа - время работы на ЭВМ.

Данные для расчета себестоимости программы игры «Точки» сведем в таблицу 3.2.

Таблица 3.2

Данные для расчёта себестоймости

Данные об обслуживающем персонале приведены в таблице 3.3.

Таблица 3.3

Обслуживающий персонал

Стоимость 1 часа работы программиста, рассчитанная по формуле (3.4), составляет:

Основная заработная плата программиста за время разработки программы рассчитывается по формуле (3.3):

Дополнительная заработная плата составляет 12% от Зо:

Отчисления на социальное страхование составляют 26% от суммы  и : 

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

Стоимость электроэнергии рассчитывается по формуле (3.6) и составляет:

Норма амортизации рассчитывается по формуле (8):

Сумма амортизации, рассчитанная по формуле (3.7), составляет:

Стоимость ремонта оборудования рассчитывается по формуле (3.10) и составляет:

Основная заработная плата обслуживающего персонала за время разработки программы рассчитывается по формуле (3.12) и составляет:

Дополнительная заработная плата составляет:

Отчисления на социальное страхование составляют:

Таким образом, заработная плата обслуживающего персонала за время создания программы, рассчитывается по формуле (3.11) и составляет:

Расходы на эксплуатацию оборудования вычисляются по формуле (3.5) и составляют:

Накладные расходы составляют 50% от :

По итогам проведенных расчетов себестоимость программы составляет:

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

Продажа компьютерной игры «Точки» будет осуществляться через Интернет. На сайте www.game-master.ru будут размещены ссылки для скачивания игры «Точки».

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

Месячные поступления денежных средств рассчитаем по формуле (3.13):

 , (3.13)

где стоимость скачивания игры, руб.;

- количество скачиваний

Скачивание игры стоит 187 рублей. За месяц, по результатам маркетинговых исследований, игру «Точки» будут скачивать не менее 100 раз в месяц. Следовательно, месячный доход от скачиваний  составит:

Годовой доход от скачиваний игры  рассчитаем по формуле (3.14):

, (3.14)

где - месячные поступления денежных средств, руб.

Прибыль () - разность между годовым доходом и себестоимостью реализованной компьютерной игры:

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

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

Срок окупаемости рассчитаем по формуле (3.15):

, (3.15)

где  - срок окупаемости компьютерной игры, год;- себестоимость компьютерной игры, руб. (п. 3);

П - прибыль от реализации компьютерной игры, руб. (п.4)

Срок окупаемости составляет:

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

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

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

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

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

Чтобы снизить вредное влияние различных производств на здоровье человека, медики разрабатывают жесткие нормы и требования, обязательные к выполнению. Эти требования носят название санитарных правил и норм. В 1996 году Государственный комитет санитарно-эпидемиологического надзора утвердил "Гигиенические требования к видеодисплейным терминалам, персональным ЭВМ и организации работы". Этот документ содержит детальные рекомендации, как правильно работать за компьютером. Существует также несколько международных санитарно-гигиенических стандартов.

Рассмотрим основные требования к организации работы за компьютером и рекомендации по их выполнению.

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

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

Желательно, чтобы площадь рабочего места составляла не менее 6 , а объем - 20 . Стол следует поставить сбоку от окна так, чтобы свет падал слева. Наилучшее освещение для работы с компьютером - рассеянный непрямой свет, который не дает бликов на экране. В поле зрения пользователя не должно быть резких перепадов яркости, поэтому окна желательно закрывать шторами либо жалюзи. Искусственное же освещение должно быть общим и равномерным, в то же время использование одних только настольных ламп недопустимо.

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

На рабочем столе должны свободно помещаться монитор, клавиатура, мышь и другое компьютерное оборудование, а также документы, книги, бумаги (Рисунок 4.1).

Рисунок 4.1.Рабочий стол

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

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

Чтобы определить наиболее подходящую высоту стула, сядьте на него и положите руки на клавиатуру: ноги должны полностью касаться пола, бедра - находиться немного выше колен, спина - чувствовать упор, а предплечья - быть параллельными полу.

Монитор следует размещать на столе прямо перед собой. Расстояние от глаз до экрана монитора должно быть не менее 70 см (Рисунок 4.2).

Рисунок 4.2.Положение монитора

Что касается минимально допустимого расстояния, то, с научной точки зрения, глаз человека четко видит в радиусе 17 градусов (сверху вниз). Отсюда легко подсчитать, что минимальное расстояние от лица человека до монитора - это размер диагонали монитора. Монитор должен стоять примерно на 10 градусов ниже условной горизонтали, находящейся на уровне глаз (т. е. взгляд на экран - сверху вниз). Освещение должно располагаться таким образом, чтобы смягчать блики на экране (желательно, чтобы их вообще не было). То есть экран монитора не должен отражать посторонний свет. Лучше всего, если плоскость экрана монитора будет перпендикулярна к источнику света. В сумерках над рабочим местом нужен дополнительный мягкий свет. Каждые полчаса старайтесь отвлекаться от монитора и смотреть вдаль - такая нехитрая гимнастика помогает сохранить зрение. Иногда закрывайте глаза на две-три минуты, благодаря чему расслабляются (отдыхают) мышечные волокна и, как следствие, восстанавливается чувствительность рецепторов глаз, отвечающих за четкость и яркость.

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

Конструкция современных клавиатур и мышей предусматривает для них опору. Однако вы легко можете сами изготовить ее, например, взяв узкую полоску пенопласта и положив ее перед клавиатурой или мышью (однако следует учитывать, чтобы материал не вызывал чрезмерного раздражения рецепторов кожи (аллергические реакции), что может привести к возникновению заболеваний кожи). Клавиатура должна располагаться в 10-15 сантиметрах от края стола (Рисунок 4.3).

Рисунок 4.3.Правильное положение рук

Иногда полезно пользоваться подставкой для ног. Она просто необходима для людей невысокого роста или детей, играющих за компьютером, у которых ноги не достают до пола.

Заключение

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

В ходе работы были получены следующие результаты:

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

Предложен некоторый подход разработки ИИ для позиционных игр, на примере игры «Точки».

Создан программный каркас для экспериментов с данным методом.

Разработаны различные модули искусственного интеллекта для игры «Точки», проведено их сравнение с существующими системами.

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

Литература:

1. Шень, А. Игры и стратегии с точки зрения математики. / А. Шень. - М.: МЦНМО. - 2008.

. Осипов, Ю.С. Пакеты программ: подход к решению задач позиционного управления с неполной информацией. // Успехи математических наук. - Т. 61, вып. 4 (370). - 2006. - с. 25-75.

. Красовский, Н.Н.; Субботин, А.И. Позиционные дифференциальные игры. - М.: Наука. - 1974.

. Бурлак, Г.Н.; Благодатских, В.А. Экономические аспекты разработки и использования программного обеспечения. / Г.Н. Бурлак, В.А. Благодатских. - М.: МЭСИ. - 1990.

. Типовые нормы времени на программирование задач для ЭВМ.  - М.: Экономика. - 1987.

. Вирт, Н. Алгоритмы и структуры данных. / Н. Вирт. - М.: ДМК. - 2010.

. Вирт, Н. Построение компиляторов. / Н. Вирт. - М.: ДМК. - 2010.

8. Проект OberonCore. Web: <http://oberoncore.ru>