Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
В»ярный на сегодня алгоритм грубого усилия. Он чрезвычайно прост и дает некоторое (до 50%) ускорение, не внося никакой дополнительной погрешности в вычисление. Он очень хорошо сочетается с современными атрибутами шахматных программ - хеш-таблицами.
У этого алгоритма есть преимущество в том, что он никогда не будет исследовать узлы которые могут быть отсечены альфа-бетой, однако некоторые ветки могут быть рассмотрены несколько раз[14].
Алгоритм NegaScout проверяет первый узел с полным окном (Alpha,Beta), считая этот вариант наилучшим. Следующие узлы он пытается отсечь перебором с нулевым окном, т.е. окном (Alpha , Alpha+1). Если результат счета улучшает альфа, то это означает что 1 узел не был лучшим, а этот узел нужно проверить с полным окном, однако вместо Alpha мы может взять полученное значение (Value,Beta). Код этого метода приведен ниже:
public int NegaScout(Cell[,] CopyBoard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)
{Value = 0, MaxValue = -1000, leight = 0;[,] Board = new Cell[8, 8];[,] Moves = new Point[50, 10];[] Move = new Point[10];(Board, CopyBoard);(Depth == 2)
{(Moves, ref leight, Board, true, true);= leight;= 0;(Moves, ref leight, Board, false, true);+= leight;= 0;
}((Depth == FinalDepth) || GameIsOver(Board, IsMy))
{(IsMy)Eval(Board, PossibleMoves);-1 * Eval(Board, PossibleMoves);
}(Moves, ref leight, Board, HaveRequiredMove(Board, IsMy), IsMy);a = Alpha, b = Beta;(int i = 0; i < leight; i++)
{(Move, Moves, i);(Board, Move);= -1 * NegaScout(Board, Depth + 1, FinalDepth, -1*b, -1 * a, PossibleMoves, !IsMy);(Value>a && Value a)= Value;(a == Beta)a;= a + 1;(Board, CopyBoard);
}a;
}
Как видно из описания выше для Нега-скаута перебор ходов является важной функцией. Если расположить все ходы от худшего к лучшему то перебор может занять даже больше времени чем минимакс.
.5 Хеш-таблицы
.5.1 Теория
В шахматах во время перебора получается не дерево игры, а граф - очень часто после перестановки ходов мы получаем одну и ту же позицию. Методика использования хеш таблиц заключается в хранении оценки уже рассмотренных позиций. Для каждой позиции надо хранить её оценку (точнее, оценку поддерева под этой позицией), глубину перебора, наилучший ход. Теперь, начав разбирать позицию, надо взглянуть - а не встречали ли мы уже её? Если не встречали, то поступаем как раньше. Если встречали, то смотрим, на какую глубину мы её раньше разбирали. Если на такую же, как нам надо сейчас, или более глубокую, то можно воспользоваться старой оценкой и сэкономить время. Если же на меньшую, то мы всё равно можем воспользоваться частью информации, а именно наилучшим ходом[20].
Лучший ход для глубины N может оказаться лучшим и для глубины N+1. То есть, кроме своего изначального предназначения, хэш таблица оказывается полезна и для упорядочения ходов. Тут ещё неожиданно помогает итеративное углубление - когда мы начинаем следующую итерацию, хэш таблица оказывается заполнена информацией от предыдущей, и до какого-то момента (до глубины 1) все позиции просто есть в ней, с наилучшим ходом на глубину N-1.
Программа, использующая итеративное углубление и хэш-таблицы, часто выполняет все итерации от 1 до N в несколько раз быстрее, чем если бы она сразу начала итерацию N, т.к. с вероятностью 75% она всегда первым выбирает наилучший ход, а с вероятностью ~90% наилучший ход оказывается в числе первых трёх рассмотренных.
3.5.2 Реализация
Хеширование является одним из самых мощных способов повышения производительности компьютера. Использование хеш таблиц является основным инструментом в программирование шахматных игр.
Хеш таблица - представляет из себя большую индексированную таблицу, в ячейках которых храниться следующая информация:
2 хеш индекса
глубина просчета для этого хода
ход
оценка этого хода
Выбор алгоритма подсчета хеш индекса хода - является важнейшим моментом, при использовании алгоритмов хеширования. При выборе алгоритма расчета хеш индекса надо учитывать 2 важнейших момента:
индекс должен наиболее отражать уникальную информации о ходе, чтобы максимально сократить количество коллизий
хеш индекс должен быть простым для подсчета
Сложный алгоритм, дает наилучшие показатели количества коллизий, но они сложно для просчета, а следовательно отнимают много процессорного времени. Необходимо построить алгоритм, простой для подсчета, но имеющий минимально число коллизий.
Для подсчета индекса, была выбрана операции с некоторыми, случайно сгенерированными масками.
Изначально хеш маски заполняются случайными числами. Для каждой позиции рассчитывается 2 хеш индекса, первый используется для поиска позиции в хеш таблице, второй для проверки коллизий.
Перед любым использование информации из хеш таблицы, проверятся совпадение вторых хеш индексов, если они не совпадают, то произошла коллизия, и информация игнорируется.
Обновление информации о позиции следует проводить только в том случае, если текущая глубина просчета больше той, что уже храним в хеш таблице.
Информации из хеша, возможно доверять только в том случае, если глубина в хеше, больше текущей глубины просчета.
3.6 Использование библиотек дебютов
Алгоритм использования библиотек дебютов заключается в использовании заранее просчитанных баз данных с дебютами партий, так как в начале партии наибольшее количество возможных ходов имеющих одинаковые оценки.
3.7 Оценка позиции
При разработке алгоритма статической оценки позиции ( функции качества ) существует неопределенность выбора между качеством и скоростью работы. Качественные оценочные функции, основанные