Может ли таблица транспозиции вызвать нестабильность поиска
Я пишу шахматный движок и недавно добавил таблицу транспозиции.
Проведя несколько тестов, я обнаружил, что, хотя поиск все еще возвращал тот же самый лучший ход, значение этого шага (насколько он хорош для максимизирующего игрока) колебалось.
Это нормальное поведение для таблицы транспозиции? Я помню, как читал, что таблица транспонирования может вызвать нестабильность поиска. Это что значит? Так это нормальное явление или серьезная ошибка в моем коде?
Решение
Да, таблицы транспонирования вводят нестабильность поиска.
К счастью, это происходит достаточно редко, когда преимущества таблиц транспозиции значительно перевешивают это осложнение.
1. Какова функция таблицы транспозиции?
После добавления таблиц транспозиции (TT) в вашу программу вы должны заметить два основных различия:
- Улучшение порядка ходов: ход из ТТ, как правило, является наилучшим из возможных ходов.
- Ранние отсечки: когда вы снова достигнете позиции, которая уже была найдена на большем расстоянии, вы можете остановиться и использовать значение, сохраненное в записи TT
В шахматах улучшенный порядок ходов является наиболее важным фактором. Только в эндшпилях вероятность переноса увеличилась, и вы увидите более ранние отсечки.
Итак, что означает нестабильность поиска? Это означает, что при поиске одной позиции с заданным расстоянием, а затем повторении одного и того же поиска (та же позиция, то же расстояние), вы получите идентичный результат.
2. Простой минимаксный / альфа-бета поиск algorthm
Давайте сначала проигнорируем расширение поиска и начнем с простого минимаксного или альфа-бета-поиска.
Обратите внимание, что ваш поиск будет иметь свойство, что поиск повторяется, и не будет видеть нестабильности поиска. Даже если вы улучшите порядок своих перемещений с помощью перемещения из таблицы транспонирования, вы все равно будете получать одинаковый результат для каждого поиска. Однако после добавления TT дополнительные отсечки от более глубокого поиска, как правило, нарушают это свойство и приводят к нестабильности.
Например, рассмотрим позицию, содержащую глубокую тактику:
- Поиск с небольшим расстоянием может не видеть его, но поиск с большим расстоянием будет.
- После того, как этот результат сохранен в TT, повторный поиск с небольшим расстоянием также увидит тактику. Теперь он ведет себя по-другому по сравнению с исходным поиском.
- Еще хуже, когда запись TT перезаписывается, улучшенные знания снова получают много.
Таким образом, использование дополнительных знаний для принудительного прекращения работы является фактором, который приводит к нестабильности. (Но на практике это того стоит, так как это скорее теоретическая проблема.)
3. Поиск расширений
При применении к простому альфа-бета-поиску улучшенное упорядочение ходов само по себе не приводит к нестабильности поиска. Ситуация более сложна в реальных алгоритмах поиска, которые реализуют множество расширений. Некоторые из этих расширений также чувствительны к порядку перемещения.
Один яркий пример называется Снижение позднего хода (LMR). Он использует тот факт, что качество порядка ходов, как правило, настолько высоко, что необходимо тщательно искать только первые несколько ходов, в то время как другие ходы, скорее всего, плохие и будут искать только с уменьшенным расстоянием.
LMR — это только один пример, когда порядок перемещения делает поиск менее повторяемым. Но опять же, преимущества преобладают.
4. Сколько нестабильности поиска нормально?
Четкого ответа нет. На практике вы не можете полностью устранить нестабильности, но если нестабильность выйдет из-под контроля, ваш поиск станет неэффективным.
Конечно, ошибки могут быть причиной нестабильности тоже. Итак, это ошибка в вашем поиске? Ну, я не знаю. Может быть. 🙂
Другие решения
Это нормальное поведение для таблицы транспозиции? Я помню, как читал
что таблица транспонирования может вызвать нестабильность поиска. Это что
это означает?
Да.
Так это нормальное явление или серьезная ошибка в моем коде?
Джонатан Шеффер совет (в разделе «План атаки»):
Если вы изначально ограничиваете поиск TT, чтобы он был действительным, только если таблица
глубина точно соответствует необходимой глубине, тогда ТТ не будет
изменить результат поиска альфа-беты с фиксированной глубиной. Должно,
тем не менее, уменьшите количество искомых узлов. Убедитесь, что это
работает правильно.Добавить в итеративное углубление и переместить порядок. Если вы делаете это правильно, это
не должен изменять конечный результат поиска, но, опять же, он должен
уменьшить количество искомых узлов.Только когда вы уверены, что все вышеперечисленное работает на 100%, вы должны двигаться
на большее количество улучшений поиска и лучшую функцию оценки.