Форма входа

Наша реклама

Помогите сайту просмотрите рекламу

Поиск

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Наш опрос

Оцените мой сайт
Всего ответов: 122

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0




Пятница, 29.03.2024, 00:30
Приветствую Вас Гость | RSS
Скорая помощь для студентов
Главная | Регистрация | Вход
Лекция 17


Алгоритм альфа-бета отсечения

Нижеследующий алгоритм вычисляет F(p) в соответствии с определением (1):

      integer procedure F(position p):

         begin integer m,i,t,d;

         Определить позиции p1,...,pd, подчиненные p;

         if d = 0 then F := f(p) else

         begin  m := -;

            for i:= 1 step 1 until d do

               begin t := -F(pi);

                  if t > m then m:= t;

               end;

            F := m;

         end;

      end.

Здесь + обозначает число, которое не меньше abs(f(p)) для любой терминальной позиции p; поэтому - не больше F(p) и -F(p) для всех p. Этот алгоритм вычисляет F(p) на основе "грубой силы": для каждой позиции он оценивает все возможные продолжения; "лемма о бесконечности" гарантирует окончание вычислений за конечное число ходов.

Перебор, который осуществляет этот алгоритм, можно уменьшить, используя идею метода "ветвей и границ". Идея состоит в том, что можно не искать точную оценку хода, про который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных раньше. Пусть, например, в процессе перебора стало известно, что F(p1) = -10. Мы заключаем отсюда, что F(p)>=10, и потому нам не нужно знать точное значение F(p2), если каким-либо образом мы как-то узнали, что F(p2)>=-1 (и, таким образом, что -F(p2)<=10). Итак, если p21 допустимый ход из p2 и F(p21)<=10, мы можем не исследовать другие ходы из p2. В терминах теории игр ход в позицию p2 "опровергается" (относительно хода в p1), если у противника в позиции p2 есть ответ, по крайней мере столь же хороший, как его лучший ответ в позиции p1. Ясно, что если ход можно опровергнуть, мы можем не искать наилучшее опровержение.

Эти рассуждения приводят к алгоритму, гораздо более экономному, чем F. Определим F1 как процедуру с двумя параметрами p и bound; наша цель - удовлетворить следующим условиям:

F1(p, bound) = F(p), если F(p) < bound,                                                                                            (6)

F1(p, bound) > bound, если F(p) > bound.

Эти условия не определяют F1 полностью, однако, позволяют вычислить F(p) для любой начальной позиции p, поскольку из них следует, что

F1(p,+ ) = F(p).                                                                                                                  (7)

Идею метода ветвей и границ реализует следующий алгоритм:

integer procedure F1(position p, integer bound):

  begin integer m,i,t,d;

    Определить позиции p1,...,pd, подчиненные p;

    if d = 0 then F1 := f(p) else

      begin m := -;

        for i:= 1 step 1 until d do

          begin t := -F1(pi, -m);

            if( t > m then m := t;

            if m >= bound then goto done;

          end;

  done: F1 := m;

      end;

  end.

Правильность работы этой процедуры и то, что результат удовлетворяет соот-ношениям (6), можно доказать следующими рассуждениями. Легко видеть, что в начале i-го витка for-оператора выполнено "инвариантное" условие

m = max { -F(p1), ..., -F(pi-1)}.                                                                       (8)

Здесь предполагается, что максимум по пустому множеству даст -. Поэтому, если -F(pi) > m, то, используя условие (6) и индукцию по длине игры, начинающейся в p, получаем F1(pi,-m) = F(pi). Следовательно, в начале следующего витка (8) также будет выполнено. Если же max {-F(p1,...,-F(pi)} >= bound при всех i, то F(p) >= bound. Отсюда следует, что (6) выполняется для всех p.

Эту процедуру можно еще улучшить, если ввести не только верхнюю, но и нижнюю границу. Эта идея - ее называют минимаксной альфа-бета процедурой или просто альфа-бета отсечениями - является значительным продвижением по сравнению с односторонним методом ветвей и границ. (К сожалению, она применима не во всех задачах, где используется метод ветвей и границ; она работает только при исследовании игровых деревьев.) Определим процедуру F2 с тремя параметрами p, alpha и beta (причем всегда будет выполнено alpha < beta), которая удовлетворяет следующим условиям, аналогичным (6):

F2(p,alpha,beta) <= alpha, если F(p) < alpha,                                                                     (9)

F2(p,alpha,beta) = F(p), если alpha < F(p) < beta,

F2(p,alpha,beta) >= beta, если F(p) >= beta.

И снова эти условия не определяют F2 полностью, однако, из них следует, что

F2(p,-, +) = F(p).                                                                                  (10)

Оказывается, представление этого улучшенного алгоритма на языке программирования лишь чуть-чуть отличается от алгоритмов F и F1:

     integer procedure F2(position p, integer alpha, integer beta):

         begin integer m,i,t,d;

         Определить позиции p1,...,pd, подчиненные p;

         if d = 0 then F2 := f(p) else

         begin  m := alpha;

            for i:= 1 step 1 until d do

               begin t := -F2(pi, -beta, -m);

                  if t > m then m := t;

                  if m >= beta then goto done;

               end;

     done: F2 := m;

         end;

     end.

 


 



Copyright MyCorp © 2024