Cтраница 4
Таблицы времен, публикуемые разработчиком сортировки, можно построить при помощи программы, которая использует некоторый набор формул, а не отслеживает работу сортировки во время ее прогонов. Все временные характеристики сортировки, естественно, являются приблизительными. Качество сценки зависит от изощренности формул временных характеристик и объема учитываемых подробностей. Даже самая лучшая формула статической оценки временных характеристик является источником серьезной ошибки. [46]
Ясно, что оценка будет в пользу белых. Здесь все в порядке, если позиция спокойная и черные не располагают какой-либо сильной угрозой. Но, с другой стороны, если на следующем ходу черные могут взять белого ферзя, то такая оценка может привести к. Очевидно, что в спокойных позициях мы можем доверять такой статической оценке в большей степени, чем в активных позициях, когда с каждой из сторон имеются непосредственные угрозы взятия фигур. Поэтому статическую оценку следует использовать только для спокойных позиций. Что же касается активных позиций, то здесь существует такой стандартный прием: следует продолжить поиск из активной позиции за пределы ограничения по глубине и продолжать его до тех пор, пока не встретится спокойная позиция. В частности, таким образом производится просчет разменов фигур в шахматах. [47]
Стрелкой а обозначен ход, предложенный одним из генераторов. Полученная оценка будет принята в качестве рабочей оценки хода а. Рассматривая по очереди каждую цель из списка целей, машина пытается дать им соответствующую статическую оценку. В данном примере оценки для простоты даются в виде чисел. В действительности используются различные множества упорядоченных символов, причем структура каждого из этих множеств зависит от характера вычислений. [48]
В общем случае это, конечно, невозможно без динамического анализа позиции. Однако во многих случаях можно догадаться, что статическая оценка позиции вряд ли надежна. Предположим, например, что для некоторого пути, ведущего от корня дерева игры к некоторой вершине, статические оценки позиций колеблются от весьма высоких до совершенно неблагоприятных. Это может быть в случае затянувшегося размена фигур в шахматах при статической оценочной функции, подсчитывающей главным образом число фигур у каждого игрока. Очевидно, что никакая статическая оценка на таком пути не может быть признана надежной; следует продвигаться вниз по дереву, пока статические оценки не стабилизируются. В нашем примере с шахматами можно ожидать, что это будет достигнуто, когда в течение нескольких ходов не будет взято ни одной фигуры. [49]
Исследование продолжений основано на обобщении понятия мертвой позиции, введенного Тьюрингом. Статическая оценка для некоторой цели имеет смысл лишь в том случае, если позиция расценивается как мертвая в отношении этой цели, иначе говоря, если следующий ход не в состоянии сильно изменить эту компоненту статической оценки. Если нет, то генерируются ходы, которые оправданы в данной позиции и в то же время могут серьезно повлиять на статическую оценку данной цели. [50]
Статическая оценка для этой цели выполняет по существу отрицательные функции - ее задача обеспечить, чтобы не были сделаны ходы, предложенные для каких-либо других целей, но подвергающие опасности контроль над центром. Возможность того, что генератор ходов для других целей случайно выдаст ход, способствующий контролю над центром, попросту игнорируется. Типичным примером таких ходов могут служить ходы Cd3 и СеЗ, если соответствующие центральные пешки еще стоят на 2 - й горизонтали. Программа статической оценки отклонит эти ходы. [51]
Ясно, что оценка будет в пользу белых. Здесь все в порядке, если позиция спокойная и черные не располагают какой-либо сильной угрозой. Но, с другой стороны, если на следующем ходу черные могут взять белого ферзя, то такая оценка может привести к. Очевидно, что в спокойных позициях мы можем доверять такой статической оценке в большей степени, чем в активных позициях, когда с каждой из сторон имеются непосредственные угрозы взятия фигур. Поэтому статическую оценку следует использовать только для спокойных позиций. Что же касается активных позиций, то здесь существует такой стандартный прием: следует продолжить поиск из активной позиции за пределы ограничения по глубине и продолжать его до тех пор, пока не встретится спокойная позиция. В частности, таким образом производится просчет разменов фигур в шахматах. [52]
Здесь возникает изящный рекурсивный эффект. Дело в том, что динамическая оценка любой данной позиции включает просчет вперед на конечное число ходов - скажем, семь. При этом промежуточные позиции, получающиеся после каждого возможного хода, также должны получить какую-то оценку. Но когда программа оценивает эти позиции, она, разумеется, уже не может просчитывать на семь ходов вперед - иначе ей пришлось бы анализировать четырнадцать возможных позиций, затем двадцать одну и так далее, и тому подобное - что породило бы бесконечный регресс. Вместо этого программа пользуется статическими оценками позиций, возникающих при анализе. Таким образом, схема Самуэля включает сложную обратную связь, в процессе которой программа непрерывно пытается превратить оценки, основанные на просчете вариантов, в более простой статический подход; этот подход в свою очередь играет ключевую роль в динамическом взгляде вперед. Таким образом, оба этих метода тесно связаны между собой, и каждый рекурсивным путем извлекает пользу из улучшений в другом методе. [53]