Разработка программного модуля искусственного интеллекта для игры в шахматы

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

Глубина перебора	Сокращение числа перебираемых позиций	Сокращение времени перебора
6	20%	21%
7	23%	25%
8	26%	25%

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

5.3 Оценка работы хеш-таблиц

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

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

Глубина перебора	Сокращение числа перебираемых позиций	Сокращение времени перебора
6	15%	14%
7	16%	16%
8	16%	15%



Как мы видим в конечном счете использование хеш-таблиц полностью оправдывает себя.

5.4 Оценка работы библиотек дебютов и эвристик убийц и истории

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

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

Глубина перебора	Сокращение числа перебираемых позиций	Сокращение времени перебора
6	5%	4%
7	6%	6%
8	6%	6%

5.5 Оценка работы алгоритма NegaScout

В этом сравнении участвовали Альфа-бета из предыдущей оценки и алгоритм NegaScout с теми же модификациями.

Таблица 5 - Сравнение показателей алгоритма альфа-бета со всеми дополнениями и алгоритма NegaScout с теми же дополнениями.

Глубина перебора	Сокращение числа перебираемых позиций	Сокращение времени перебора
6	17%	19%
7	21%	22%
8	20%	23%



Как мы видим алгоритм NegaScout значительно ускоряет процесс перебора.



6.Оценка качества работы программы

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

Таблица 6 - результаты турниров на 20 партий с популярными аналогами

	Absolut Chess v 1.3.9	Deep Fritz	LingoChess	Chess Workbook v2.2.0	ChessPro V 3.7
% побед	70%	55%	65%	60%	65%
Количество партий	20	20	20	20	20



Заключение

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

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

В ходе выполнения задания были изучены и реализованы на языке программирования С# следующие алгоритмы и дополнения:

· Альфа-Бета отсечение

· Nega-Scout

· Итерационное погружение

· Сортировка ходов

· Хеш-таблицы

· Генетический алгоритм

Затем были проведены сравнительные испытания реализованных алгоритмов и дополнений.

По итогам испытаний было выяснено что без модификаций алгоритм Альфа-Бета отсечения ускоряет перебор ходов на 50-60%. Дополнения в виде итерационного погружения и сортировки ходов увеличивают производительность еще на 20-22%. При добавлении хеш-таблиц процесс ускоряется еще на 15%. После перехода на алгоритм Nega-Scout итоговые показатели возросли еще на 20%. Так же генетический алгоритм позволил определить наиболее оптимальные весовые коэффициенты для фигур. Таким образом изученные дополнения в значительной степени улучшают результат работы программы.

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

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



Список литературы

1.Исаев С.Е., Введение в генетические алгоритмы программирования, Наука, 2002

2.Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. -- 2-е изд. -- М: Физматлит, 2006

3.Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. -- М: Физматлит, 2006

4.Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. -- М: Физматлит, 2003

5.Ботвинник М. М. О кибернетической цели игры. М.: Советское Радио, 1975

6.Ботвинник М.М., Алгоритм игры в шахматы, "Наука", Москва, 1968

7.Лысенко А.А., Гик В.Е., Оценка позиции. Компьютерные шахматы, 2004

8.Джонс М.Т. Программирование искусственного интеллекта в приложениях /М. Тим Джонс; Пер. с англ. - М.: ДМК Пресс 2004.

9.Imran Ghory, Reinforcement learning in board games. 2004.

10.J.B.Pollack, A.D. Blair, Co-Evolution in the successful learning of backgammon strategy.

11.D.Stoutamire, Machine learning, game play, and Go.

12.A.Shapiro, G.Fuchs, R.Levinson, Learning a game strategy using pattern-weights and self-play.

13.J.Baxter, A.Tridgell, L.Weaver, KnightCap: a chess program that learns by combining TD with game-tree search.

14.A.Junghanns, J.Shaeffer, Search versus knowledge in game-playing programs revisted.

15.J.Pollack & A.Blair «Co-Evolution in the successful learning of backgammon strategy.

16.M. Buro «Efficient approximation of backgammon race equities».

17.Мальцев А.И., Алгоритмы и рекурсивные функции, Наука, 2003

18.Назин А.В., Позняк А.С. Адаптивный выбор вариантов: Рекуррентные алгоритмы, 1986

19.Юзюк В.В., Виртуальный алгоритм, "Абетка", 2000

20.Карпов А.Е. Мацукевич А.А., Оценка позиции и план, 1999

21.Ананд В., Энциклопедия шахматных дебютов, 1993

22.Николаев Л.В., Оценка и расчет, 2009

23.Ламот А., Программирование игр для Windows, 2004

24.Норвиг П., Искусственный интеллект. Современный подход, 2007

25.Нэш Т., C# Ускоренный курс для профессионалов, 2008

26.Шилдт Г., Полный справочник по C#. 2004

27.Бишоп Д., C# в кратком изложении, 2005

28.Adam N., WPF 4 Unleashed, 2008

29.Laurence M., Foundations of WPF: An Introduction to Windows Presentation Foundation, 2008

30.Matthew D., Pro WPF in C# 2010: Windows Presentation Foundation in .NET 4, 2010



Приложение

Правила игры в шахматы

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

Рисунок 24 - Начальное положение фигур

По горизонтали доска помечена латинскими буквами от a до h, по вертикали цифрами от 1 до 8. Эти цифры и буквы служат для записи шахматной партии. Перед началом партии "черные" и "белые" имеют одинаковое количество фигур. Эти фигуры расположены симметрично, как показано на рисунке. В комплект фигур (как белых, так и черных) входят следующие:

Рисунок 25 - Начальный комплект фигур



Король. Самая главная фигура шахматной партии, но в тоже время самая уязвимая. Если королю поставлен мат (то есть у короля нет возможности пойти, и ему шах), то шахматная партия заканчивается.

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

Рисунок 26 - Возможные действия короля



Рокировку нельзя делать:

· если король уже делал ход

· если ладья, с которой король хочет сделать рокировку уже делала ход

· если заняты соседние поля (для короткой рокировки g и f, для длинной b,c,d )

· если после рокировки король окажется под шахом

· если королю объявлен шах (и он уходит из-под него рокировкой)

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

В записи шахматной партии короткая рокировка обозначается "0-0", длинная "0-0-0".

Шах - ситуация, когда король атакован вражеской фигурой. В такой ситуации возможно:

· защититься от шаха

· забрать шахующую фигуру другой своей фигурой

· уйти от шаха на другое поле не атакованное вражеской фигурой

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

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

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

Ладья. Условная цена 5 пешек. Ходит по горизонталям и вертикалям, на любое возможное место, если на пути ладьи не стоят другие фигуры.

Слон. Условная цена слона 3 пешки. Ходит по диагонали, на любое возможное место, если на его пути не стоят другие фигуры. Слоны бывают чернопольные (те,которые ходят только по черным полям) и белопольные (те,которые ходят только по белым полям).

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

Пешка. Ходит по вертикали, но бьет по горизонтали, становясь на место побитой фигуры. Если пешка находится в начальной позиции (например на поле е2), то она может сделать ход через клетку (на поле е4), а может пойти только на одну клетку вперед (е3). Если пешка находится не в начальной позиции, то она ходит только на одну клетку вперед.

Рис.



Рисунок 27 - Ходы фигур

Битое поле - это такая позиция когда, к примеру, белая пешка дошла до е5, а черная находится в начальной позиции. Черная пешка делает ход d7-d5, и здесь белая пешка может побить черную, став на поле d6.

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

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

Выигрыш фиксируется в следующих случаях:

· На доске поставлен мат. Игрок, поставивший мат королю противника , выигрывает.

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

· Один из игроков просрочил время. Его противник объявляется победителем, если при этом у него формально достаточно материала, чтобы поставить мат (подробнее см. в разделе «Контроль времени»).

· Техническая победа -- присуждается в официальном турнире игроку, если его противник не явился на партию в течение определённого правилами турнира времени, либо прервал партию (начал партию, но отказался её продолжать), либо в случае грубого нарушения правил турнира или неподчинения судье.

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

Ничья фиксируется в следующих случаях:

· Пат.

· Ни у одной из сторон нет минимально необходимого для мата количества

фигур (например, на доске остались только короли и одна лёгкая фигура).

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

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

· Данным пунктом, правда, никто ни разу не воспользовался, и впоследствии его отменили, было сделано исключение лишь для трёх типов окончаний -- ладья и слон против ладьи, два коня против пешки и ладья с пешкой против слона с пешкой. В 1970--1980-х годах компьютерный анализ показал, что для многих других типов эндшпиля 50 ходов также не хватает, и кодекс был пополнен. Однако впоследствии все исключения отменили, и сейчас правило 50ходов действует в любых позициях[6].

· Игроки согласились на ничью, то есть один из игроков при своём ходе предложил ничью, другой её принял. Для предложения ничьей достаточно сказать «ничья». Если противник делает ход, не ответив на предложение ничьей, оно считается отвергнутым. С недавних пор на некоторых турнирах применяются так называемые «Софийские правила», ограничивающие возможность соглашения игроков на ничью.

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

· Игрок просрочил время в последнем периоде партии, но его соперник пытался или не мог выиграть и играл «на время». Если у игрока осталось менее 2 минут времени до конца партии, а соперник явно тянет время, игрок может остановить часы и обратиться к судье с требованием объявления ничьей.

· Судья вправе, по собственному усмотрению, либо объявить ничью немедленно, либо отложить решение (в этом случае он должен лично наблюдать за игрой до конца партии и вынести решение до или после падения флажка), либо отклонить требование (в этом случае сопернику добавляется 2 минуты времени) (Правила ФИДЕ, статья 10).

В зависимости от итога игрок получает следующее количество очков:

Выигрыш -- 1 очко;

Ничья -- ? очка;

Проигрыш -- 0 очков.

Размещено на Allbest.ru