Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ля проведения отбора используется турнирный отбор. Играют случайные 2 хромосомы между собой, до четырех побед, ходят первыми по очереди. Победитель дуэли остается, проигравший удаляется из популяции[2].
При скрещивании используется метод одноточечного скрещивания.
Берется случайным образом 2 родителя, выбирается случайно число, по которой хромосома разделится, схема показана на рисунке №14. В результате у каждого потомка будут черты как от первого так и от второго родителя.
Рисунок 14 - Пример углубленного отсечения
Мутации выполняется следующим образом: выбираются с некоторой вероятностью хромосомы, и у них, каждый ген меняется на случайное число в диапазоне [-50; 50], кроме значения статических оценок ферзя и пешки[1].
Для финальных значений полученные веса делятся на 100.
3.7.5 Суммарная оценка
При оценке позиции обращается внимание на 8 составляющих:
.Материальные силы соперников
.Количество полей под боем
.Занятие ключевых полей
.Проходные пешки
.Сдвоенные пешки
.Рокировка
.Продвижение пешки
.Пешечные цепи [*1]
Количество полей под боем рассчитывается на глубине дерева 2, ввиду большых производительных затрат. За каждое поле которое бьет фигура компьютера к оценке позиции прибавляется 1 очко, за поля, которые бьются фигурами игрока, снимается по очку. Полученное значение передается в низ дерева как параметр. Так же на глубине 2 производится рассчет баллов за пешечные цепи, проходные и сдвоенные пешки. За наличие соприкающихся слева или справа пешек сторона получает по 1 баллу. Пешка считается проходной, если на ее вертикали, а так же на соседних с ней, нету пешек соперника которые могут помешать ей пройти до конца. Сдвоенные пешки - 2 пешки одного цвета стоящих на одной вертикали[11]. За наличие сдвоенных пешек со стороны снимается 4 очка, за наличие каждой проходной пешки прибавляется 5 очков. В шахматах есть ключевые поля:
Рисунок 15 - Ключевые поля
За занятие каждого из них даются дополнительные 4 очка.
Т.к. после совершения рокировки король находится в очень устойчивом положении, за совершенную рокировку сторона получает 3 очка.
Чем ближе пешка к последней для нее горизонтали, тем она ближе к превращению. За каждую пройденную вперед клетку к ценности пешки прибавляется 1.
После рассчета количества очков для обоих сторон получается итоговая оценка позиции, путем вычитания из очков компьютерного оппонента очков игрока.
4. Разработка программы
.1 Требования к шахматному алгоритму
Во время разработке модели программного модуля для игры в шахматы, следует учитывать следующие параметры:
шахматные алгоритмы очень требовательны к производительности, и сила игры программы напрямую зависит от производительности программы
модули программного обеспечения должны быть легкими в разработке и тестировании
пользовательский интерфейс должен быть легким, легко настраиваемым и масштабируемым
4.2 Виды шахматных алгоритмов
Большую часть современных программ можно разбить на 3 категории:
Первая категория Fast searchers - идея состоит в том, что, упростив до предела оценочную функцию, и тщательно с оптимизировав всю программу в целом (что обычно достигается путём написания программы на ассемблере), можно довести количество позиций, рассматриваемых программой (nps - nodes per second) до астрономического числа, например, до 150-200k nps на P/200. То есть на каждую позицию программа тратит порядка одной-двух тысяч машинных команд. В это число входит делание хода из предыдущей позиции в эту, оценка позиции, генерация ходов из данной позиции, управляющая логика и т.д. На собственно оценочную функцию остаются вообще крохи - порядка сотни команд. Программы получаются безумно быстрыми и превосходно ведут себя в сложных тактических позициях, а также отлично решают комбинационные задачи, но имеют слабую позиционную игру
Вторая категоря - knowledge-based программы. Тут все силы брошены на написание сложной оценочной функции. Учитывается и взаимодействие фигур друг с другом, и прикрытость короля, и контроль позиций, и чуть ли не фаза луны. В терминах nps программа работает в 10-100 раз медленнее, чем fast searches, но играет в хорошие позиционные шахматы. Точнее, хорошими эти шахматы являются только тогда, когда на доске нет глубокой тактики, или же контроль времени таков, что у программы есть достаточно времени, чтобы эту тактику просчитать.
Третья категория - гибрид между двумя первыми категориями. Они работают в 2-5 раза медленнее быстрых программ и имеют уже достаточно сложную оценочную функцию[25].
4.3 Контроль времени в шахматных алгоритмах
Важнейшим параметром в построении алгоритма искусственного интеллекта шахматного оппонента является контроль времени хода. От контроля времени зависит сила игры шахматной программы. Перед началом "обдумывания" хода компьютером, должно быть вычислено время, доступное компьютеру.
При расчете времени доступного на ход, надо исходить из двух параметров:
алгоритм поиска лучшего хода строиться на переборе всех возможных ходов на некоторую глубину, и, следовательно, напрямую зависит от времени, затраченного на перебор. Чем больше времени используем, тем сильнее компьютер играет
время ожидание ответа компьютерного оппонента не должно быть слишком большим. За основу можно взять международные правил