Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ета отсечения.
Глубина перебораСокращение числа перебираемых позицийСокращение времени перебора62036%
Результаты экспериментов показывают, что этот алгоритм ускоряет перебор.
5.3 Оценка работы хеш-таблиц
В этом сравнении участвовали Альфа-бета с итерационным погружением и сортировкой ходов и альфа-бета отсечения с итерационным погружением, сортировкой ходов и хеш-таблицами.
Таблица 3 - Сравнение показателей алгоритма альфа-бета отсечения с итерационным погружением и сортировкой ходов и альфа-бета отсечения с итерационным погружением, сортировкой ходов и хеш-таблицами.
Глубина перебораСокращение числа перебираемых позицийСокращение времени перебора61566%
Как мы видим в конечном счете использование хеш-таблиц полностью оправдывает себя.
5.4 Оценка работы библиотек дебютов и эвристик убийц и истории
В этом сравнении участвовали Альфа-бета с предыдущими модификациями и альфа-бета с предыдущими модификациями и с использованием библиотек дебютов и эвристик убийц и истории.
Таблица 4 - Сравнение показателей алгоритма альфа-бета отсечения с итерационным погружением, сортировкой ходов и хеш-таблицами и альфа-бета отсечения с итерационным погружением, сортировкой ходов, хеш-таблицами, библиотеками дебютов и эвристиками убийц и истории.
Глубина перебораСокращение числа перебираемых позицийСокращение времени перебора65%4%6%6%
5.5 Оценка работы алгоритма NegaScout
В этом сравнении участвовали Альфа-бета из предыдущей оценки и алгоритм NegaScout с теми же модификациями.
Таблица 5 - Сравнение показателей алгоритма альфа-бета со всеми дополнениями и алгоритма NegaScout с теми же дополнениями.
Глубина перебораСокращение числа перебираемых позицийСокращение времени перебора61710%
Как мы видим алгоритм NegaScout значительно ускоряет процесс перебора.
6.Оценка качества работы программы
Для проведения оценки качества разработанной программы были сыграны 20 партий с популярными аналогами. Результаты игр показаны в таблице 6:
Таблица 6 - результаты турниров на 20 партий с популярными аналогами
Absolut Chess v 1.3.9Deep FritzLingoChessChess Workbook v2.2.0ChessPro V 3.7% побед70%Количество партий2020202020
Заключение
Целью выполнения дипломного проекта была разработка и реализация программного алгоритма логической игры шахматы.
В ходе выполнения дипломного проекта необходимо было исследовать существующие методы и алгоритмы для компьютерной реализации игры шахматы, определить их основные преимущества и недостатки для того, чтобы, основываясь на полученных знаниях, создать алгоритм, обеспечивающий наилучшую работу данной системы.
В ходе выполнения задания были изучены и реализованы на языке программирования С# следующие алгоритмы и дополнения:
Альфа-Бета отсечение
Nega-Scout
Итерационное погружение
Сортировка ходов
Хеш-таблицы
Генетический алгоритм
Затем были проведены сравнительные испытания реализованных алгоритмов и дополнений.
По итогам испытаний было выяснено что без модификаций алгоритм Альфа-Бета отсечения ускоряет перебор ходов на 50-60%. Дополнения в виде итерационного погружения и сортировки ходов увеличивают производительность еще на 20-22%. При добавлении хеш-таблиц процесс ускоряется еще на 15%. После перехода на алгоритм Nega-Scout итоговые показатели возросли еще на 20%. Так же генетический алгоритм позволил определить наиболее оптимальные весовые коэффициенты для фигур. Таким образом изученные дополнения в значительной степени улучшают результат работы программы.
В результате в ходе выполнения дипломного проекта была разработана программа, позволяющая человеку играть с компьютерным оппонентом.
Проведенная оценка качества показала состоятельность программы на фоне популярных аналогов.
Список литературы
.Исаев С.Е., Введение в генетические алгоритмы программирования, Наука, 2002
.Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. - 2-е изд. - М: Физматлит, 2006
.Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. - М: Физматлит, 2006
.Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. - М: Физматлит, 2003
.Ботвинник М. М. О кибернетической цели игры. М.: Советское Радио, 1975
.Ботвинник М.М., Алгоритм игры в шахматы, "Наука", Москва, 1968
.Лысенко А.А., Гик В.Е., Оценка позиции. Компьютерные шахматы, 2004
.Джонс М.Т. Программирование искусственного интеллекта в приложениях /М. Тим Джонс; Пер. с англ. - М.: ДМК Пресс 2004.
9.Imran Ghory, Reinforcement learning in board games. 2004.
.J.B.Pollack, A.D. Blair, Co-Evolution in the successful learning of backgammon strategy.
.D.Stoutamire, Machine learning, game play, and Go.
.A.Shapiro, G.Fuchs, R.Levinson, Learning a game strategy using pattern-weights and self-play.
.J.Baxter, A.Tridgell, L.Weaver, KnightCap: a chess program that learns by combining TD with game-tree search.
.A.Junghanns, J.Shaeffer, Search versus knowledge in game-playing programs revisted.
.J.Pollack & A.Blair Co-Evolution in the successful learning of backgammon strategy.
.M. Buro Efficient approximation of backgammon race equities.
17.Мальцев А.И., Алгоритмы и рекурсивные функции, Наука, 2003
.Назин А.В., Позняк А.С. Адаптивный выбор вариантов: Рекуррентные алгоритмы, 1986
.Юзюк В.В., Виртуальный алгоритм, "Абетка", 2000
.Карпов А.Е. Мацукевич А.А., Оценка позиции и план, 1999
.Ананд В., Энциклопедия шахматных дебютов, 1993
.Ни