Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Анализ моделей и методов реализации интеллектуальных игр в системе человек-робот
• 1.1 Выбор алгоритма игры
• 1.2 Передача данных игрового состояния
• 2. Разработка архитектуры программного комплекса
• 3. Разработка структур данных и знаний
• 3.1 Язык программирования
• 3.2 Структуры данных
• 3.3 Среда разработки Choreographe
• 4. Разработка алгоритмов
• 4.1 Алгоритмы модуля распознавания
• 4.2 Алгоритмы модуля обработки данных
• 4.3 Алгоритмы функций модуля игры
• 4.4 Алгоритмы выбора хода
• 4.5 Алгоритм преобразования и вывода данных
• 5. Разработка и реализация программных модулей
• 5.1 Разработка модуля распознавания
• 5.2 Разработка модуля обработки данных
• 5.3 Разработка модуля игры
• 5.4 Разработка модуля выбора хода
• 6. Экспериментальное тестирование и отладка програмных модулей
• 6.1 Тестирование программного комплекса
• 6.2 Поиск ошибок
• 6.3 Редактирование и исправление ошибок
• 7. Оценка качества разработанного продукта
• Заключение
• Список использованных источников
• Приложение
• Введение
• интеллектуальный игра программный choreographe
• Целью данного дипломного проекта является исследование алгоритмов принятия решений и обучение в программировании робототехнических устройств, а также введение материала по обучению в дисциплине «Интеллектуальные информационные системы» по направлению 09.03.02 и 09.04.02.
• Частью предмета интеллектуальные информационные системы является искусственный интеллект(ИИ). ИИ - это одно из направлений информатики, целью которого является разработка аппаратно-программных средств, позволяющих пользователю-непрограммисту ставить и решать свои, традиционно считающиеся интеллектуальными задачи, общаясь с ЭВМ на ограниченном подмножестве естественного языка[1].
• Основная задача -- это обучить антропоморфного робота NAO Evolution V5 играть в интеллектуальную игру "Шашки“ и сделать этот процесс не отличимым от игры с обычным игроком.
• В первой части рассматриваются модели и алгоритмы принятия решений. Основной задачей программы является принятие решения о совершаемом ходе. Каждый игрок, основываясь на своём опыте и стратегии выполняет ход, который считает нужным. Робот может просчитывать все возможные ходы и выбрать оптимальный из них, или выбирать ходы основываясь на стратегии, на которую запрограммирован.
• Во второй части дипломного проекта рассматривается архитектура программного комплекса. Анализируются и описываются ресурсы, на которых будет построен программный комплекс. Такими ресурсами будут являться, язык программирования и среда разработки.
• В следующем части ведётся разработка структур данных и знаний. Это часть состоит из описания типов данных, используемых в программном обеспечении и из описания знаний необходимых для выполнения работы.
• Указываются и рассматриваются материалы, применяемые при разработке программного комплекса.
• В четвёртой части дипломного проекта разрабатываются алгоритмы всех функций программного комплекса. Каждый алгоритм подробно разбирается и поясняется блок-схемами для визуального сопровождения и лучшего понимания.
• Пятая часть проекта содержит в себе пояснительную информацию о разрабатываемых функциях и код функций, написанный на выбранном языке. Также в коде функций присутствуют комментарии для подробного объяснения написанного кода.
• В следующей части проводится экспертное тестирование разрабатываемого программного комплекса и отладка программных модулей. При выполнении данной задачи, могут выявиться программные или логические ошибки.
• В заключительной части дипломной работы проводится оценка разрабатываемого продукта. В процессе оценки рассматриваются такие факторы как, удобство работы, новизна, надежность, скорость работы и другие.
• В результате работы мы получим программный комплекс, загружаемый в робота Nao. Робот с легкостью сможет определить положение доски во внешней среде и определить координаты шашек игрока. Проанализируя полученную информацию, робот выполнит ход и оповестит об этом пользователя.
• Игра будет приближена к игре с реальным игроком. За исключением выполнения хода роботом. Выполненный ход будет сообщён пользователю по средствам голосовых команд. Для использования разрабатываемого программного комплекса также будет разработана документация со скриншотами и подробным описанием. Процесс настройки системы будет простым и доступным для любого человека.
• 1. Анализ моделей и методов реализации интеллектуальных игр в системе человек-робот
• Для рассмотрения этого вопроса, необходимо изучить некоторые определения и понятия.
• Под интеллектуальной игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу -- в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках [2].
• Робот - это техническое устройство, которое предназначено для выполнения программы, на которую запрограммирован. В основном такое устройство предназначено для выполнения производственных задач, для использования в учебных и исследовательских целях.
• При реализации интеллектуальных игр в модели человек-робот требуется решить две задачи:

1) нахождение алгоритма, по которому совершаются ходы в игре;

2) способ передачи данных об игровом состоянии между роботом и человеком.

1.1 Выбор алгоритма игры

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

Одним из существующих видов алгоритмов является метод построения игрового дерева. Рассмотрение данного алгоритма можно начать с более простой игры “Крестики-Нулики”.

Деревьями решений можно представить практически любую игру. Узлом игры является её состояние в данный момент времени до выполнения следующего хода и после выполнения предыдущего. Отдельная ветвь игрового дерева решений является последовательностью ходов игрока. Главная задача данного алгоритма найти оптимальный и лучший путь от корня до листа.

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

Каждый узел имеет H ответвлений, при условии, что игрок имеет H возможных ходов. Начальное состояние игры представляется пустым полем и в игровом дереве представлено корневым узлом. Ход первого игрока способен выпасть на любой из девяти возможных вариантов. Каждый возможный ход представлен ветвью, выходящей из корневого узла. Второму игроку для выполнения хода нолика остаётся восемь вариантов. Первые два хода представлены игровым деревом на рисунке 1.1

Рисунок 1.1 - Дерево решений

Число возможных состояний в конце игр составит 362800 узлов. Но в действительности число возможных состояний игры будет приблизительно составлять 250000. Это связано с правилами игры. При победе одного из игроков продолжение ветки останавливается и текущее состояние является листом дерева.

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

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

Каждый из игроков имеет определённое значение, которое соответствует одному из четырёх состояний:

1) выигрыш - 4;

2) не ясная ситуация -3;

3) ничья - 2;

4) проигрыш - 1.

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

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

1) победа игрока;

2) игра приходит к ничьей;

3) превышение допустимой глубины рекурсии.

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

Чем больше уровень глубины, тем выше мастерство программы. На рисунке 1.2 показано состояние дерева на момент окончания партии.

Рисунок 1.2 - Игровое дерево решений в конце партии

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

Память, используемая для хранения одного хода, уменьшить длительность выполнения хода игрока в 72 раза.

В игре шашки количество состояний или узлов равняется 10²⁰. В 2007 все допустимые ходы были просчитаны суперкомпьютером. Отсюда следует, что человек никогда не выиграет у компьютера.

В игре шахматы данное число составляет 10⁴⁶. Для обхода данного количества узлов требуется астрономическое время даже для суперкомпьютера.

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

Возможные варианты развития игры можно представить в виде графа, где вершина графа - это состояние игры. Стратегия в глубину подразумевает поиск по направлению “вглубь” по графу. Стратегия в ширину рассматривает поиск по всем вершинам на одном уровне. Каждая из стратегий имеет своё преимущество. Если не ограничивать поиск, то алгоритмы затрачивают одинаковое количество ресурсов и можно выбрать любой. При ограничении по количеству уровней лучшим алгоритмом является поиск в ширину[3].

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

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

Любая стратегия основана на анализе происходящих событий и состояний игры. И каждая из этих стратегий имеет одну цель - победа.

Рассмотрим несколько стратегий игры на примере интеллектуальной игры “Шашки”.

Стратегия “Поддавки”.

Является ловушкой для противника, осуществляемой в начале игры. Задача такого метода в подстановке своих шашек под взятие противником для выполнения в будущем выигрышных комбинаций.

Стратегия “В дамки”.

Совершение ходов, при которых игрок хочет, как можно раньше пройти в дамки.

Стратегия “Блокирование”.

Блокировка противника - это ситуация, при которой игрок имеет возможность сходить, а его противник нет.

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

1.2 Передача данных игрового состояния

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

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

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

Рисунок 1.3 - Игра “Шашки” на ПК, передача данных “Человек-программа”

Робот анализирует положение пешек на доске, и исходя из своих алгоритмов совершает ход. Информация о ходе может передаваться в звуковом формате, а также физическим перемещением пешек.

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

В примере, представленном на рисунке 1.4 продемонстрированы передача данных “Человек-робот” с физическим взаимодействие. Данный робот был представлен компанией ЧТПЗ на конференции «Иннопроме-2015». Для реализации данной игры потребовались специальные металлические шашки. Такая форма и размер шашек удобна для манипулятора.

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



Рисунок 1.4 - Передача данных “Человек-робот”

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

2. Разработка архитектуры программного комплекса

Для разработки интеллектуальной игры в системе “Человек-Робот” необходимо проанализировать и рассмотреть некоторые требования и ограничения. Разработка системы будет осуществляться на основе алгоритма стратегии выбора хода и передачи данных по типу “Человек-Робот”

В качестве интеллектуальной игры выбрана игра “Шашки”. Основная цель игры состоит в том, чтобы взять все шашки противника и не оставить ему вариантов для хода путём блокирования его шашек. Существует большое количество вариантов игры. 64 клеточные шашки можно разделить на русские, обратные русские, английские(чекерс), пул чекерс, бразильские, испанские, португальские, чешские и другие.

Также есть 80-ти клеточные и 100 клеточные шашки. Пример 100 клеточного поля представлен на рисунке 2.1

Рисунок 2.1- Стоклеточные шашки

Для проектирования игры воспользуемся 64 клеточным русскими шашками.

В качестве робота выбран антропоморфный робот NAO Evolution V5 французской компании Aldebaran Technologies. NAO Evolution V5 робот-андроид идеально подходит для исследовательских миссий, а также учебных целей и разработок в области ИИ(искусственный интеллект). Робот построен на производительной аппаратной платформе. Разнообразные типы датчиков и их количество позволят в полной степени получить информацию об окружении робота. Полные характеристики представлены в таблице 2.1

Таблица 2.1 - Технические характеристики NAO V5

Модуль робота	Описание модуля
Аппаратная платформа(Ядро)	Процессор: Intel Atom 1.6 ГГц , ARM9 ОС: ОС NAOqi на ядре Linux Питание: 27,6 Вт/ч Время работы без подзарядки 1.5 часа?
Двигательная система	Моторы и приводы, 25 степеней свободы Установлены устройства поддерживания равновесия гироскоп и акселерометра. На ступнях робота установлены сенсоры давления
Система визуализации	2 камеры качеством 920p. Скорость записи 30 кадров в секунду, что даёт плавную картинку.
Слуховая система	В систему встроено 4 микрофона
Кинестетическая система	На голове, руках и ногах установлены тактильные датчики для отслеживания касаний.
Сонары	Для определения расстояния до объекта установлены сонары.
Система связи робота	Робот поддерживает Ethernet подключение и Wi-Fi. Также имеет инфракрасный порт для взаимодействия со сторонними устройствами

Внешней вид робота представлен на рисунке 2.2

Рисунок 2.2 - Антропоморфный робот Nao

Полную систему робота можно представить в виде структурной схемы, изображённой на рисунке 2.3



Рисунок 2.3 - Структурная схема системы робота

Каждый модуль в Hardware управляется соответствующим модулем из Software. Модуль NAOqi Motion отвечает за движения робота и управление приводами. Он реализует такие функции как, движение в выбранную сторону на указанное количество шагов, сесть, встать, задаваемое движение руками. Можно управлять каждым приводом. Отключение приводов используется для снятия нагрузки с моторов.

NAOqi Vision предназначен для управления верхней и нижней камерой робота. Vision включает в себя классы для работы с фото и видео потоком. Также в библиотеку встроены алгоритмы распознавания и обнаружения объектов.

Вместе с NAOqi Vision следует рассмотреть модуль NAOqi Trackers, имеющий функции распознавания и слежения за лицом человека.

NAOqi Core отвечает за память робота, за ресурсы, за связь через Wi-Fi, Ethernet или ИК-порт и за общие настройки системы.

NAOqi Audio используется для передачи звукового сигнала во внешнюю среду за счёт встроенных динамиков и распознавания слов и фраз.

Все классы, входящие в модули представлены в таблице 2.2

Таблица 2.2 - Классы, входящие в модули NAOqi

Наименование модуля	Классы
NAOqi Core	ALBehaviorManager ALConnectionManager ALMemory ALModule ALPreferences ALResourceManager ALVisionExtractors
NAOqi Motion	ALMotion ALNavigation ALRobotPosture
NAOqi Audio	ALAudioDevice ALAudioPlayer ALAudioRecoder ALAudioSourceLocalisation ALSoundDetection ALSpeechRecognition ALTextToSpeech
NAOqi Vision	ALBacklightingDetection ALDarknessDetection ALFaceDetection ALLandmarkDetection ALMovementDetection ALPhotoCapture ALRedBallDetection ALVideoDevice ALVideoRecorder ALVisionRecognition ALVisualCompass
NAOqi Sensors	ALBattery ALFsr ALInfrared ALLaser
	ALSensors ALSonar ALLeds
NAOqi Trackers	ALFaceTracker ALRedBallTracker
NAOqi DCM	DCM

Рассмотренный робот идеально подходит для реализации системы[4].

Компания Aldebaran Technologies специально для NAO V5 разработала среду программирования Choreographe. Данная среда позволяет осуществлять разработки без использования языков программирования, что значительно увеличивает количество разработчиков. В блочном программировании в основном используются стандартные модули. В данных модулях описаны алгоритмы распознавания образов и объектов, перемещение объектов, команды встать, сесть, распознавание голоса и другое. Данная программа использована в качестве среды разработки программного комплекса[5].

Структурная схема проекта представлена на рисунке 2.5

Рисунок 2.5 - Структурная схема проекта

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

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

Основная цель модуля игры прослеживать выполнение правильности ходов игроками. Все текущие данные игры хранятся в рассматриваемом модуле. Программа выдаст исключение, если ход сделан неверно, если неожиданно с поля пропадёт несколько шашек и сообщит, если игрок не сделал ход для совершения хода по правилу “фука”.

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

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

Задача модуля вывода данных состоит в оповещении в сделанном ходе или нескольких ходов, а также о выполнении ходов по правилу “фука” и текущем статусе игры.

Диаграмма компонентов, изображённая на рисунке 2.6 демонстрирует какие классы входят модули и их основные функции. Диаграмма классов представлена на рисунке 2.7

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

Рисунок 2.6 - Диаграмма компонентов

Рисунок 2.7 - Диаграмма классов

3. Разработка структур данных и знаний

3.1 Язык программирования

Библиотека NAOqi импортирована на такие языки как Java, C++, Python и MathLab. У каждого из данных языков есть плюсы и минусы. Язык программирования C++ является самым быстрым языком, так как программный код компилируется непосредственно в машинный код. Основным минусом данного языка является сложность. От этого качества зависит скорость разработки.

Язык программирования Java самый популярный на рынке труда. Данный язык включает в себя такие библиотеки как Spring, Java EE, JDBC и другие. Являлся официальным языком для разработки на Android. Продукты на данном языке также проигрывают в скорости, так как программный код транслируетя в байт-код и только после этого запускается на JVM.

Python является интерпретируемым языком. В отличии от C++ и Java данный язык является динамически типизированным. Эта особенность позволяет писать быстрый код. Python позволяет писать сложные конструкции в одну строку, что также ускоряет процесс разработки. Минусом является то, что язык также, как и Java запускается на собственной виртуальной машине.

Языком программирования для разработки программного комплекса выбран язык Python. Разработано огромное количество библиотек на для данного языка. Такие как Pillow[11], ImageDraw[12] и random будут использоваться при разработке. Среда разработки по умолчанию использует выбранный язык.

Язык Python это высокопроизводительный интерпретируемый язык программирования. Основная концепция и философия данного языка -- это минимализм. Вот несколько правил философии языка Python[6]:

1) красивое лучше, чем уродливое;

2) явное лучше, чем неявное;

3) простое лучше, чем сложное;

4) сложное лучше, чем запутанное;

5) плоское лучше, чем вложенное;

6) разреженное лучше, чем плотное;

7) читаемость имеет значение;

8) особые случаи не настолько особые, чтобы нарушать правила;

9) при этом практичность важнее безупречности;

10) ошибки никогда не должны замалчиваться;

11) если не замалчиваются явно;

12) встретив двусмысленность, отбрось искушение угадать;

13) должен существовать один -- и, желательно, только один -- очевидный способ сделать это;

14) хотя он поначалу может быть и не очевиден, если вы не голландец;

15) сейчас лучше, чем никогда;

16) хотя никогда зачастую лучше, чем прямо сейчас;

17) если реализацию сложно объяснить -- идея плоха;

18) если реализацию легко объяснить -- идея, возможно, хороша.

Самая актуальная на данный момент версия Python это 3.6.1. Язык является строгим с динамической типизацией. Самой используемой в проекте типом данных является список.

Python умеет работать с исключениями. Он умеет выбрасывать и обрабатывать их при помощи конструкции try…catch. Выбрасывание исключения производится при помощи выражения raise. Данная особенность нужная нам для разработки программного комплекса.

Для удаления переменных из оперативной памяти и из программы используется конструкция del <имя переменной>[7].

Список или list является аналогом массива в таких языках программирования как Java, C++ и др. Отличием от этих типов данных является то, что список способен хранить в себе элементы любых типов.

Для добавления элемента используется метод append. Для получения элемента списка пользуются следующей синтаксической конструкцией list[i], где i это индекс элемента.

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

3.2 Структуры данных

В процессе преобразования для хранения данных о цвете пикселя используется список из трёх элементов.

Так как монитор использует RGB цветовую схему то цвет пикселя можно задать тремя цветами R - красный, G - зелёный, B - голубой. Значение каждого цвета может быть от 0 до 255.

Элементом списка также может быть список. Если каждый элемент списка является списком, список можно считать двумерным массивом. При бинаризации изображения создаётся двумерный массив. Пример представлен ниже.

Данный пример представляет бинаризированное изображение 9 на 9 пикселей, где 1 - это белый цвет, а 0 - это чёрный цвет.

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

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

Координаты шашки на поле представлены структурой данных в виде списка с двумя элементами. Нулевой элемент массива представляет координату X, а первый элемент массива Y.

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

,

где x1, y1 - координаты начального положения шашки;

x2, y2 - координаты ячейки, куда будет перемещена шашка;

STR - тип игрока, кем совершается ход. STR - может принимать два значения “player” или “pc”.

Данный ход передаётся в объект класса Game в функцию move. Данная функция возвращает информацию, необходимую для дальнейшего выполнения игры. Возвращаемый объект является списком, состоящего из двух элементов.

Первый элемент(CH) может принимать три значения:

1) 1 - ход переходит к противнику;

2) 2 - продолжайте ход;

3) 3 - выполнение правило “фука” и переход хода к противнику.

При значении первого элемента, равному единице, значение второго элемента равно пустому словарю. При значении два, значение второго элемента равно словарю с одним элементом по ключу(KEY) “last” и значением(VALUE) последней шашки, которой ходил игрок. При значении элемента равном трём, словарь имеет один элемент по ключу “shashka” со значением, равным объекту типа Shashka, который удаляется с поля.

Передачу данных структур информаций можно изобразить в виде семантической сети. Данная семантическая сеть представлена на рисунке 3.1

Рисунок 3.1 - Семантическая сеть

MPC - объект типа список, состоящий из двумерных списков, содержащих физические координаты ячеек(LPH). MCD, CC - список, объектами которого являются списки с двумя элементами, равными логическим координатам(LLOG) (MCD - текущее состояние поля, CC - последнее состояние поля). M - двумерный список, состоящий из двух списков LLOG. SH - двумерный список, который содержит две строки, несущую в себе логическую информацию о совершаемом ходе.

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

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

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

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

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

Объект типа ИИ проверяет все шашки на возможность взять шашку противника. Если объект находит данную шашку, он проверяет шашку на статус удаления. Если шашку можно удалить, то она откладывается в буфер возможных ходов. Если шашки с отрицательным статусом удаления найдены выполняется ход именно ей. Если не найдено, то ход выполняется из буфера.

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

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

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

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

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

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

3.3 Среда разработки Choreographe

Для разработки программного комплекса используется среда разработки Choreographe. Данное ПО относится к средам визуального программирования. Визуальное программирование позволяет разрабатывать ПО обычным пользователям ПК.

Каждая написанная программа называется behavior(поведение). У каждого поведения есть точка входа и выхода. Вся программа располагается между этими точками.

Весь процесс разработки заключается в соединении так называемых box(боксов). Каждый бокс имеет входы и выходы. Два основных это вход onStart(запуск) и выход onStopped(остановка). Блоки можно соединять как параллельно, так и последовательно. Финальной точкой является точка выхода из поведения и дальнейшее завершение программы.

Исходные коды всех боксов находятся в открытом доступе. Каждый бокс настраиваемый. Например, бокс Say Text имеет настройку выбора языка, на котором необходимо произнести фразу. Бокс Led Eye дат возможность выбора цвета подсветки глаз. Каждый бокс написан на языке Python с использованием библиотеки NAOqi.

Бокс представляет из себя класс, наследованный от класса GeneratedClass. Данный класс может иметь неограниченное количество методов. Четыре из них являются основными:

1) onLoad - выполняется при загрузке программы;

2) onUnload - при выгрузке или завершении программы;

3) onInput_onStop - выполняется при подаче сигнала на вход onStop;

4) onInput_onStart - выполняется при подаче сигнала на вход onStart.

Входные параметры боксов могут быть четырёх типов Bang, Number, String и Dynamic. Тип Bang является особенным типом, разработанным для библиотеки NAOqi. Данный тип является типом передачи потока.

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

Пример программы распознаёт лицо человека и передаёт сигнал на следующий бокс, функция которого заключается в произношении фразы. Если бокс трекер обнаруживает лицо человека он передаёт сигнал потока программы в бокс Say.



Рисунок 3.2 - Пример программы

4. Разработка алгоритмов

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

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

1) модуль выбора хода;

2) модуль игры;

3) модуль распознавания;

4) модуль обработки данных;

5) модуль вывода данных.

Анализ модулей проводится в порядке их использования.

4.1 Алгоритмы модуля распознавания

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

Распознавание доски состоит из нескольких этапов:

1) снимок доски;

2) бинаризации изображения и сохранение нового файла - функция binary_image;

3) поиск верхних ячеек доски - функция search_top_ugly;

4) поиск нижних ячеек доски - функция search_bottom_ugly;

5) нахождение центров верхних и нижних ячеек - функция avg;

6) нахождение всех ячеек доски - функция parsing_mest.

Робот Nao Evolution V5 имеет две камеры. Для управления камерой используется функция модуля ALPhotoCaptureProxy takePicture. Также для данного действия можно использовать стандартный бокс в программе Choreographe.

После выполнения предыдущего этапа полученный файл преобразуется в чёрно-белую копию. За этот процесс отвечает функция binary_image. Каждый пиксель изображения преобразуется в RGB(R - красный, G - зелёный, B - синий). Если сумма всех трёх значений больше числа высчитываемого по формуле

,

где factor - это любое число, от значения которого зависит порог выбора белого или чёрного цвета пикселя, то пиксель считается белым, в противном случае пиксель чёрный[9].

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

Указатель в виде номера строки и номера столбца пикселя на изображении перемещается от левого верхнего пикселя с указателем (0,0) в правый нижний пиксель с указателем (width, height). Основная задача алгоритма функции найти последовательное смену черных и белых областей. Для этого на каждой строке пикселей инициализируется переменная v1 и ей присваивается значение 0. После того как текущее значение пикселя меняется на противоположный цвет переменной v2 присваивается значение v3 - v1 где v3 - текущее значение номера столбца. При дальнейшем поиске значение v2 сравнивается с предыдущим v2. Если данное значение с погрешностью равной или меньшей p1 равно предыдущему значению v2, то счётчик count увеличивается на один, иначе count сбрасывается.

При count равному семи, поиск завершается, и данная строка считается верхней границей ячеек игральной шахматной доски. Блок-схема данной функции представлена на рисунке 4.1

Процедура search_bottom_ugly совершает такую же процедуру только с нижней границей.

Рисунок 4.1 - Блок-схема процедуры search_top_ugly

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

Для поиска центральных пикселей каждой клетки игрального поля используется функция avg класса RECOGNIZE.

Функция имеет следующий алгоритм. Каждая нулевая координата ячейки верхней и нижней границы приравнивается к значению разности нулевой координаты и среднего расстояния между ячейками пополам. Для вычисления координаты Y используется следующий этап.

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

,

где y1 - Y координата предыдущей ячейки;

y2 - Y координата текущей клетки.

Координаты Y нецентральных точек совпадают с координатами центральных точек. А координаты X находятся по следующей формуле:

,

где угол A - угол между вертикалью и прямой проведённой от верхней точки границы к нижней точки границы с соответствующим коэффициентом.

Также тангенс угла A найти по следующей формуле:

где x1 - координаты центрального пикселя;

y2 - координата y нецентрального пикселя;

y1 - координата верхнего центрального пикселя.

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

Для определения позиций чёрных тёмных клеток используется функция get_coords_black_fields. Для получения логических координат клеток, на которых расположены белые шашки необходимо выполнить процедуру get_white_shashki. Результат выполнения модуля представлен на рисунке 4.2

Рисунок 4.2 - Результат выполнения функции распознавания

4.2 Алгоритмы модуля обработки данных

В процессе сканирования доски мы получим массив физических и логических координат белых шашек. Для получения хода, выполненного игроком, необходимо выполнить сравнение массива логических координат шашек, сохранённых в объекте класса Game с массивом полученных после распознавания данных.

Для данной цели используется функция get_hod. На вход функции поступает два массива: before - состояние поля до хода, after - состояние поля после хода.

При выполнении функция проверяет размерность массивов, если они не совпадают выбрасывается исключение. Функция перебирает все элементы массива after и ищет данный элемент в массиве before. При обнаружении найденный элемент удаляется.

Элемент, который останется в массиве before является стартом, а элемент массива after, который отсутствует в before является, финишем хода. Массив из двух элементов возвращается функцией. К данному объекту добавляется третий элемент строка “player”, информирующая, что ход был совершён игроком. Данный массив передаётся к объекту Game.

4.3 Алгоритмы функций модуля игры

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

Алгоритм модуля игры реализуется классом Game. Данный класс имеет несколько процедур и функций, а также массив данных о шашках.

При создании объекта класса Game выполняется метод __init__. Данный метод является аналогом конструкторов в таких языках как Java и C++. В процессе инициализации в массив chess_circle добавляются элементы класса Shashka. Данный класс хранит в себе информацию о шашке. Логические координаты и флаг дамки, а также тип игрока, которому принадлежит шашка. Для назначения координат шашкам используется двойной вложенный. Шашки располагаются на нечётных строках чётных столбцов и чётных строках нечётных столбцов при условии, что один тип пешек располагается на первых трёх строках, а второго типа на последних трёх.

После инициализации игра ожидает получение информации о совершаемом ходе. Весь дальнейший алгоритм выполняется в функции move.

Данная функция выполняет проверку на правильность выполнения хода при помощи функции-члена класса protect_move. Блок-схема данной функции представлена на рисунке 4.3

Реализуемая функция получает шашку по координатам начальной позиции и финальной позиции при помощи функции get_shashka. Входными параметрами являются логические координаты, а выходными данными является либо объект класса Shashka и значение False. Если шашка по начальной позиции найдена, а по конечной нет, то функция выполняется дальше, иначе выбрасывается исключение.

После этого выполняется проверка на диагональный ход при помощи логического выражения, представленного ниже

При выполнении хода модули разности соответствующих координат должны быть равны по правилу равнобедренного треугольника при углах в 45 градусов.

Следующей проверкой является проверка на выполнение хода в границах игрального поля

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

Если шашка не является дамкой, длина хода должна составлять две или одну клетку. При длине хода равному двум при помощи функции get_beetween_shashka получаем объект Shashka или значение False, если шашки не найдено. Функция-член get_beetween_shashka принимает две пары логических координат и возвращает объект Shashka или ложное булевое значение. Сравниваем владельцев пешек. При несовпадении типов ход принимается. Если типы совпадают или шашка не найдена выбрасывается исключение.

При длине хода, равному единице, проверяется направление хода, в зависимости от типа игрока.

Если флаг дамки имеет значение истина, то проверка идёт по другому алгоритму. Длина хода неограниченна. Ограничением является только тот момент, при котором ход выполняется через шашки такого же типа или через несколько пешек другого типа.



Рисунок 4.3 - Блок-схема функции protect_move

Если при выполнении функции не было выброшено ни одного исключений ход считается правильным и информация передаётся дальше.

После выполнения проверки функция move получает шашку по начальной позиции. При длине хода большего чем две клетки получаем шашки расположенные между клетками хода и удаляем их из массива chess_circle.

Также в функции-члене move реализуется логика присвоения флага дамки. Если шашка не является дамкой, и она достигла позиции восьмой или первой строки в зависимости от типа, то ей флаг дамки принимает значение истина.

Функция move возвращает объект со статусом и дополнительной информацией. Информация о возможных статусах и описание дополнительной информации представлены в таблице 4.1

Таблица 4.1 - Статусы выполнения хода

Статус	Описание статуса и дополнительной информации
3	Статус “зафука”, информирует о том, что игрок не выполнил ход за взятие шашки противника. Возвращается объект типа Shashka, которую необходимо удалить.
1	Ход переходит к противнику.
2	Игрок может продолжать ход. Данное событие возникает при удалении шашки игроком, с возможностью удалить следующую шашку из новой позиции. В качестве дополнительной информации возвращается объект класса Shashka, которой был выполнен предыдущий ход.

Также модуль игры реализует вспомогательные функции:

1) size_move - вычисляет размер хода;

2) i_can_del - проверка возможности удаления пешек противника.

3) is_game_end - статус завершения игры.

4.4 Алгоритмы выбора хода

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

Класс II содержит следующие функции:

1) get_shashka - получение шашки по логических координатам;

2) get_sosed - получение шашки соседа по объекту типа Shashka и направлению поиска;

3) parallel_pos - возвращает обратное направление;

4) get_sosed_coords - получение логических координат соседа по шашке и направлению;

5) protect_del_diagonal - проверка на диагональную атаку;

6) protect_del_me - проверяет возможно ли взять шашку, принимаемую в качестве входного значения;

7) smart_attack - умная атака;

8) search_simple_move - поиск простого хода, выполняется после умной атаки;

9) protect_del_shashki - проверка всех пешек на возможность их взятия, возвращает простой ход или ход страховку;

10) move_shashka - поиск хода и выполнение определённой шашкой;

11) move - главная функция, объединяющая все выше перечисленные функции, возвращает ход;

12) change_data - используется для обновления информации о шашках на поле.

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

Словарь POS_AND_COORDS является словарём направлений перемещений шашек по шахматной доске. Описание направлений представлены ниже:

1) lu - left up, в лево вверх;

2) ru - right up, вправо вверх;

3) ld - left down, в лево вниз;

4) rd - right down, вправо вниз.

Основной функцией класса является функция-член move. Если в функцию передан объект типа Shashka, то в первую очередь выполняется атака данной шашкой при помощи move_shashka. Программа проверяет по всем направлениям возможность взять шашку противника. Если шашка не является дамкой получаем соседа по определённому направлению. Если сосед обнаружен и его тип “player”, проверяется наличие шашки в финальной позиции. При обнаружении шашки переходим к следующему направлению. Если шашка не найдена, выполняется проверка на возможность удаления. При положительном статусе проверки ход сохраняется в буфере хода. Если статус отрицательный ход выполняется.

Логика функции smart_attack подобна логике предыдущей, но есть некоторые отличия. Происходит обход всех шашек робота, а не только определённой. Шашки сортируются таким образом, что все дамки идут вначале, а потом идут обычные шашки. Обычные шашки отсортированы по статусу подстраховки. Статус подстраховки переделяется переменной-членом podstrahovka класса II.

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

Функция protect_del_shashki проверяет шашки на статус удаления. Если статус удаления положительный выполняется podstrahovka для защиты от ударов со стороны противника или выполняется функция search_simple_move атакуемой шашкой для ухода от удара.

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

Модуль выбора хода принимает решения о ходе на основе данных алгоритмов. Для более интеллектуальной игры алгоритмы можно усовершенствовать.

Для функции smart_attack можно добавить проверку на цепочку удалений. Это означает, что более приоритетным ходом будет являться ход, при котором будет удалено наибольшее количество пешек противника в продолжении хода. Также одним из новшеств будет введение стратегии “поддавки”. Жертвой своей шашкой для достижения большего результата.

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

4.5 Алгоритм преобразования и вывода данных

Основная задача модуля данных это оповещение игрока о выполненном ходе и возвращаемом статусе игры. Для вывода данных используется стандартный бокс среды разработки Choreographe под названием Say Text. Входным параметром бокса является строка, которая будет произнесена роботом.

После передачи данных о совершаемом ходе игрока в функции move объекта класса Game, объект возвращает статус выполненного хода. Если статус равен единице, объект класса ИИ просто вычисляет ход при помощи функции move, перед этим обновляя информации о шашках на поле при помощи функции change_data. И формирует строку в виде выполняемого хода.

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

Функция принимает список из двух координат и возвращает строку, состоящую из буквенного символа от A до H в латинском алфавите и цифры от 1 до 8.

Если Game возвращает статус два, то робот оповещает пользователя о том, что он может продолжить ход.

Если статус игры равен трём, то робот оповещает пользователя о взятии шашки по правилу “фука” с координатами, преобразованными функцией get_chess_coords. И потом сообщает о своём ходе.

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

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

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



Рисунок 4.4 - Блок-схема функции search_simple_move

5. Разработка и реализация программных модулей

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

Перед написанием кода программы стоит обратить внимание на некоторые особенности языка Python.

В таких языках программирования как Java для обращения к объекту класса используется зарегистрированное слово this. В языке Python для этих целей используется self. В Java по умолчанию в функцию член класса передаётся объект, обращения к которому и осуществляется через переменную this. В Python необходимо явно указывать объект в виде параметра функции.