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

Главная

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

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

1.1 Характеристика и анализ решаемых задач
1.2 Позиционная игра «Точки». Правила игры
1.4 Актуальность разработки "искусственного интеллекта" для позиционных игр
1.5 Анализ существующих подходов программирования "искусственного интеллекта"
1.6 Концепция позиционного "искусственного интеллекта"
2.1 Проектирование и разработка общей структуры системы
2.2.2 Отрисовка основных элементов поля
2.3 Реализация сохранения и воспроизведения игры
2.4 Проектирование позиционного «искуственного интеллекта» (ИИ)
2.4.2 Направления развития решающей части
3.1 Характеристики программы для игры в «Точки»
3.3 Расчёт поступления денежных средств от реализации компьютерной игры «Точки»
3.4 Расчёт срока окупаемости затрат на разработку компьютерной игры «Точки»
С развитием компьютерной техники и информационных систем во всех сферах человеческой деятельности появляются задачи, решение которых требуют создания систем, частично или полностью заменяющих специалиста, а так же позволяющих имитировать различные ситуации и процессы реального мира для выработки стратегий действия в этих ситуациях. Такие системы позволят решать множество задач в экономике и управлении, политике и военном деле.
Как показывает практика, моделью ситуаций реального мира являются позиционные игры. Следовательно, целесообразно вести поиски решения данных задач именно на основе позиционных игр. Разработки «искусственного интеллекта» (ИИ) для позиционных игр, а именно, для шахмат ведутся с конца 50-х годов XX века. За это время компьютерная техника всё более совершенствовалась, и алгоритмы программ, соответственно, усложнялись. Однако до сих пор такие программы основаны на алгоритмах перебора. Для игр типа шахмат и шашек данные алгоритмы являются весьма эффективными, но методы и технология разработки такого «искусственного интеллекта» достаточно примитивна и мало интересна, так как скорость перебора зависит лишь от мощности компьютера.
В силу такой ситуации, чтобы создать мощный «искусственный интеллект» для класса позиционных игр требуется разработка нового подхода, который будет существенно отличаться от метода простого перебора.
В качестве основы для исследования выбрана игра «Точки», которая является упрощённым вариантом классической японской игры Го. До сих пор не существует систем, играющих в Го лучше, чем начинающий игрок. Существующие реализации играющей части так же, как и в шахматах, основаны на переборе дерева вариантов, но перебор в Го («Точки») усложняется значительно большей величиной дерева. В реализованных системах просчёты ведутся лишь на три-четыре пары ходов. Это ещё раз доказывает то, что перебор дерева вариантов и его последующие модификации не являются эффективными для решения задачи создания систем принятия решений. Для создания эффективной системы принятия решений требуется создание концепции позиционного «искусственного интеллекта».
Суть данного дипломного проекта заключается в разработке на основе игры «Точки» подхода к программированию «искусственного интеллекта» в позиционных играх, а также возможность применения данного подхода для решения задач в области экономики и управления и в других областях науки и техники.
1.1 Общая характеристика и анализ решаемых задач
Цель проекта -- исследовать подходы к программированию систем принятия решений в позиционных играх. К классу позиционных игр относятся многие задачи из области экономики и управления, а также других областей науки и техники. В отличие от игр комбинаторного характера, известные успехи программирования позиционных игр пока невелики. Успешные исследования и разработки по программированию систем принятия решений, возможно, станут применимы для решения задач в практической деятельности.
В ходе работы были поставлены следующие базовые задачи:
Разработать программу для игры в «Точки».
Разработать каркас для организации игрового ИИ.
Решение поставленных базовых задач заключается в следующем:
Разработана программа, поддерживающая процесс игры в «Точки» для двух игроков и возможное подключение вместо одного или двух игроков модулей ИИ. В том числе имеется реализация сетевой игры, с возможным подключением наблюдателей.
Разработаны отдельные компоненты анализа, оценки и прогнозирования игровой ситуации по разным критериям.
Реализован базовый игровой ИИ, имеющий дальнейшие перспективы развития.
1.2 Позиционная игра «Точки» . Правила игры
Игра «Точки» представляет собой упрощенный вариант японской игры «Го». Два игрока на клетчатом поле заданного размера ставят по очереди точки своего цвета. Игрок стремится окружить точки противника замкнутым контуром. Точки и территория, окруженная другим игроком, считается захваченной. Следовательно, основная цель игры -- захватить как можно больше точек противника и территории поля (Рисунок 1.1).
Рисунок 1.1. Пример игровой ситуации
Несмотря на столь простые правила игры «Точки», её программная реализация достаточно сложна. Причины сложности программирования хорошо выявляются при сравнении игры «Точки» и шахмат. В начале партии в шахматах можно сделать около 20-ти различных ходов, в точках -- около 900. Соответственно, дерево просчета ходов в шахматах разрастается как геометрическая прогрессия с основанием 20, а в точках -- с основанием 900. Основная же сложность точек заключается не в огромном числе всевозможных позиций, а в том, что «Точки» -- это игра в основном позиционная, в отличие от тех же шахмат, которые являются в значительной степени комбинаторной игрой. Всё это затрудняет создание хорошего искусственного интеллекта, и большинство созданных программ, играющих в «Точки», основаны на неточных, в данном случае, алгоритмах частичного перебора дерева ходов. Недостаток алгоритма перебора дерева ходов очевиден, поэтому для создания качественного искусственного интеллекта нужен новый подход, который бы учитывал то, что ситуация в игре гораздо более «непрерывна», «локально обусловлена»: каждый ход влияет на небольшую окрестность поля. Ходы на этом участке поля подчиняются неким «предсказуемым» правилам, т.е. они единообразны, однородны. Для использования этой особенности требуется разработка особых алгоритмов, «видящих» ситуацию на поле образно (функция «машинного зрения»).
1. 4 Актуальность разработки «искусственного интеллекта» для позиционных иг р
Многие практические задачи реального мира, для которых требуется разработка систем принятия решений, имеют позиционный, стратегический характер. К таким задачам можно отнести различные задачи экономики и управления, задачи стратегического планирования. Позиционные черты можно выделить в следующих областях: биология, экология, военное дело, психология, социология, управление государством и регионом и многое другое.
Кроме того, «искусственный интеллект» необходим в области компьютерных стратегических и онлайн игр.
Следовательно, можно сделать вывод о том, что при дальнейшем развитии науки и техники наработанные подходы в области систем принятия решений станут весьма полезны для решения конкретных задач.
1. 5 Анализ существующих подходов программирования позиционных игр
Если говорить о программировании логических игр, то доминирующим подходом является перебор на дереве вариантов. Исследования в области перебора на дереве ходов преимущественно строятся на базе его усовершенствований, например, посредством введения эвристических критериев отсечения неперспективных веток дерева.
Перебор на дереве ходов является неэффективным для игры «Точки» из-за взрывной скорости роста дерева вариантов. Поэтому принято решение отказаться от этого метода как стержня системы. Однако, не исключено, что перебор на дереве вариантов будет применен в качестве локального средства.
Если говорить о прикладных системах принятия решений, то в них применяются разного рода специализированные математические модели, которые не применимы в выбранной задаче (например, теория позиционных игр, связанных с преследованием цели).
Программ игры в «Точки», которые имеют «искусственный интеллект», существует мало. Все те, которые известны нам, организованы на базе перебора на дереве вариантов, играют на уровне игрока-новичка, страдают «стратегической слепотой» и не имеют качественных возможностей для совершенствования.
1. 6 Концепция позиционного «искусственного интеллекта»
В ходе исследовательской работы сложилась концепция позиционного искусственного интеллекта для игры «Точки». Она заключается в том, что искусственный интеллект должен опираться на ряд независимых модулей, которые будут классифицировать ходы и последовательности ходов по различным эвристическим оценкам. Такие эвристики будут опираться на статус точки, который она приобретет в момент хода. Например: ход может стать частью окружения; ход является смежным с существующей группировкой точек; ход является оборонительным, ход препятствует планам противника и т.п. (Рисунок 1.2)
Далее на основании сводной оценки система выбирает очередной ход. При этом некоторые оценки должны опираться на прогнозирование. Прогнозирование должно быть основано не на переборе ходов, а на просмотре трансформаций текущей позиции с отбором интересных возможностей. Наконец, наиболее сложным и мощным компонентом искусственного интеллекта может стать механизм, подобный человеческому зрению, «машинное зрение» -- с ассоциативным узнаванием интересных элементов позиций.
Программно каркас для ИИ имеет разъёмы и стандарт обмена данными для подключения разных модулей эвристического анализа. Подключаемый модуль анализирует каждое место возможного хода по какому-то эвристическому признаку и записывает результат на «центральную доску». После работы всех таких модулей выполняется процедура общего оценивания над доской, присваивающая каждому ходу одну численную оценку.
В первую очередь выполнена сборка и испытание описанного каркаса с некоторыми простыми модулями анализа (на сомкнутость -- прямую и диагональную, на защиту от разрыва диагональной линии противником -- и т. п.). Сравнение игры с другими существующими реализациями дало обнадёживающие результаты: простейший начальный вариант ИИ ведёт оборонительную игру не хуже, чем сложные системы, в которых применён классический перебор с множеством эвристических оптимизаций.
Направлениями постепенного усовершенствования данной системы являются:
- увеличение арсенала модулей эвристического анализа и схем их совместного включения;
- экспериментальный подбор логики выведения общей оценки для хода;
- выбор хода не только на основе простой численной оценки.
Кроме того, имеется направление радикального развития системы: снятие «стратегической слепоты» путем применения полевых алгоритмов, разработка онлайн-версии игры для отработки ИИ в «живом окружении», а так же разработка многопользовательской стратегической онлайн-игры по мотивам «Точек» (проект развлекательного характера).
2.1 Проектирование и разработка общей структуры системы
Проектной частью дипломной работы является расширяемая программа игры в «Точки» для двух игроков, разработанная на языке Компонентный Паскаль в среде BlackBox Component Builder. Структура программы состоит из отдельных модулей, взаимодействующих друг с другом (Рисунок 2.1)
Модель игровой ситуации формируется в модуле ТочкиИгра. В этом модуле реализована основная логика игры -- хранение ходов, расчёт захваченных областей и их границ.
Графика и интерфейс игры реализованы в модуле ТочкиГрафика. Данный модуль включает в себя процедуры по отрисовке основных элементов поля, цветовой настройке поля.
Сохранение и загрузка с проигрыванием игры реализованы в модуле ТочкиХранение.
Сетевая игра реализована в модуле ТочкиСетевая. С помощью модуля ТочкиСетевая осуществляется игра по сети с возможным подключением наблюдателей.
Решающая часть реализована в модуле ТочкиРешатели. Данный модуль содержит оценочные алгоритмы, позволяющие подключать в качестве одного или двух игроков модули «искусственного интеллекта».
Модель игровой ситуации обеспечивается модулем ТочкиИгра. В этом модуле реализованна основная логика программы, включающая в себя различные функции для создания модели игровой ситуации.
Рассмотрим основные типы данных, используемые в модуле ТочкиИгра (Листинг 2.1).
Листинг 2.1 - Интерфейс модуля ТочкиИгра
Игра - указательный тип записи, имеющие следующие поля:
поле-: Поле; -- двумерный динамический массив типа Узел.
игроков-: INTEGER - количество игроков, для которых создается игра.
ход-: INTEGER - номер текущего хода.
статистика-: Статистика - структура данных, хранящая в себе количество пленных точек и захваченную территорию.
(и: Игра) Сделать_ход (x, y, игрок: INTEGER), NEW - метод у типа Игра. Вызывается, в частности, в модуле ТочкиГрафика. (при щелчке мышки по полю области игры).
Область - указательный тип записи, являющийся определяющим типом для поля область- и поля граница- в записи Узел.
игрок-: INTEGER - какому игроку принадлежит область;
точек_противника: INTEGER - сколько точек противника находится в области игрока.
Узел - тип записи, для определения игрового поля (Листинг 2.2).
точка_игрока-: INTEGER - указывает, какому игроку принадлежит поставленная точка.
поставлена_на_ходе-: INTEGER - поле хранит в себе номер хода, на котором была поставлена точка_игрока.
была_в_плену-: BOOLEAN - принимает одно из двух состояний в зависимости от игровой ситуации, которым определяется статус точки.
Новая_игра - процедура фабрика с параметрами:
ш, в: INTEGER - размеры игрового поля.
игроков: INTEGER - количество игроков, для которых создается игра.
Наиболее интересными видами алгоритмов в программной реализации модели игровой ситуации игры «Точки», являются волновые алгоритмы. На двумерной клетчатой матрице (поле), есть «занятые» и «свободные» пересечения. Цель алгоритма -- выделить замкнутые области на поле. По полю во все направления распространяется волна, причем каждая пройденная волной клетка помечается как клетка, в которой волна есть, т.е. она доступна для волны (не является внутренней для области). Волна расширяется, пока имеется такая возможность, т.е. имеются доступные клетки, не занятые волной.
Волновые алгоритмы в программе игры «Точки» используются для определения замкнутых контуров, принадлежности точки захваченной области. Рассмотрим эти алгоритмы подробнее.
После того, как создана новая игра, игроки поочередно ставят точки. За каждый новый ход отвечает процедура Сделать_ход. Процедура имеет параметры x, y - координаты точки, игрок - какой игрок делает ход.
Прежде всего проверяются предусловия того, что точка с координатами x, y свободна и номер игрока допустимый ( Листинг 2.3)
Листинг 2.3 - Процедура Сделать_ход
Если эти условия выполняются, то поставленная точка становится точкой игрока, сделавшего ход, а в поле и.поле[x,y].поставлена_на_ходе присваивается номер текущего хода. Номер текущего хода увеличивается.
Затем вызывается процедура Перерасчёт (Листинг 2.4).
В процедуре Перерасчёт сначала происходит выполнение процедуры Очистить_области для игрового поля (Листинг 2.5).
Листинг 2.5 - Процедура Очистить_области
После выполнения этой процедуры у каждой точки игрового поля отсутствуют области и границы.
Расчет областей и границ выполняется, начиная с последнего игрока, сделавшего ход, так как на практике возникает ситуация, когда у одного игрока имеется область, в которой находится пересечение, не занятое точкой ни одного игрока. (Рисунок 2.2) Если синий игрок поставит точку в пустое пересечение, точка красного игрока окажется пленной, а область, ранее ему принадлежащая, перестанет существовать (Рисунок 2.3).
Рисунок 2.2. Область с пустым пересечением
Расчет областей происходит в процедуре Рассчитать_области (Листинг 2.7)
Листинг 2.7 - Процедура Рассчитать_области
Расчет областей происходит методом волнового распространения. В разделе описания переменных заводим переменную двумерного динамического массива логического типа - «волна». Переменная «расширение» служит показателем того, что на предыдущей итерации цикла было дальнейшее распространение волны. Затем создаем двумерный логический массив «волна».
Начинаем распространение волны процедурой Начать_волну (Листинг 2.8).
Листинг 2.8- Процедура Начать_волну
Процедура Начать_волну расставляет признаки волны по краям поля, там, где нет точки игрока.
Первый цикл проверяет верхнюю и нижнюю полосы пересечений, второй - правую и левую.
Затем, выполняем распространение волны по центральной части поля (Листинг 2.9). Процедура Ход_волны выполняется до тех пор, пока волне некуда будет расширяться.
Листинг 2.9 -- Распространение волны по центральной части поля
Рассмотрим подробнее процедуру Ход_волны (Рисунок 2.10).
Суть её заключается в том, чтобы проверить точки центральной области поля и распространить в них, если возможно, волну. Для этого принимаем, что волна расшириться дальше не может (расширение := FALSE). В цикле проверяем, соответствует ли точка [i, j] условию того, что в этой точке нет волны, но волна может быть и ей есть откуда прийти (волна рядом). Волна рядом, если в одном из соседних пересечений волна уже есть. (Листинг 2.11)
Если условие проверки выполняется, то данная точка доступна для волны, произошло расширение.
Листинг 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.16 - Процедура Добавить_границу
Рисунок 2.6 - Точка, имеющая две границы
В среде BlackBox Component Builder создаваемые графические объекты называются отображениями (вьюшками) и являются подтипом абстрактного типа Views.View. Отображения являются универсальным элементом BlackBox Framework, так как большинство команд выполняются над отображениями, окна показывают отображения, отображения могут быть загружены и выгружены, с помощью отображений проводится взаимодействие с пользователем и отображения могут быть внедрены в другие отображения.
Основным типом в модуле ТочкиГрафика является тип View (Листинг 2.17).
Тип View представляет собой набор элементов (полей), необходимых для отрисовки основных элементов игрового поля.
Поле «игра» имеет тип Игра.Игра, который импортирован из модуля ТочкиИгра и необходим для доступа к таким полям, как «поле», «игроков», «статистика».
Поле «последние_ходы_игроков» необходимо для пометки последней поставленной точки каждого игрока (Рисунок 2.7). Данное поле представляет собой массив типа Ход, в котором хранятся координаты поставленных точек.
Рисунок 2.7. Последние ходы игроков
Поле «карандаш» хранит положение курсора мыши, который перемещается по игровому полю и показывает, какой игрок должен сделать ход (Рисунок 2.8).
2.2.2 Отрисовка основных элементов поля
В Компонентном Паскале отрисовкой вьюшки занимается связанная с типом процедура Restore (Листинг 2.18).
В результате выполнения процедуры Restore будет отрисовано игровое поле (Рисунок 2.9). Оно включает в себя несколько элементов. Это статистика для каждого игрока, клетчатое поле, точки свободные и захваченные, последний ход для каждого игрока, курсор, номер текущего хода и его координаты. Рассмотрим подробнее, как происходит рисование этих элементов.
Процедура Рисовать_статистику выполняет рисование на игровом поле информации о количестве захваченных точек и территории для каждого игрока (Рисунок 2.10).
В процедуре сначала происходит задание параметров для текста: шрифт, его размер, стиль и ширина символа. Затем для каждого игрока выполняется отображение его статистики (Листинг 2.19)
Листинг 2.19 - Процедура Рисовать_статистику
Процедура Рисовать_сетку отвечает за рисование клетчатого поля. (Рисунок 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.24, Листинг 2.25).
Свободная и занятая точки рисуются с помощью функции DrawOval c параметрами. Параметры рисования свободной точки отличаются от параметров рисования захваченной тем, что свободная точка закрашенная и имеет цвет того игрока, кем поставлена. Захваченная точка - окружность (точка с не закрашенным центром).
Листинг 2.24 - Процедура Рисовать_свободную
Листинг 2.25 - Процедура Рисовать_взятую
Далее рассмотрим процедуру Рисовать_карандаш, она отвечает за отрисовку курсора мыши при наведении на клетчатое поле (Листинг 2.26). Курсор представляет собой перпендикулярное пересечение двух диагональных отрезков (Рисунок 2.8). Отрезки рисуются с помощью функции DrawLine заданного цвета, для игрока, который должен сделать очередной ход.
Листинг 2.26 - Процедура Рисовать_карандаш
Ещё одним компонентом, носящим информационный характер, является так называемый статус - номер очередного хода с координатами (Рисунок 2.15). Его рисование реализовано в процедуре Рисовать_статус (Листинг 2.27).
Также как в процедуре Рисовать_статистику, в процедуре Рисовать_статус сначала происходит задание параметров текста. Затем функцией IntToString номер хода переводится в символьный тип. Координаты зависят от положения курсора на клетчатом поле и, также как номер хода, переводятся в символьный тип. После этого происходит рисование строки статуса функцией DrawString.
Листинг 2.27 - Процедура Рисовать_статус
Одним из интересных алгоритмов реализации игры «Точки» является алгоритм рисования границ. Алгоритм реализован в процедуре Рисовать_границы (Листинг 2.28). Данная процедура состоит из подпроцедур с тремя циклами.
В первом цикле перебираются все пересечения, кроме крайних (горизонтальных и вертикальных); если у точки есть граница, то вызываются процедуры Вверх_вправо и Вниз_вправо, которые рисуют границы (в случае, когда там есть граничная точка) по следующим направлениям: вверх, диагонально вверх-вправо, вправо и вниз, диагонально вниз-вправо, вправо, соответственно (Рисунок 2.16). Защиту от рисования «ненужных» диагоналей обеспечивает процедура проверки Внутренняя_клетка. Данная процедура проверяет диагональные точки, образующие границы. Когда эти парные диагональные точки принадлежат одной области, они образуют так называемую внутреннюю клетку (Рисунок 2.17)
Во втором цикле перебираются точки верхнего и нижнего горизонтальных пересечений. Если в верхнем горизонтальном пересечении находится точка с границей, то для нее вызывается процедура Вниз_вправо. Для нижнего горизонтального пересечения, в аналогичном случае, вызывается процедура Вверх_вправо (Рисунок 2.18). Рисование границы происходит до того узла, где есть граничная точка.
Третий цикл в процедуре Рисовать_границы предназначен для отрисовки границ по правой боковой стороне клетчатого поля. Когда там есть граничная точка, то выполняется процедура Вверх, которая рисует границу вверх, если в этом узле тоже находится граничная точка (Рисунок 2.19). Для левой боковой стороны граница будет прорисована процедурой Вниз_вправо.
Использование такого метода рисования границ позволяет избежать проверок границ клетчатого поля.
Листинг 2.28 Процедура Рисовать_границы
Рисунок 2.16. Рисование границ для точек центральной части поля
Рисунок 2.18. Рисование границ для точек верхней и нижней части поля
Рисунок 2.19. Рисование границ для точек боковой части поля
2.3 Реализация сохранения и воспроизведения игры
В программе для игры в «Точки» реализованы функции сохранения и воспроизведения сохраненной игры. Сохранение игры реализовано как сохранение в текст, а воспроизведение - как считывание из текста.
Рассмотрим, как происходит сохранение игры. После щелчка мыши в командном листе по коммандеру ТочкиКоманды. Сохранить_историю в модуле ТочкиКоманды вызывается процедура Сохранить_историю (Листинг 2.29).
Листинг 2.29. Процедура Сохранить_историю
В переменную «история» заносятся связанные списки ходов с координатами точек. Это происходит с помощью функции История, реализованной в модуле ТочкиХранение.
Затем из того же модуля вызывается процедура В_текст, которая и реализует запись содержимого переменной «история» в текстовую форму (Листинг 2.30).
Результатом выполнения процедуры Сохранить_историю будет являться текстовая вьюшка с номерами ходов и их координатами (Рисунок 2.20).
История игры воспроизводится путем считывания сохраненных ходов из текстовой вьюшки. Загрузка происходит после нажатия коммандера с командой Загрузить_историю. Происходит вызов процедуры (Листинг 2.31).
Листинг 2.31 - Процедура Загрузить_историю
Прежде всего считываются сохраненные размеры игрового поля (ш, в) и количество игроков (игроков).
Далее в переменную «история» помещается результат процедуры. Из_текста модуля ТочкиХранение - список считанных ходов.
Затем создается новая игра со считанными параметрами ш, в, игроков и открывается игровое поле. В диалоговом окне можно задать, на сколько ходов вперед или до какого хода проиграть игру (Рисунок 2.21).
2 .4 Проектирование позиционного «искусственного интеллекта» (ИИ)
Концепция предлагаемого позиционного искусственного интеллекта для игры «Точки» заключается в том, что искусственный интеллект должен опираться на ряд независимых модулей, которые будут классифицировать ходы и последовательности ходов по различным эвристическим оценкам. Такие эвристики будут опираться на статус точки, который она приобретет в момент хода. Например: ход может стать частью окружения; ход является смежным с существующей группировкой точек; ход является оборонительным, ход препятствует планам противника и т.п. Далее на основании сводной оценки система выбирает очередной ход. При этом некоторые оценки должны опираться на прогнозирование. Прогнозирование должно быть основано не на переборе ходов, а на просмотре трансформаций текущей позиции с отбором интересных возможностей. Наконец, наиболее сложным и мощным компонентом искусственного интеллекта может стать механизм, подобный человеческому зрению, «машинное зрение» -- с ассоциативным узнаванием интересных элементов позиций.
В ходе дипломного проекта программно был реализован каркас ИИ для позиционной игры «Точки». Разработанный каркас основан на концепции позиционного «искусственного интеллекта» и имеет разъёмы, а также стандарт обмена данными для подключения разных модулей эвристического анализа. Подключаемый модуль анализирует каждое место возможного хода по какому-то эвристическому признаку и записывает результат на «центральную доску». После работы всех таких модулей выполняется процедура общего оценивания над доской, присваивающая каждому ходу одну численную оценку.
В первую очередь выполнена сборка и испытание описанного каркаса с некоторыми простыми модулями анализа (на сомкнутость -- прямую и диагональную, на защиту от разрыва диагональной линии противником -- и т. п.) (Рисунок 2.22).
Рисунок 2.22. Эвристики: классы ходов
Сравнение игры с другими существующими реализациями дало обнадёживающие результаты: простейший начальный вариант ИИ ведёт оборонительную игру не хуже, чем сложные системы, в которых применён классический перебор с множеством эвристических оптимизаций.
2. 4 .2 Направления развития решающей части
Направлениями постепенного усовершенствования данной системы являются:
а) увеличение арсенала модулей эвристического анализа и схем их совместного включения;
б) экспериментальный подбор логики выведения общей оценки для хода;
в) выбор хода не только на основе простой численной оценки.
Кроме того, им
Разработка подхода к программированию "искусственного интеллекта" в позиционных играх на основе игры "Точки" дипломная работа. Программирование, компьютеры и кибернетика.
Курсовая работа: Организация работы школьной столовой на 200 мест 2
Дипломная работа по теме Особенности методики расследования взяточничества
Требует Ли Любовь Работы Над Собой Сочинение
Курсовая работа: Эксплуатация и обслуживание башенного крана
Курсовая работа по теме Мониторинг форм продвижения товаров аптечного ассортимента в аптечной сети 'Живика'
Дипломная работа по теме Имущественные сделки супругов. Особенности правового регулирования
Контрольная работа по теме Ах, эти странные англичане!
Реферат по теме Репродуктивное поведение земноводных
Маленькое Сочинение Памятный День В Школе
Курсовая работа по теме Страховая отрасль в Республике Казахстан
Информатика Босова Самостоятельные И Контрольные Работы
Реферат: Взаимодействие аллельных генов
Реферат по теме Спортивный туризм
Реферат: Создание корпоративной культуры, поддерживающей стратегию компании
Реферат: Россия в конце 1920-х 1930-е годы
Производственная Практика Финансиста Отчет
Нужны Ли Перемены В Жизни Сочинение
Океан Кладовая Планеты Реферат
Конфликт Практическая Работа
Фипи Сочинение По Литературе 11 Класс 2022
Проектный метод на уроках "Технологии" (при изучении раздела "Лоскутная пластика") - Педагогика аттестационная работа
Нивелирование - Геология, гидрология и геодезия презентация
Формы соучастия по уголовному праву - Государство и право курсовая работа