Главная » Игры, Теория » Эвристика истории

0

(History heuristic) является статистическим методом упо­рядочивания перемещений. Позиция имеет размер 8×8 или 0..63. Можно сделать некоторую таблицу [64] [64], обнуленную в начале вычисления. Если данное перемещение вызывает улучшение alpha (или отсечку за beta), то в клетке [ni] [n2] можно увеличить значение на 1, где ni — позиция, от­куда пошла фигура, а n2 — куда пошла.

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

?    взятие короля (если был шах в преузле);

?    взятие последней ходившей фигуры противника;

?    определение атаки (последняя ходившая фигура противника напала на большую или незащищенную фигуру);

?    если атака, берем перемещения атакованной фигуры;

?    еслй не было взятия последней ходившей фигуры противника или атаки, пробуем Killer — лучший ход соседа на этой глубине (он в преузле сбра­сывается);

?    остальные взятия берутся по принципу "наиболее ценная жертва — наи­менее ценный нападающий";

?    остальные перемещения добавляются в список и будут рассмотрены в самом конце, если имеет место потеря при взятии;

?    Killer не записывается, если было взятие короля, последней ходившей фигуры или атака;

D если не было атаки, "тихие" перемещения просчитываются от лучших (сразу) до худших;

?    потери материала в любом случае рассматриваются в конце;

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

Данный порядок ходов не является единственно правильным, но отражает реальное положение вещей. Killer — очень мощная эвристика, если не было взятия последней сходившей фигуры или тяжелой атаки — тогда лучший ход, безусловно, другой. Хочется спросить: куда здесь можно вставить эври­стику истории с ее статистикой? Только для тихих перемещений. Но если тихие перемещения брать просто по приращению позиционной оценки, мы гарантированно ускорим процесс в несколько раз. Если атака оппонента, перемещения сортировать вообще не нужно. Не обязательно генерировать все перемещения сразу.

У нас есть списки фигур, и мы можем быстро сгенерировать нужное пере­мещение и сразу просчитать его. Эвристику убийцы и ход из хеша вообще не нужно получать, их только надо проверить на легальность. Ход из хеша идет самым первым. Тихие перемещения можно упорядочить по статистике, но упорядочивание по приросту оценки дает гарантированный результат.

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

Литература:

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

По теме:

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