Когда прекратить итерационное углубление с помощью альфа-бета-обрезки и таблиц транспонирования?

Question

Как узнать, когда я могу остановить увеличение глубины для алгоритма итерационного углубления с помощью таблиц обрезки и транспонирования альфа-бета с negamax? Следующий псевдокод взят со страницы вики:

function negamax(node, depth, α, β, color) 
alphaOrig := α 

// Transposition Table Lookup; node is the lookup key for ttEntry 
ttEntry := TranspositionTableLookup(node) 
if ttEntry is valid and ttEntry.depth ≥ depth 
    if ttEntry.Flag = EXACT 
     return ttEntry.Value 
    else if ttEntry.Flag = LOWERBOUND 
     α := max(α, ttEntry.Value) 
    else if ttEntry.Flag = UPPERBOUND 
     β := min(β, ttEntry.Value) 
    endif 
    if α ≥ β 
     return ttEntry.Value 
endif 

if depth = 0 or node is a terminal node 
    return color * the heuristic value of node 

bestValue := -∞ 
childNodes := GenerateMoves(node) 
childNodes := OrderMoves(childNodes) 
foreach child in childNodes 
    val := -negamax(child, depth - 1, -β, -α, -color) 
    bestValue := max(bestValue, val) 
    α := max(α, val) 
    if α ≥ β 
     break 

// Transposition Table Store; node is the lookup key for ttEntry 
ttEntry.Value := bestValue 
if bestValue ≤ alphaOrig 
    ttEntry.Flag := UPPERBOUND 
else if bestValue ≥ β 
    ttEntry.Flag := LOWERBOUND 
else 
    ttEntry.Flag := EXACT 
endif 
ttEntry.depth := depth 
TranspositionTableStore(node, ttEntry) 

return bestValue 

И это итерационный Углубление вызов:

while(depth < ?) 
{ 
    depth++; 
    rootNegamaxValue := negamax(rootNode, depth, -∞, +∞, 1) 
} 

Конечно, когда я знаю, что общее количество ходов в игре я мог бы использовать depth < numberOfMovesLeft как верхняя граница. Но если эта информация не указана, когда я знаю, что другой вызов negamax не дает лучшего результата, то предыдущий запуск? Что мне нужно изменить в алгоритме?

Answer 1

Короткий ответ: , когда вы бежите из времени (и транспозиционные таблицы не имеют никакого отношения к ответу/вопрос)

---

Здесь я предполагаю, что функция оценки разумно (дает хорошее приближение позиции).

Основная идея объединить итерационное углубление с альфа-бетами заключается в следующем: предположим, что у вас есть 15 секунд, чтобы придумать лучший ход. Как далеко вы можете искать? Я не знаю, и никто больше не знает. Вы можете попытаться выполнить поиск до depth = 8, чтобы узнать, что поиск завершен за 1 секунду (так что вы остаетесь свободными 14 секунд). С проб и ошибок вы обнаружили, что depth = 10 дает вам результат в 13 секунд. Поэтому вы решили использовать его все время. Но теперь что-то пошло ужасно неправильно (ваша альфа-бета не была достаточно обрезкой, некоторые позиции заняли слишком много времени, чтобы оценить), и ваш результат не был готов через 15 секунд. Таким образом, вы либо сделали случайный ход, либо проиграли игру.

Чтобы этого не было, хорошо иметь хороший результат. Итак, вы делаете следующее. Получите лучший результат для depth=1 и сохраните его. Найдите лучший результат для depth=2 и перезапишите его. И так далее. Время от времени проверяйте, сколько осталось времени, и если это действительно близко к timelimit - верните свой лучший ход.

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