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


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


·          Û {вставка}

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

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

·         " q Î

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

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

                                                                      a-ход

 


                                                                      b-ход

 


                                                                      a

-ход

 


                                                                      b-ход

 


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

Рис. 10.1.

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

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

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

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


Начало  Назад  Вперед



Книжный магазин