Я прочитал (например, http://radagast.se/othello/Help/order.html), что поиск лучших ходов на каждом уровне в первую очередь (которые можно найти с помощью итеративного углубления) значительно ускоряет поиск.
Как можно было бы искать наилучшие возможные ходы, не используя слишком много дополнительной памяти и процессорного времени?
В основном есть две стратегии:
Динамический порядок перемещений использует информацию из предыдущих поисков либо потому, что вы снова перемещаетесь в ту же позицию, либо вы уже достигли позиции в предыдущем менее тщательном поиске. Это идея итеративного углубления, о которой вы упомянули, которая постоянно увеличивает расстояние поиска.
Динамический порядок ходов очень эффективен. Есть много способов сделать это, но два самых распространенных — это таблицы транспонирования и убийственные ходы:
Таблицы транспонирования кэшируют информацию о предыдущих поисках, особенно о лучшем найденном ходе. Когда та же позиция будет достигнута снова, вы можете немедленно найти лучший ход из предыдущего поиска. Очень часто более глубокий поиск подтверждает, что это лучший ход.
Убийственные приемы используют аналогичный подход и имеют дополнительное преимущество, заключающееся в том, что они могут использовать знания из схожих, но не идентичных позиций. Однако качество ходов-убийц для упорядочения ходов в целом хуже, чем для ходов из таблиц транспонирования. Вот почему их обычно ищут после перемещения транспонирования.
Но что делать, если информации из предыдущих поисков нет? Часто у вас есть определенные знания предметной области, которые вы можете использовать для статического упорядочения перемещений. Например, в шахматах есть много эмпирических правил. Во-первых, ходы с захватом, скорее всего, будут лучшим ходом, чем не захваты. Существуют более сложные стратегии (например, статический повторный анализ), но вы должны быть осторожны, так как более сложные вычисления также замедляют поиск.
Сочетая как статический, так и динамический порядок ходов, шахматные движки часто могут угадать лучший ход в позиции с вероятностью попадания более 90%.
Если вы априори знаете, как искать лучшие ходы, вам вообще не нужно будет выполнять поиск. То, что вы можете сделать, часто требует некоторого опыта в игре, которую вы пытаетесь решить. Например, в шашках вы можете попытаться оценить все ходы, которые приводят к королю, прежде чем ходы, которые этого не делают.
