Лекция 16. Игровые программы.

Игра в шахматы.

В шахматах существует 16 возможных направлений перемещений фигур. Фигура pможет перемещаться в каждом из разрешенных направлений на некоторое число шагов, максимум которого обозначим черезn pas max(p).Его величина зависит от вида фигуры.

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

ПОВТОРЯТЬ ДЛЯ ВСЕ полей (i,j) доски

| ЕСЛИ поле(i,j) занято своей фигурой

| | ТО

| | pфигура(i,j);

| | ПОВТОРЯТЬ ДЛЯ ВСЕХ направлений  [1, число направлений]

| | | ЕСЛИ направление  множество разрешенных направлений(p)

| | | | ТО

| | | | xi; yj

| | | | ПОВТОРЯТЬ ДЛЯ ВСЕХ шагов  [1, n pas max(p)]

| | | | | xx+dx; yy+dy

| | | | | ЕСЛИ (x,y)  в пределах доски И поле (x,y)  свое

| | | | | | ТО зарегистрировать ход: [(i,j)  (x,y)]

| | | | | КОНЕЦ ЕСЛИ

| | | | КОНЕЦ ПОВТОРЯТЬ

| | | КОНЕЦ ЕСЛИ

| | КОНЕЦ ПОВТОРЯТЬ

| КОНЕЦ ЕСЛИ

Конец повторять

Из приведенного выше ясно, что наиболее простой способ ограничения дерева заключается в ограничении глубины анализа числом 1. В этом случае необходимо: 1) найти все допустимые ходы; 2) оценить их; 3) сделать наилучший из оцененных ходов.

При этом возможных ход игры можно представит в виде:

ЕСЛИ существует выигрывающий ходрой

| ТО

| сделат его; конец;

| ИНАЧЕ

| рассмотреть другие разрешенные ходы;

| пусть с – следующий ход

| ЕСЛИ существует виыгрывающий ответ противника на ход с

| | ТО исключить ход с

| | ИНАЧЕ учесть возможных ответов противника после хода с

| КОНЕЦ ЕСЛИ

| сделать ход, на который противник имеет минимальное число ответных ходов

КОНЕЦ ЕСЛИ

Лекция 17. Интеллектуальные системы в Интернет

Пространство WWWуже сегодня содержит огромное количество НТМL-документов, причем не только тексты, но и графику, видео, звук и т. д. Гипертексто­вые связи между Web-документами и/или их частями отражают" отношения между отдельными информационными фрагментами, представленными в сети. Броузеры, поддерживающие HTML-стандарты, обеспечивают представление материалов пользователям и навигацию по ссылкам для доступа к документам, распределенным по сети. Однако поиск информации в настоящее время поддер­жан существенно слабее и в большинстве случаев базируется на использовании ключевых слов И ограниченного числа типов машин поиска.

Машины поиска.

Машины поиска, по-видимому, являются в Интернете самым распространенным и доступным ресурсом для извлечения информации. При этом, как правило, ис­пользуются два типа сетевых роботов: спайдеры (spiders) и индексы (indexes);

Спайдеры, иногда называемые также ботами (bots, от робот-robots), перемеша­ются поWebот сайта к сайту. Некоторые из них перемешаются от сервера к сер­веру беспорядочно, другие используют приоритеты, такие, например, как посе­щаемость сайта. Оказавшись на сайте, спайдер посылает отчет поисковой;

машине и продолжает индексирование. Индексы используются для ускорения поиска и сбора информации. Некоторые поисковые механизмы индексируют содержание страниц полностью, Другие — только отдельные ихчасти, такие, на­пример, как заголовки документов.

Основными характеристиками машин поиска являются языка запросов пользователя, представление исходных и выходных документов, время индексации и поиска, объем индекса. Существенной характеристикой машин поиска являет также качество представления результатов.

Как правило, поисковые машины обеспечивают интерфейс типа меню, с помощью которого пользователь может скомпоновать запрос на поиск информации используя ключевые слова и/или фразы и логические связки И-ИЛИ-НЕ. Большинство машин поиска находят огромное количество «релевантных» страниц запросу пользователя. Каждый найденный документ обычно ранжируется степени его корреляции с запросом. Релевантность каждого документа оценивается с помощью различных технологий, например учета частоты появления странице искомых слов. Некоторые поисковые механизмы используют дополнительно другие факторы, такие как частота посещения страницы и/или близость расположения друг к другу искомых терминов. Типичную организацию машин поиска можно рассмотреть на примере систем WebCrawler(рис. 17.1), разработанной в университете Вашингтон (Сиэтл, США).

Рис. 17.1. Общая архитектура системы WebCrawler

WebCrawlerначинает процесс поиска новых сайтов с известных ему документ и переходит по ссылкам на другие страницы. Он рассматривает сетевое пространство как ориентированный граф и использует алгоритм обхода графа, работая следующем цикле:

• найти новый документ;

• отметить документ как извлеченный:

- расшифровать ссылки с этого документа;

- проиндексировать содержание документа».

Поисковый механизм работает в двух режимах: поиск документов в реальном времени и индексирование документов.

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

Агенты в системе WebCrawlerотвечают за извлечение документов из сети. Для выполнения этой работы поисковый механизм находит свободного агента и пере­дает ему задание на поиск. Агент приступает к работе и возвращает либо содержа­ние документа, либо объяснение, почему данный документ нельзя доставить. Агенты запускаются как отдельные процессы, что позволяет изолировать основ­ной процесс работы системы от ошибок и проблем с памятью. Одновременно ис­пользуется до 15 агентов.

В базе данных хранятся метаданные документов, связи между документами, пол­нотекстовый индекс, другая служебная информация. База обновляется каждый раз, когда поступает новый документ. Для отсечения семантически незначимых слов используется стоп-словарь, словам из документа приписывается вес, рав­ный частоте их появления в данном тексте, деленной на частоту появления слова в ссылках на другие документы. Такой индекс позволяет быстро находить по за­данному слову ссылки на документы его содержащие. Целиком URL(ссылки на документы в сети) не запоминаются. Вместо этого вся нужная информация по­мещается в специальные объекты. Каждый объект запоминается в отдельномB-дереве: документы — в одном, серверы — в другом, а ссылки — в третьем. Такое разделение данных позволяет быстро определить неиспользуемые или часто ис­пользуемые серверы.

Аналогичным образом устроены и другие машины поиска. Характеризуя их в целом, можно отметить, что это глобальные поисковые механизмы, охватывающие до 90 % ресурсов Интернета. Они не могут настраиваться на предпочтения пользо­вателя и не имеют средств анализа информации, а их сетевым роботам становится все труднее справляться с постоянным ростом ресурсов Интернета. Главной зада­чей машин поиска, по сути, является индексация ресурсов глобальной сети, а так­же поддержка и расширение соответствующих баз данных. Фактически в базах данных машин поиска хранится информация о том, где и что лежит в сети. Поэто­му можно считать, что существующие машины поиска обеспечивают низкоуров­невый сервис для клиентских поисковых программ более высокого уровня.