Существует в основном две стратегии:
- Статический порядок ходов
- Динамический порядок ходов
При динамическом порядке перемещения используется информация из предыдущих поисков, либо потому, что вы снова переместились в ту же позицию, либо уже достигли позиции в предыдущем менее тщательном поиске. Вы упомянули эту идею итеративного углубления, которое непрерывно увеличивает расстояние поиска.
Динамический порядок движений очень мощный. Есть много способов сделать это, но два наиболее распространенных из них - это таблицы транспонирования и ходы убийцы:
Таблицы транспонирования кешируют информацию о предыдущих поисках, особенно лучший найденный ход. Когда та же самая позиция снова достигнута, вы можете сразу найти лучший ход из предыдущего поиска. Очень часто это подтверждается более глубоким поиском.
Ходы-убийцы используют аналогичный подход и имеют дополнительное преимущество в том, что они могут использовать знания из одинаковых, но не идентичных позиций. Однако качество ходов-убийц для упорядочивания ходов обычно хуже, чем для ходов из таблиц транспозиции. Вот почему их обычно ищут после перемещения транспонирования.
Но что делать, если нет информации из предыдущих поисков? Часто у вас есть некоторые специфичные для предметной области знания, которые вы можете использовать для статического упорядочения перемещения. Например, в шахматах есть много эмпирических правил. Одним из них является то, что движения захвата с большей вероятностью будут лучшим движением, чем не захваты. Существуют более сложные стратегии (например, статический анализ повторного захвата), но вы должны быть осторожны, так как более сложные вычисления также замедляют поиск.
Комбинируя статическое и динамическое упорядочение ходов, шахматные движки часто могут угадать лучший ход в позиции с вероятностью попадания более 90%.