Способы ограничения дерева допустимых ходов. Недостатки игровых программ и приемы их усовершенствования.
В интеллектуальных играх соревнование между соперниками заключается в том, что они поочередно принимают решения не зная, какое следующие решение примет соперник, т.е. можно построить дерево допустимых ходов и возможных позиций. Необходимость построения дерева связанна с тем, что не существует способов точной оценки исходной позиции.
Рассмотрим принцип построения алгоритмизации для игр с 2 игроками, в которых используется клеточная доска с расположенными на ней фишками. При поиске хода для одного из игроков, во первых, будут последовательно рассмотрены клетки занятых его фишками.
Принцип поиска хода: 1. Проверить занятость всех клеток (i,j). 2. Если поле (i,j) занято своей фигурой, то Р=фигура (i,j) (своя фигура на поле i,j). 3. Эсли направление принадлежит множеству допустимых направлений фишки Р, то x=i y=j . 4. Повторять для всех шагов от [1, max(P)] x=x+dx, y=y+dy. 5. Если (x,y) находятся в пределах игрового поля, то зарегистрировать ход (i,j)?(x,y).
Наиболее простой способ организации дерева глубину анализа 1. В этом случае необходимо: 1Найти все допустимые ходы 2Оценить их 3Сделать лучшие из оцененных ходов.
Процесс игры можно представить в виде: если существует выигрывающий ход, то сделать его и конец; иначе рассматриваем другие допустимые ходы. Пусть С- следующий ход, если существует ответный ход противника, то исключить ход С, иначе учесть число возможных ответов противника после хода С (повторный вызов процедуры поиска хода). Конец если сделать ход на который противник имеет минимальное число ответных ходов.
Приемы усовершенствования игр.
Т.к. в данных программах многое зависит от оценочной функции необходимо сделать ее как можно более точную.
Эвристическое отсечение ветвей. Цель – достижение большей предельной глубины поиска, путем отбрасывания менее перспективных продолжений. Этот прием в дополнении с ?-? отсечением позволяет уменьшить дерево допустимых ходов. Но возникает риск отсечь лишнее и при этом неправильно вычислить оценку позиции.
Последовательное углубление. Программа многократно выполняет ?-? алгоритм до некоторой небольшой глубины, затем увеличивает предел по глубине. Это заканчивает, когда истекает время. Процесс завершается и выполняется наилучший ход на максимальной глубине. Преимущество – облегчается контроль времени, когда оно истекает всегда есть лучший ход.
Недостатки игровых программ.
Полное отсутствие стратегии. Каждая новая позиция рассматривается в отрыве от всех остальных позиций, т.е. программа не ведет игру, а анализирует последовательность позиций независимых друг от друга.
Эффект горизонта. В связи с тем, что необходимо ограничить максим. значение глубины дерева, программа не в состоянии видеть и оценить ходы, которые находятся на глубине превосходящую максимальную.
Программирование игр с полной информацией.
06 Мар, 2009