При минимаксном поиске проблема состоит в том, что количество состояний игры, которые должны быть исследованы в процессе поиска, зависит экспоненциально от количества ходов. К сожалению, такую экспоненциальную зависимость устранить невозможно, но фактически существует возможность сократить ее наполовину. Весь секрет состоит в том, что вычисление правильного минимаксного решения возможно без проверки каждого узла в дереве игры. Это означает, что можно позаимствовать идею отсечения, описанную в главе 4, чтобы исключить из рассмотрения большие части дерева. Конкретный метод, рассматриваемый в данной главе, называется альфа-бета-отсечением. Будучи применен к стандартному минимаксному дереву, этот метод возвращает такие же ходы, которые вернул бы минимаксный метод, но отсекает ветви, по всей вероятности, не способные повлиять на окончательное решение.

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

<< В начало < Предыдущая 1 2 3 4 5 Следующая > В конец >>