ДВУХСТУПЕНЧАТЫЙ АЛГОРИТМ ПЕРЕБОРА В ШАХМАТНОЙ ПРОГРАММЕ

Марков С.
Оленин Н., международный мастер спорта
Научный руководитель: Костенко Т.П.

          Одной из важных проблем организации минимаксного перебора позиций в игре является выбор эвристической функции, используемой для оценки позиций в листьях дерева поиска. Сложность заключается в выборе факторов, учитываемых эвристикой. Здесь существует две крайности. С одной стороны, мы можем заложить в оценочную функцию максимальное количество формализуемых свойств позиции. В этом случае позиционная оценка станет достаточно точной, однако, скорость вычисления эвристики будет очень велика. Это приведет к тому, что программа, основанная на подобной функции, не сможет осуществить достаточно глубокий перебор вариантов. Как следствие, такая программа будет неплохо вести стратегическую, позиционную борьбу в относительно спокойных позициях, но не сможет эффективно комбинировать и наносить тактические удары в острые моменты игры.
          Другая крайность - построение оценочной функции с минимумом факторов. Очевидно, что программа, основанная на такой оценочной функции, будет обнаруживать прямо противоположную слабость.
          Авторами предлагается два различных подхода к разрешению вышеописанной проблемы.
          Первый, заключается в отделении тактического перебора от стратегического. Вводится две оценочные функции. Первая - H₁ - включает в себя только оценку материала, а также способна обнаруживать матовые или патовые ситуации. Вторая - H₂ - включает в себя максимально возможное число параметров позиции.
          На первом этапе перебор осуществляется при помощи функции H₁. В результате этого перебора отбирается группа ходов, оценка которых не более чем на некоторую грань w отличается от наилучшего. Это значит, что если существуют ходы, ведущие в пределах горизонта перебора к мату или безвозмездному выигрышу материала, то они автоматически окажутся выбранными. Если таких ходов нет, будут отобраны ходы не приводящие к потере материала или к получению мата. Если потеря материала неизбежна, то отобранными окажутся ходы, теряющие наименьшее его количество.
          Для отобранных ходов производится перебор, основанный на функции H₂. Т.е. из "тактически допустимых" ходов выбирается наилучший с точки зрения стратегической оценочной функции.
          Описанный метод реализован в программе SMARTHINK v0.01.
          Вторым перспективным методом перебора оказывается разделение в дереве перебора материальной составляющей оценки от позиционной. Причем позиционная оценка производится только до глубины k. Если p₁...p_n - позиции, возникшие на k-ом уровне дерева перебора, а S(p_i) - поддерево, корнем которого является позиция p_i, то позиционная оценка позиции a є S(p_i) принимается равной позиционной оценке p_i.
          Данная схема находится в стадии реализации.