Поиск покоя — обработка флагов Exact/Alpha/Beta для таблицы транспонирования

Я добавляю поиск покоя в свой шахматный движок, используя альфа-бета-обрезку с таблицами транспонирования, вызываемыми внутри алгоритма MTD(f). В моем основном поиске, после достижения глубины = 0 (конечный узел), я вызываю поиск Quiescence, который реализован как простая альфа-бета-обрезка без таблицы транспонирования (поскольку тесты показали, что поиск только по захватам работает быстрее без TT).

Я заметил кое-что, что не описано в псевдокодах по этой теме: когда я нахожусь на глубине = 0 (лист) в основном поиске и вызываю функцию поиска покоя для получения оценки узла, я думаю, что я также должен получить тип оценки: точный , альфа или бета:

... beginning of main alpha-beta search, checking node in TT
if (depth == 0)
{
    // calling quiescence search with current alpha beta
    int qresult = QuiescenceAlphaBetaSearch(node, alpha, beta);
    saveInTT(node, qresult.Type, qresult.Value);
} 
else
{
    ... run alpha beta search of node.children
}

В типичных примерах оценка конечного узла всегда хранится в TT как «точное» значение, но когда оценка узла основана на альфа-бета-поиске с помощью захватов, и этот поиск начинается с границ альфа-бета, которые не являются (-inf,+inf), Я думаю, что результат QuiescenceAlphaBetaSearch не всегда будет точным значением, и если он хранится в TT, он должен быть помечен флагом, возвращаемым из поиска покоя, я прав?

Я не совсем уверен, что передача текущей альфы и беты из основного поиска в поиск покоя математически правильна, поэтому я был бы признателен за подтверждение и по этой теме.


artificial-intelligence algorithm heuristics chess alpha-beta-pruning
person PanJanek    schedule 04.05.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Как я уже сказал, записи TT поиска покоя будут использоваться редко. Из-за дороговизны доступа к основной памяти быстрее не пробовать попадание ТТ и вычислять позицию. Если вы реализуете хеш-таблицу без списков переполнения и перезаписываете хеш-записи, вы определенно перезаписываете только существующие записи, когда новая запись была найдена на «лучшей» глубине. Поэтому, когда вы начинаете заполнять хеш-таблицу, у вас нет возможности быстро сохранить запись TT, потому что есть лучшие записи, у которых не «больше», чем максимальная глубина, как у этих записей покоя.

Но если вам нравится записывать узлы покоя в таблицу TT, тем не менее, вы можете использовать «обычные» флаги точного, верхнего и нижнего пределов. Вы можете использовать флаг «точно», когда нет альфа- или бета-обрезки, потому что новый поиск покоя, который начинается в той же позиции, вернет то же значение.

person TheSlater    schedule 22.07.2015

arrow_upward
0
arrow_downward

Уже существует защита от неправильного использования значения TT ​​покоя. Запись TT хранит глубину, на которой было найдено значение, и поэтому она будет использоваться только тогда, когда поиск осуществляется на той же или большей глубине поиска. Как вы сказали, TT не будет использоваться в узлах выхода, поэтому не повредит, получено ли значение из поиска покоя или нет.

person TheSlater    schedule 13.05.2015
comment
Под листовым узлом я понимаю лист основного поиска. После достижения определенной глубины выполняется еще один поиск состояния покоя с текущими значениями альфы и беты. Я хотел бы сохранить результат поиска в TT, но я не уверен, что его можно считать точным. - person PanJanek; 19.05.2015
comment
@PanJanek, я все еще пытаюсь понять твой вопрос. Почему вы не можете просто сохранить результат в TT, например, точные, верхние и нижние границы напрямую в TT? Так работают все современные двигатели. - person SmallChess; 05.06.2015