Функции выигрыша

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

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

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

Ниже перечислен ряд других правил, в соответствии с которыми действуют хорошие шахматные программы:

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

2. Распространение “цепочек взятия”, которые представляют собой последовательности ходов сопровождающиеся взятием фигур противника, за пределы последнего уровня, до которого обычно распространяется дерево. Это помогает более точно оценить относительную материальную силу позиций.

3. Сокращение поиска на дереве методом альфа-бета отсечения (см. дальше в этом разделе)

Метод ветвей и границ

Игры – не единственная категория задач, которые можно решать полным перебором всего дерева возможностей.

Широкий спектр задач, в которых требуется найти минимальную или максимальную конфигурацию того или иного типа, поддаются решению путем поиска с возвратом, применяемого к дереву возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций, а каждый потомок узла n представляет некоторое подмножество конфигураций.

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

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