Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?грока, факторы, заложенные в оценочную функцию, определяют цель перебора[14].
Сопоставление числа с позицией дает возможность различать машине плохие и хорошие комбинации. Способность отличать хорошие комбинации от плохих, определяет силу виртуального игрока. В играх двух лиц оценка производится со стороны одного из игроков. Если оценочная функция возвращает хорошую оценку для одного игрока, она должна возвращать плохую для его противника. Это правило является критерием применимости любой функции оценки в алгоритмах, реализующих искусственный интеллект.
Основное требование к оценочной функции - её симметричность по отношению к игрокам, т.е. должно выполняться условие - то, что хорошо для одного игрока, плохо для другого. Хорошая оценочная функция должна учитывать базовые принципы стратегии игры и отвечать следующим характеристикам:
материальная - вычисляется непосредственно как разность количества фигур игроков, возможно добавление весовых коэффициентов для каждой конкретной фигуры
позиционная - показывает качество расположения фигур игрока
развитость позиции - показывает количество возможных ходов игрока. Чем лучше развита позиция, тем больше возможных стратегий имеет игрок. По этой причине необходимо контролировать и уменьшать её состояние у противника
отслеживание конца игры - в случаи выигрыша (взятие короля соперника), должна давать максимальную оценку, обычно + бесконечность, в случаи проигрыша (потери короля), должна возвращать минимальную оценку, обычно - бесконечность
Для игры шахматы, надо учитывать изменение оценки позиции, в зависимости от стадии партии.
Классическая оценочная функция представляет собой функцию от некоторых вышеперечисленных характеристик игровой позиции, то есть оценочная функция является суммарным результатом оценки позиции с различных точек зрения.
Оценочная функция для всех игр различна, так как она отражает специфику игры. Характеристики оценочной функции выбираются экспериментально.
Существенное значение имеет важность выбранной характеристики. Важность определяется путем домножения выбранной характеристики на соответствующий, коэффициент. Этот коэффициент должен иметь статистическое обоснование.
Следовательно, оценочную функцию можно представить в следующем виде:
(p) - оценочная функция по позиции р,
- коэффициент важности для i-ой характеристики,
- i-ая характеристика позиции p[22].
2.5 Постановка задачи
В ходе выполнения дипломной работы необходимо исследовать существующие методы и алгоритмы для компьютерной реализации игры шахматы, определить их основные преимущества и недостатки для того, чтобы, основываясь на полученных знаниях, выбрать алгоритм, обеспечивающий наилучшую работу данной системы.
По итогам дипломной работы необходимо:
реализовать исследуемые алгоритмы на языке программирования С#
реализовать их различные модификации, используя дополнительные модули
провести численные эксперименты, позволяющие оценить качество разработанных моделей, сравнить реализованные модификации, iелью выбора наилучшей
разработать удобный и интуитивно понятный интерфейс
3.Исследуемые алгоритмы и дополнения
.1 Альфа-бета отсечение
Альфа-бета отсечение (англ. Alpha-beta pruning) - это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Основная идея состоит в следующем: если на один из ваших ходов оппонент имеет неблагоприятный для вас ответ, то бессмысленно анализировать другие его возможные ответы на этот ваш ход, потому что даже если среди них и найдутся более благоприятные для вас, противник их не выберет. Альфа-бета отсечение является оптимизацией, так как результаты работы оптимизируемого алгоритма не изменяются.
Рисунок 6 - Алгоритм альфа-бета отсечения
Преимущество альфа-бета отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) - при сортировке чем больше в начале рассмотрено хороших вариантов, тем больше плохих ветвей может быть отсечено без исчерпывающего анализа. минимаксный поиск осуществляется в глубину, поэтому в любой момент времени достаточно рассматривать узлы вдоль единственного пути в дереве.
Ключевая идея альфа - бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение.
На вход этого алгоритма подаются параметры alpha и beta, их называют окном перебора. Эти параметры отвечают за границы отсечения на первом уровне, при углублении в дерево игры, эти параметры изменяются. Алгоритм alpha-beta с параметрами alpha = + бесконечность и beta = - бесконечность ( перебор с полным окном ) дает результат точно такой же, как и алгоритм negamax, т.е полный перебор[18]. На рисунке 7 представлена блок-схема алгоритма alpha-beta по подсчету оценки позиции в глубину.
Рисунок 7 - Блок-схема alpha-beta по поиску оценки в глубину
3.1.1 Пример стандартного отсечения