Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Разработка программного модуля искусственного интеллекта для игры в шахматы
шахматный компьютерный интеллект алгоритм
Введение
Понятие компьютерные шахматы является ровесником науки кибернетики и ее раздела искусственный интеллект. Шахматы представляют собой идеальную модель для исследования сложных задач, особенно тех, где требуется перебор вариантов. Разработку шахматной программы относят к проблеме разработки искусственного интеллекта по следующим причинам:
имеется общая уверенность, что задача имеет отношение к проблеме искусственного интеллекта, так как шахматы считаются самой интеллектуальной игрой
существует объективный критерий сделанной работы - сила шахматной программы
большая дифференцированность этого критерия представляет возможность постепенного усовершенствования программы.
Один из основателей кибернетики и теории информации - Клод Шеннон - еще в 50-х годах первым сформулировал правила выбора хода на шахматной доске. В анализируемой позиции на определенную глубину перебираются все возможные варианты, и итоговым позициям с помощью целевых функций присваивается численная оценка. Затем минимаксной процедурой осуществляется откат к исходной позиции, происходит ее оценка и указывается лучший, по мнению машины, ход[7].
Роль человека заключается в том, чтобы, оценивания позиции, как можно точнее задать целевые функции. Эти функции имеют две составляющие - материальную и позиционную. С первой все ясно - материальный перевес (в фигурах и пешках) является, как правило, весьма серьезным аргументом для оценки позиции как лучшей. Кроме того, чем меньше материала на доске у обеих сторон, тем точнее оценка.
А вот с позиционной составляющей все гораздо сложнее: здесь учитывается много факторов, например, особенности расположения отдельных фигур и пешек, пространство на доске, время для перегруппировки сил и др. Умение правильно оценить роль всех факторов в определенной позиции всегда считалось одним из признаков мастерства шахматистов-людей.
Слабость игры компьютеров заключалась именно в злоупотреблении материалом и невозможности осуществить абсолютный перебор вариантов. В шахматных книгах 70-80-х годов можно встретить немалое количество образцово-показательных примеров игры людей с машинами, когда мастер или гроссмейстер выигрывал партию с помощью красивых жертв фигур и пешек. Секрет уже понятен: для человеческого интеллекта, в отличие от искусственного, было очевидным доминирование позиционных факторов над материальными именно в те моменты, когда осуществлялись жертвы материала[20].
Шли годы, с ростом быстродействия ЭВМ увеличивалась глубина расчета, и одновременно совершенствовались алгоритмы, улучшающие составление функций оценки позиций. И во второй половине 90-х годов компьютеры уже стали успешно соперничать с гроссмейстерами экстра-класса. Эпохальное для шахматных кибернетиков событие произошло в мае 1997 года. Созданный корпорацией IBM компьютер Deep Blue в матче из 6 партий победил самого Гарри Каспарова. Компьютер был оснащен специальным шахматным чипом, причем машина просматривала около 200 млн. позиций в секунду. Корпорация IBM для своего проекта привлекла многих гроссмейстеров, использовались последние достижения шахматной теории для создания как можно более совершенных алгоритмов. И вот, как уже отмечалось, в 90-е годы шахматные программы для настольных ПК стали теснить специализированные компьютеры.
С каждым месяцем сила шахматных программ и мощность компьютеров неумолимо увеличивается, опережая даже самые смелые предположения оптимистов. Еще лет 12-15 назад рассуждения на тему Когда машина сможет обыгрывать гроссмейстера? в основном сводились к вопросу А способна ли она это сделать в принципе?. И если ответ Сможет все же удавалось получить, то время оценивалось в промежутке 15-25 лет.
Действительность же опровергла и эти прогнозы. Все случилось гораздо быстрее! Уже в середине 90-х обнаружилось, что синтез игровая программа + компьютер способен состязаться с гроссмейстером[8].
Целью работы является разработка и реализация программного модуля искусственного интеллекта для игры шахматы, что в себя включает:
. исследование существующих игровых алгоритмов применимых для игры шахматы
. разработка алгоритма поведение компьютерного оппонента
. определение параметров алгоритма поведение компьютерного оппонента
. реализация программного обеспечения, что включает в себя реализацию игрового алгоритма и разработка графического интерфейса
. сравнение разработанного программного обеспечения с существующими аналогами.
1. История развития шахматных программ
В 1951 году Алан Тьюринг написал алгоритм, при помощи которого машина могла бы играть в шахматы[11]. Только в то время в роли машины выступал сам изобретатель. В том же 1951 г . математик Клод Шеннон пишет свою первую статью о программировании шахмат. Он описывал две стратегии поиска лучшего хода, обе основываются на эвристической функции оценки конечных точек:
тип А - перебор всех возможных ходов на фиксированную глубину, с вызовом в конце оценочной функции (т.к. невозможно осуществить перебор до конца)
тип В - выполняет только выборочные расширение опред