Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
на статистической базе, работают медленно, но дают очень точные оценки, некоторые даже без применения перебора, проявляют задатки интеллекта.
Гораздо быстрее работают простые функции, учитывающие простейшие принципы игры, они не дают точной оценки, но позволяют проводить глубокий поиск. Таким образом, точная, но медленная оценка, может уступить глупой, но быстрой.
Качество оценки определяется объемом знаний об игре, на основе которых позиции сопоставляется число. Добротность оценки прямо пропорциональна скорости работы и объему знаний. Как показывает 40-летняя практика создания программ с искусственным интеллектом, объем знаний оценочной функции обратно пропорционален её скорости[7].
Графически эта зависимость изображена на рисунке в виде семейства гипербол.
Рисунок 12 - Пример углубленного отсечения
При разработке оценочной функции для шахмат, следует учитывать, что в шахматах оценки всех параметров зависят от стадии игры.
Шахматны принято разделять на этапа: дебют - открытие партии, миттельшпиль - середина игры, эндшпиль - заключительная стадия. Для алгоритма решено разделить партии на 3 этапа по количеству фигур, оставшихся на доске у компьютерного игрока. Изначально на доске по 16 фигур у игроков. В таблице представлена зависимость этапа игры от количества оставшихся фигур:
Таблица 1 - Этапы игры
Этап игрыНазваниеКоличество фигурОткрытие партииДебют[12,16]Середина игрыМиттельшпиль[6,11]Заключительная стадияЭндшпиль[0,5]
3.7.1 Материальная оценка
Материальный перевес одного из игроков считается важнейшим параметром в шахматной теории, следовательно материальная оценка вносит наибольшее влияние на общую оценку позиции. Материальная оценка считается как сумма весовых коэффициентов всех фигур на доске. Король не включается в материальную оценку, так как в случае потери короля, игрок автоматически проигрывает. Оценка весов фигур, является основной задачей при построении оценочной функции. Для определения весов фигур, было решено воспользоваться самообучаемым алгоритмом, основанном на генетическом алгоритме. Веса фигур не зависят от этапа игры. Генетический алгоритм - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию, впервые предложены Холландом (1975)[4].
3.7.2 Описание работы генетического алгоритма
Исходная задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора (хромосома). Случайным образом создаётся некоторое количество начальных векторов (начальная популяция). Они оцениваются с использованием функции приспособленности, в результате чего каждому вектору присваивается определённое значение (приспособленность), которое определяет вероятность выживания организма, представленного данным вектором.
После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к скрещиванию. К этим векторам применяются генетические операторы (обычно скрещивание и мутация), создавая таким образом следующее поколение. Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. [1]
Так моделируется эволюционный процесс, продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
нахождение оптимального решения;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию [2].
Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.
Таким образом, можно работу генетического алгоритма можно представить на следующей схеме:
Рисунок 13 - Пример углубленного отсечения
.7.3 Этапы работы генетического алгоритма
Создание начальной популяции - случайным образом создается начальная популяция; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции[4].
Отбор (селекция) - из всей популяции выбирается определенная доля, которая останется в живых на этом этапе эволюции. Скрещивание (размножение) - для того, чтобы произвести потомка, нужны несколько родителей; обычно, конечно, нужны ровно два. Размножение в разных алгоритмах определяется по-разному - оно, конечно, зависит от представления данных. Главное требование к размножению - чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, смешав их каким-либо достаточно разумным способом[3].
Мутации - стохастическое изменение части особей (хромосом).
3.7.4 Определение весов фигур с помощью генетического алгоритма
В состав хромосомы генетического алгоритма входят веса шахматных фигур, за исключением короля.
Для задания начальной популяции значения хромосом задаются случайным образом в интервале [100; 1000], кроме весов пешки и ферзя, значения их весов фиксируются, пешка - 100, ферзь - 1000.
Д