ОРГАНИЗАЦИЯ ГРАФА ДЛЯ ПОИСКА ХОДОВ В ДЕБЮТНОЙ БИБЛИОТЕКЕ

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

          Организация дебютной библиотеки шахматной программы в виде дерева приводит к возникновению значительной избыточности. Действительно, некоторая позиция A может быть получена в результате различных последовательностей ходов. Пусть узлы B и B' представляют позицию A. Тогда поддеревья B и B' идентичны и их хранение приводит к неэкономному использованию ресурсов запоминающих устройств.
          Альтернативным способом представления дебютной библиотеки является хранение ее в виде ориентированного графа, в котором вершины соответствуют позициям, а ребра - ходам.
          Однако серьезной проблемой в таком случае становится организация быстрого поиска необходимой позиции.
          Выходом из сложившейся ситуации является использование хэширования. Возьмем две 32-битные функции H₁ и H₂. Позиции сортируются в порядке возрастания значения функции H₁ и снабжаются значением H₂. При поиске позиции A рассчитаем значение H₁ искомой позиции. Затем просмотрим все позиции x, у которых H₁(A)=H₁(x). Если среди них есть позиция для которой H₂(A)=H₂(x), то это и есть искомая позиция. Вероятность ошибки такого утверждения в случае независимости H₁ от H₂ исчезающе мала и ей можно пренебречь.