Главная » Алгоритмы, Игры » Сортировка простых перемещений

0

Простые перемещения тоже нужно сортировать. Если у простых перемеще­ний нет приращения стратегической оценки (в случае, если мы считаем только материал), то все они одинаковы, с точки зрения alpha-beta, и сор­тировать их незачем. Как же осуществляется сортировка простых переме­щений? У нас есть функция Evaluate, которая статически оценивает пози­цию. Вызывать ее для каждого перемещения в генераторе ходов, чтобы по­лучить величину приращения оценки при этом перемещении, слишком большая роскошь. Тут возможны два пути:

?     Если в программе материальная и позиционная оценка вычисляются пошагово (сделали ход — подсчитали изменение), то все очень просто. Мы легко можем узнать приращение стратегической оценки для данного хода.

?     Если оценка позиции в программе такова, что не может быть вычислена пошагово, нужно определять примерное приращение стратегической оценки для данного хода.

Можно делать три списка (по аналогии с сортировкой взятий). В первый список заносятся худшие ходы (приращение оценки меньше 0), во вто­рой — средние (незначительное приращение), в третий — лучшие. Этого, как правило, оказывается достаточно, чтобы ускорить счет в несколько раз. Конец списка соединяется с началом предыдущего и получается один спи­сок. Для отслеживания конца списка можно использовать ссылку на указа­тель. Вставка осуществляется всегда в конец списка, а ссылка на указатель передвигается при каждой вставке и всегда указывает на конец. Начало списка — простой указатель. Если генератор ходов объединен с функцией счета, то список лучших ходов можно не вести, а тотчас же выполнять счет, как только нашли лучший ход. Шахи являются, бесспорно, самыми лучши­ми из простых ходов, но специально их выявлять в генераторе ходов слиш­ком накладно. При использовании хеш-таблиц лучшие ходы все равно будут запоминаться, и это не принципиально. Для сортировки простых переме­щений используются также различные эвристики: эвристика убийцы (Killer heuristic), эвристика истории лучших ходов (History heuristic), таблица пере­становок, итеративные углубления. Это все будет описано позже. Пока мы лишь рассмотрели сортировку простых перемещений по значению, что, не­смотря на простоту, качественно ускоряет счет. Для сравнения: NegaScout разгоняет максимум на 50%, а простая сортировка перемещений — в не­сколько раз.

Существует еще один способ построения программы. Получили хорошее перемещение — сразу же обсчитываем и не ждем генерации всех перемеще­ний. Такая программа содержит множество вложенных функций. Со спи­сками фигур такую схему построить нетрудно. Скажем, для взятий мы на­чинаем перебирать наш список с наименьших фигур. Если фигура может бить последнюю ходившую фигуру противника (для этого- используется прием, аналогичный детектору шахов), то выстраивается линия до нее (для дальнобойных фигур). Если ход корректен, то его сразу обсчитываем, потом пробуем лучший ход соседа по узлу, потом — остальные взятия. Мы про­сматриваем список фигур противника, начиная с наибольших, и пытаемся бить нашей наименьшей фигурой. Нашли перемещение — сразу же в сле­дующую позицию. Простые перемещения тоже можно брать со смыслом.

Если расстояние между нашим ферзем и королем противника опасно сокра­тилось или проходная пешка — обсчитываем сразу. Если плохое перемеще­ние — добавляем в список и рассмотрим в конце. Генерация перемещений должна быть разумной и в то же время быстрой.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии