При компьютерном анализе шахмат обычно рассматривают дерево возможных ходов. Но однако такое дерево имеет одну важную особенность: различные его ветви далеко не всегда имеют одинаковую ценность для дальнейшего поиска. Предлагаемая в статье модель основана на предположении, что дерево поиска следует рассматривать не как неподвижную структуру, а как динамическую систему, в которой глубина каждой ветви определяется её изменяющейся перспективностью.
где D - глубина, до которой предлагается исследовать данную ветвь, D0 - начальная глубина поиска, E - изменение оценки позиции после очередного хода, а k - коэффициент чувствительности. То есть ветви, в которых оценка позиции резко изменяется, получают возможность более глубокого анализа.
Смысл этого подхода состоит в следующем. Если несколько последовательных ходов практически не изменяют положение фигур и оценку позиции, нет необходимости тратить одинаковое количество вычислений на каждую такую ветвь. Напротив, если один ход приводит к резкому изменению оценки, появлению угрозы, жертве фигуры или другому важному событию, именно эту часть дерева имеет смысл исследовать подробнее.
Величину I можно рассматривать как условную интенсивность изменения позиции. Чем больше значение I, тем сильнее отличается новая позиция от предыдущей с точки зрения используемой функции оценки. При малом значении I ветвь может рассматриваться с обычной глубиной, а при большом значении анализ может автоматически продолжаться.
Интересным следствием такой модели является то, что одинаковая глубина поиска для всех ходов становится необязательной. Например, спокойный ход пешки может быть исследован на небольшой глубине, тогда как взятие ферзя, жертва фигуры или открытие линии для атаки короля автоматически вызовет дополнительный анализ.
Здесь W - приоритет ветви, I - изменение оценки позиции, а N - количество уже рассмотренных похожих продолжений. Такая зависимость позволяет постепенно уменьшать приоритет повторяющихся и малоинформативных вариантов. В результате дерево поиска может самостоятельно перераспределять вычислительные ресурсы между различными направлениями анализа.
Особенно интересным является случай, когда две совершенно разные последовательности ходов приводят к позициям с близкими оценками. Обычный поиск может рассматривать их как независимые ветви, однако с точки зрения предлагаемой модели они могут иметь сходную структуру. Если удастся определить такие повторяющиеся структуры, часть вычислений можно будет использовать повторно.
где S(P) - расширенная оценка позиции, E(P) - обычная оценка позиции, R(P) - показатель её структурного сходства с уже исследованными позициями, а λ - коэффициент влияния этого сходства. В отличие от обычной оценки, такая функция учитывает не только качество самой позиции, но и информацию, полученную во время предыдущего поиска.
В итоге, дерево перестает быть простой последовательностью "ход - ответ - ход - ответ", а превращается в изменяющуюся систему, в которой одни ветви постепенно получают высокий приоритет, а другие практически перестают развиваться. Это позволяет сформулировать гипотезу о динамическом дереве поиска: оптимальная программа должна тратить вычислительное время не пропорционально количеству доступных ходов, а пропорционально информационной ценности этих ходов.
Конечно, предложенная модель является теоретической и сама по себе не доказывает, что такой способ поиска будет эффективнее существующих алгоритмов. Для проверки этой идеи потребовались бы реальные эксперименты с шахматным движком, сравнение времени поиска, количества просмотренных позиций и качества получаемых ходов. Однако сама возможность изменять глубину поиска в зависимости от характера позиции представляет интерес для дальнейшего изучения компьютерного анализа шахмат. Возможно, статья получит продолжение - следите на этой странице.