Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
а шахмат, в которых есть несколько видов партий: блиц - 15 минут на партия, быстрые - 60 минут на партию, классические - больше 60 минут на партию.
Исходя из требуемых параметров, решено время доступное для ходы перед началом каждого хода компьютера вычислять по следующей формуле:где: time - время на ход; full_game_time - общее время партии; avg_moves - среднее количество ходов игрока в партии; collect_time - дополнительно накопленное время; ? - небольшое сокращение времени, требуемое на дополнительные расчеты. Параметры общего времени партии и среднее количество ходов игрока в партии - два основных внешних параметры, изменяя которые можно менять силу игры[27]. По статистике шахматного портала TheChess.ru, среднее количество ходов игроков за партию равно 30, по этому решено взять среднее количество ходов игрока в партии равному 30. Таким образом, из вне задается общее время партии. При разработке алгоритма поведения компьютерного оппонента (искусственного интеллекта) были использованы следующие алгоритмы:
алгоритм итеративного поиска, с контролем времени
алгоритм alpha-beta отсечения и Nega-Scout
библиотеки дебютов
хеш-таблицы
для сортировке ходов использовались эвристики убийцы и истории.
.4 Разработанная программа
В программе на языке программирования С# были реализованы все вышеперечисленные алгоритмы и дополнения.
Скриншоты программы приведены ниже:
Рисунок 16- Выбор цвета
Рисунок 17 - Скриншот программы
Рисунок 18 - Скриншот программы
При наведении мышкой на фигуру своего цвета, она подсвечивается белым цветом. При выборе фигуры для хода цвет ее поля становится оранжевым и все клетки, на которые может сходить фигура, выделяются белым. При наведении мышкой на такую клетку ее цвет тоже становится оранжевым.
Во время игры совершенные ходы выводятся в табличке слева, так же игрок может сохранить историю в отдельный файл.
4.5 Базовый цикл поиска лучшего хода
Главной задачей базового цикла поиска лучшего хода является нахождение и выполнение наилучшего хода компьютерного оппонента. Цикл использует библиотеки дебюта и итеративный поиск с контролем времени. На рисунке 12 представлен процесс поиска лучшего хода:
Рисунок 19 - Базовый цикл поиска лучшего хода
4.6 Поиск лучшего хода первого уровня
Главной задачей работы алгоритма поиска лучшего хода первого уровня (ответа противника) является нахождение наилучшего хода оппонента на первом уровне. Алгоритм построен на алгоритма NegaScout, использующий оценивание в глубину, для определения оценки текущего хода. На рисунке 13 представлен процесс работы алгоритма:
Рисунок 20 - Поиск лучшего хода первого уровня
4.7 Нахождение глубинной оценки хода
Главной задачей нахождения глубинной оценки - нахождение оценки текущего хода, используя алгоритм NegaScout, эвристику нулевого хода, данные из хеш таблицы и статическую оценку позиции. На рисунке 14 представлен процесс подсчета оценки хода в глубину:
Рисунок 21 - Нахождение глубинной оценки хода
4.8 Прочие модели и диаграммы
Математическая модель программы выглядит следующим образом:
Рисунок 22 - Математическая модель
От абстрактного класса Figure сосздаются 7 классов наследников, описывающих действия и свойства фигур. Так же есть класс Еmpty, обозначающий что клетка пуста. Доска представляет собой массив из 64 элементов Figure, каждый из которых может становиться любым из классов-наследников. Ход в компьютере представляется в виде 4 цифр - координат (от 1 до 8) точки начала хода и координат точки конца хода. Ниже приведена диаграмма состояний для программы:
Рисунок 23 - Диаграмма состояний
5. Экспериментальная оценка качества реализованных алгоритмов
Реализованные алгоритмы были подвергнуты сравнительному анализу iелью выявления оптимальной по быстродействию и качеству совершения хода конфигурации. В ходе эксперимента проводился ряд турниров между каждой парой различных реализаций.
.1 Оценка работы Альфа-Бета отсечения
С помощью данного эксперимента необходимо было выяснить, удалось ли достичь снижения фактора ветвления, и как следствие улучшения скорости работы алгоритма без потери качества принятия решения о совершаемом ходе.
Для оценки качества итогового алгоритма, экспериментально сравнивался данный алгоритм поиска с поиском по принципу минимакса.
В таблицах приведены коэффициенты, демонстрирующие отношения числа перебираемых позиций для алгоритмов, а так же отношение времен, отводимых на совершение данного просмотра.
Таблица 1 - Сравнение показателей алгоритма альфа-бета отсечения с алгоритмом минимакса.
Глубина перебораСокращение числа перебираемых позицийСокращение времени перебора64531%
Результаты экспериментов показывают, что альфа-бета отсечение намного лучше простого минимакс поиска.
5.2 Оценка работы итерационного погружения и сортировки ходов
Для оценки качества алгоритма, экспериментально сравнивался данный алгоритм поиска с Альфа-Бета отсечением и просто Альфа-Бета отсечение.
Таблица 2 - Сравнение показателей алгоритма альфа-бета отсечения с итерационным погружением и сортировкой ходов с простым алгоритмом альфа-б