e3e5.com
ВСЕ СТАТЬИ АВТОРА

24.06.2004 В.Баженов. ПУТЕШЕСТВИЕ ПО ШАХМАТНОМУ ДЕРЕВУ.

(Лекции шахматного любителя)

Лекция  №2.  Логика электронных монстров (часть 1)

(Читать лекцию №1)

Диаграмма  5.

          На диаграмме изображена гипотетическая позиция, которая вряд-ли случится в реальной партии. Шахматная компьютерная программа «Frits-7» дает мгновенную оценку + - 6,04.  Через час непрерывной работы оценка «Фрица» практически не изменилась + - 6,29. В переводе на человеческий язык, такая оценка  означает – у белых абсолютно выигранная позиция, черным пора сдаваться.

          Не нужно быть шахматным мастером и не нужно анализировать позицию в течение часа, чтобы понять : на доске стоит теоретическая ничья. Пешечные редуты перегораживают доску по горизонтали. Белые слоны, белый король вынуждены вечно маневрировать на своей половине доски. Черный слон и черный король также никогда не проникнут в расположение белых фигур. Ничья.        

          Почему же одна из лучших шахматных программ так грубо ошибается в оценке этой тривиальной позиции (и не только этой, - добавит любой гроссмейстер, хорошо знакомый с «Фрицем»)?

          Здесь и далее, всякую шахматную программу мы будем именовать  просто - Фриц.               

          Попробуем  ответить на поставленный вопрос. Пришло время пояснить, как «мыслит» Фриц.

           Мышление Фрица практически всегда основано всего на двух вычислительных процедурах:  процедуре оценки позиции и процедуре построения дерева.

          Автору неизвестны какие-либо умеющие играть в шахматы компьютерные программы, основанные на иных вычислительных процедурах.

           Остановимся подробнее на их описании.

Процедура оценки позиции

       Фриц способен оценивать любую позицию. Как правило, для оценки позиции Фриц рассчитывает так называемую оценочную функцию (сокращенно ОФ). Различные Фрицы используют различные ОФ.

       Пример простейшей ОФ - когда при оценке позиции учитывается только разность в материале. 

       Например, в позиции на диаграмме № 6 у черных  лишняя пешка.

      Здесь и в дальнейшем, мы будем рассчитывать материал исходя из традиционных  представлений о сравнительной ценности фигур:

      Пешка    -    1

      Конь      -    3

      Слон      -   3

     Ладья     -   5

     Ферзь     -   9

     Что же касается ценности короля, примем это значение (пока без объяснений) заведомо большим, равным – 1000.

     В дальнейшем, поскольку оба короля всегда присутствуют на доске, будем рассчитывать разность материала только по фигурам и пешкам, опуская при этом вес королей.

Диаграмма  6.

       Простейшая ОФ, учитывающая только материальный фактор, для позиции на диаграмме № 6 рассчитывается очень просто  ОФ = 2 - 3 = -1. Если бы на диаграмме № 6 отсутствовала любая черная пешка, то ОФ имела бы значение ОФ = 2 – 2 = 0.   Если бы на доске  осталась  всего  одна  черная  пешка,  то  значение  ОФ  стало бы положительным ОФ = 2 – 1 = 1. Таким образом, мы видим, что значение ОФ может быть отрицательным (что, по мнению компьютера, означает преимущество черных), положительным (преимущество белых) или равным нулю (на доске равенство). Необходимо особенно подчеркнуть, что таковым будет мнение компьютера, вооруженного очень примитивным инструментом для оценки позиции.  Почему примитивным?  Во-первых потому, что позиция на  диаграмме № 6 выиграна за белых независимо от очереди хода. Однако ОФ = -1 неверно указывает на преимущество черных.

Диаграмма  7.

       Для диаграммы № 7 ОФ = 1  – 3 = - 2. Электронный монстр, обладающий такой ОФ, оценивает позицию как выигранную за черных. Никто не будет возражать, что две лишние  пешки в большинстве случаев - это выигрыш. Но не всегда. В нашем случае все зависит от очереди хода. У черных выиграно только при их очереди хода: ¢e5, и король черных в квадрате. При ходе белых, они выигрывают ходом h6. Черный король не попадает в квадрат, белые успевают поставить ферзя.

       Для более точной оценки позиции приходится писать более замысловатые ОФ, которые кроме материального фактора учитывают и позиционные плюсы и минусы позиции. Плюсы это позиционные факторы в пользу белых, а минусы, соответственно, - в пользу черных. Здесь простор для фантазии авторов шахматных программ не ограничен. Привлекая шахматных мастеров, программисты стараются написать ОФ, которые бы учитывали, кроме материального фактора, и иные позиционные особенности позиции. В ОФ начинают вводить позиционные оценки, выраженные в пешечном эквиваленте.  

      Например:

·         владение центром                                                           0,45

·         владение открытыми линиями (диагоналями)                 0,15

·         выполненная рокировка                                                  0,05

·         преимущество двух слонов                                              0,30

·         сдвоенные изолированные пешки                                 - 0,30

·         слабая пешка                                                                - 0,25

·         открытый король в миттельшпиле                                 - 0,45

и т.д.

 

      Автор, совершенно произвольно (только в качестве примера) указывает численные значения, приписываемые тем или иным позиционным факторам

 

     Таким образом, суммируя материальные и позиционные оценки за белых и вычитая из них материальные и позиционные оценки за черных, можно получать довольно приличные оценочные функции. Некоторые Фрицы используют ОФ, учитывающие до нескольких сотен  (иногда нескольких тысяч) позиционных факторов. Во многом сила игры компьютера зависит от удачно подобранной ОФ (т.е. фактически от работы шахматных консультантов, помогающих программистам в создании ОФ).

     Естественно, что ОФ различных Фрицев, могут серьезно различаться по принципам построения. Численные оценки могут не просто суммироваться, а, например, перемножаться, ранжироваться, изменяться в зависимости от  других факторов и т.д. Но это уже тайны создателей Фрицев, это их ноу-хау, а для нашей статьи не так уж важно, как на самом деле устроена та или иная ОФ. Принципиально для нас, в конечном счете, то, что ОФ любого из известных сегодня Фрицев включает материальную и позиционную составляющие и выражается десятичным числом, которое может быть отрицательным, положительным или равным нулю. Как правило, одна единица ОФ эквивалентна стоимости одной пешки. Важно также отметить, что видно из примера на диаграмме № 7, что численное значение ОФ имеет смысл только при указанной очередности хода.

     Здесь уместно заметить, что в приведенных выше рассуждениях имеет место большая «дыра». Дотошный читатель может возразить – зачем нам в позиции на диаграмме №6 нужна сложная оценочная функция?  Будем считать только материал. Но не на один ход, а, предположим, на три хода вперед. Пусть очередь хода за белыми. Тогда, через три хода белая пешка превратится в ферзя. ОФ = 9 + 1 – 3 = 7. У белых выиграно.

     Читатель прав. В позиции на диаграмме № 7, как и во множестве других позиций, оценивать позиционные факторы не имеет смысла. Необходимо считать, причем как можно дальше, и как можно шире. И здесь может возникнуть простая идея: снабдить компьютер простейшей ОФ, оценивающей только разность в материале, и дать ему возможность рассчитывать ходов на двадцать пять вперед при обдумывании каждого хода… Вот только реализовать такую возможность на практике не удастся – на расчет вариантов не хватит компьютерного времени.

 

     Для расчета на двадцать пять ходов всех возникающих вариантов, то есть для построения пятидесятиуровневого  дерева, самому совершенному компьютеру  понадобятся триллионы  и триллионы лет (См. лекцию №1. Дерево. Неприятность № 2).  

 

      При написании шахматных программ разработчики сталкиваются со сложным выбором из двух принципиальных возможностей:

 

· Применить громоздкую ОФ, учитывающую, помимо материала, большое количество позиционных факторов. При этом существенно сократить глубину расчета вариантов, поскольку чем больше составляющих входит в ОФ, тем больше времени требуется на ее многократное вычисление. 

 

· Написать простую (короткую) ОФ, тем самым сэкономив время ее вычисления и увеличив глубину расчета вариантов. При этом, потеряв в позиционной оценке, мы не так уж много выигрываем в глубине расчета вариантов. (С каждым новым полуходом дерево стремительно разрастается, «пожирая» драгоценное время, отведенное на расчет вариантов. Неприятность №2).

      Процедура построения дерева или искусство обрезания

       Когда Фриц играет в шахматы, он строит деревья. Каждому ходу Фрица соответствует дерево, которое он построил, чтобы выбрать этот один единственный ход. Дерево строится из той позиции, которая предшествовала ходу. Естественно, что Фриц строит дерево в электронном виде, при этом он генерирует шахматные позиции, записывая их, при необходимости, в память компьютера.

         Дерево, если оно строится не из начальной позиции, у программистов принято называть «поддеревом». «Поддеревом» также часто называют некое усеченное дерево, то есть дерево с сознательно обрезанными ветвями.

         Искусство обрезания ветвей в поддеревьях – это и есть искусство шахматного программирования. Чем больше ветвей обрежет Фриц при выборе очередного хода, тем на более низкий уровень он спустится при построении поддерева (на шахматном языке это означает - рассчитать более длинный вариант) за заданный промежуток времени. Искусство как раз и заключается в том, чтобы обрезать как можно больше ветвей, но при этом не обрезать «лишнего».

          При построении поддерева можно смело обрезать все ветви, исходящие из  повторяющихся позиций. Позиции в дереве могут повторяться, как в пределах одного уровня (одинаковые позиции могут возникнуть путем перестановок одних и тех же ходов), так и на разных  уровнях дерева (могут возникнуть при возврате ходов, повторении ходов). Возможны также иные многочисленные варианты возникновения одинаковых позиций в дереве.

          Автор не ставит перед собой цель объяснить читателю, как практически решаются  задачи построения поддеревьев, выявления повторяющихся позиций и отсечения ветвей. В  настоящей лекции всего лишь перечисляются некоторые проблемы, возникающие при разработке Фрицев, а также указывается основные методы их разрешения.  

           Остается еще множество путей отсечения ветвей, связанных, однако, с риском отсечь целый букет оригинальных позиций, которые потенциально могут вести к победе (или ничьей - в зависимости от целей игры).

           Соблазнительным с точки зрения экономии компьютерных ресурсов является отсечение ветвей, исходящих из «неперспективных» позиций. Правда заключается в том, что «неперспективность» позиций устанавливается при помощи все той же ОФ. При этом чем «качественней» ОФ, чем больше в ней, по мнению разработчиков Фрицев, учтено позиционных факторов, тем решительнее рубятся ветви на дереве.  Такой подход дает существенную экономию компьютерного времени, но Фриц при этом становится заложником качества ОФ.

Продолжение следует

 

 



   Главная  О компании  Статьи по разделам  Лучшие партии месяца  Творческие обзоры  Портрет шахматиста  Интервью  Закрытый мир  Архив Новостей  Гостевая книга  Ссылки