Конспект установочных лекций по комплексному курсу Информатика, Теория информации

Альфа»бета»поиск


В связи с игрой двух лиц мы встречаем следующую постановку задачи. В этой игре два игрока поочередно делают ходы из некоторого множества допустимых ходов, зафиксированного правилами игры. Если один из игроков сможет достичь определенной позиции (не сможет избежать определенной позиции), то он выигрывает (проигрывает) - ничьей не; бывает. Ищется ответ на вопрос: если задана позиция, то всегда ли выигрывает какой-либо игрок при оптимальном ведении игры?

Начнем с формализации проблемы. Пусть (x и р- игроки. Пусть у е {а, р} - один из игроков. Будем использовать следующие типы и функции для моделирования игры:

(1)        Рosition - тип позиции в игре, player - тип игрока, содержащий только элементы а и р.

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

(3)        Пусть t есть предикат на множестве игроков и позиций. Истинность t(s, р) определяет, является ли позиция р терминальной для игрока s, точнее: достигнут ли конец игры, когда в позиции р право хода имеет игрок s.

(4)        Пусть g - предикат на множестве игроков и позиций. Значение истинности g(s, р) устанавливает, является ли терминальная позиция р выигрышной для игрока s.

(5)        Для игрока s обозначим его партнера по игре через gegner (s). Всегда имеет место gegner (а) = ^ и gegner (?) = а.

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

fct sicher = (player

s, position р) bool:

       if  t(s, p)   then g(s, p)


                        else $ q Î Z(s, р): Øsicher(gegner(s), q)



       fi

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

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

Рис.10.1 передает дерево вызовов вычислительного предписания sicher для игрока а. Оно соответствует возможным ходам в игре. При этом в дереве оказываются по мере надобности попеременно ситуации для а и для р. Мы говорим об а-ситуации, если ход принадлежит а. Дерево позиций можно «раскрасить» путем деления его вершин на «надежные» и «ненадежные» позиции. Поскольку раскраска для листьев дерева вызовов предопределена функцией g, мы можем все дерево «раскрасить» по следующему правилу, которое соответствует принципу работы предписания sicher:

·

Позиция для а-ситуации окрашивается как надежная, если для р-ситуации существует следующая позиция, которая надежна для а и тем самым ненадежна для р; в противном случае эта позиция окрашивается как ненадежная.

·         Позиция для p-ситуации оценивается как надежная для а, если все непосредственно следующие позиции (которые будут использоваться уже в ос-ситуациях) являются надежными для а и тем самым ненaдежными для р.

Обратим внимание, что для нетерминальной позиции р справедливо высказывание

sicher(s, р) Û $ q Î Z(s, р): Øsicher(gegner(s), q). Через отрицание мы получаем:

·         Øsicher(s, р)



·          Û {вставка}

·         Ø$ q Î Z(s, р): -sicher(gegner(s), q)

·         Û { правило для отрицания квантора всеобщности}

·         " q Î

Z(s, р): sicher(gegner(s), q).

Итак, позиция является ненадежной, если все достижимые последующие являются надежными для партнера. Из предписания sicher путем замены квантора оператором цикла (for-оператора) тотчас можно получить рекурсивную программу, которая устанавливает, какие позиции являются надежными для игрока. Мы говорим о методе «сверху вниз», поскольку дерево вычислений проходится сверху, начиная с исходной позиции.

                                                                      a-ход

                                                                      b-ход

                                                                      a
-ход

                                                                      b-ход

Позиция выигрыша   Позиция проигрыша для a

Рис. 10.1.

Схематичное представление дерева вызовов

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

Здесь более эффективен метод «снизу вверх». При этом методе мы сначала раскрашиваем терминальные вершины на надежные и ненадежные. Затем последовательно по приведенным выше правилам раскрашиваются все вершины, для которых все их вершины-наследники уже раскрашены; это происходит по тем же правилам, что и в методе «сверху вниз».

Из предписания sicher получается также и оптимальная стратегия игры (так как она существует в рассматриваемом типе игры).


Метод может быть применен также и для шахматной игры. Впрочем, там число комбинаций столь велико, что этот алгоритм не может быть выполнен ни на одной машине мира.

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

fct opt == (player s, position p) int:

       if t(s, p)    then ge(s, p)

                 else max {-opt(gegner(p), q): q Î Z(s, p)}

fi

(Заметим, что

max{opt((gegner(p), q): q Î Z(s, p))} равно -mm{opt((gegner(p), q): q Î Z(s, p))}. - Ред,)

Пусть ge(s, p) есть выигрыш игрока s, если игра заканчивается в позиции р. Обратим внимание, что если х есть выигрыш одного из игроков, то «выигрыш» его партнера есть -х. При большом числе возможных комбинаций при игре этот алгоритм требует больших затрат ион неэффективен. Снова во многих случаях его эффективность можно повысить применением метода «снизу вверх».

Имеется, однако, еще один способ достичь повышения эффективности (а-p-отсечение). Он заключается в том, что если для ожидаемого выигрыша игрока sb позиции в нашем распоряжении имеется просто вычисляемая оценка maxopt(s, p) для верхней границы этого выигрыша, то можно обрезать (исключать из процесса их анализа) некоторые части дерева вызовов.

На рис.10.2 те части дерева, которые можно исключить из анализа (т. е. «обрезать»), выделены пунктирными ребрами.

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

opt(s, р) £ maxopt(s, р).                                              

      

       a                                                                    4                                                                                                                                                                                            

   b                        -4                    1                                     -1                           -3                                                      



   a            5                  4      6     -1      7                  3         1        5           6      4        3

   b     -5    0      1    -2      -4             2        -7                           -5        7        -1       -4

   a                                               -2        5

                           Рис.10.2  Пример для дерева вызовов с miniт структурой 

Для упрощения алглмитрического представления введём значения -? и ?. Пусть еint – тип целых чисел, расширенный этими двумя искусственными элементами. Примем соглашение о том, что

         max Æ = -¥,            min Æ = +¥

Теперь будем работать со следующим вычеслительным предписанием opt, реализующим a-b-отсечение:

fcp setopt = (player s, set position m, eint gr, eint min) eint:

       if maxopt(s, p) £ gr then gr

                                       else   -setopt(gegner(s), Z(s, p), -min, -gr);

           if a £ then gr

                     elif gr < a < min then setopt(s, m\{p},gr, a)

                                                else –setopt(s, m\{p},gr, min)

           fi

       fi

 

Дадим некоторые пояснения к этому предписанию.

1.      При каждом вызове setopt мы ищем min на слое при вычисленной на предыдущем слое границе gr этого значения.

2.      Значения gr и min всегда удовлетворяют порядку gr < min

3.      Начальное обращение к setopt производится с gr = -¥ и min = +¥

Обрезание какой-либо ветви или продолжение её обработки на некотором слое производится по следующему правилу:

·         a £ gr Þ gr                                                 (обрезание ветви)

·         gr < a < min Þ setopt(s, m\{p},gr, a)        (уточняется значение min)

·         min £ a Þ setopt(s, m\{p},gr, min)           (сохраняется значение min)



Имеет место

setopt(s, {р}, -¥, +¥) == opt(s, p).

С помощью этого инициирующего вызова мы получаем желаемый результат для игрока s в начальной позиции р.

Если вместо cint

возьмем тип bool

и заменим начальное значение gr == -¥ на gr == false, а начальное значение min = ¥ на значение true, то для решения проблемы выигрышной позиции в булевской постановке получим классический бэктрекинг с а-р-отсечением.

С помощью оценок maxopt(s, р) можно отсекать определенные ветви вычислений. В случае сложных игр эти оценки можно заменить более или менее грубыми приближениями. Мы получим «эвристики», -при применении которых результаты не будут уже корректными, а только приближенными.

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


Содержание раздела