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


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


                        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, р)




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



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