Cтраница 4
Одна из тем исследований игровых программ в основном была связана с улучшением представления - - шахматной доски и процессов ходов на этой доске с целью ускорить поиск и сделать возможным поиск на деревьях больших размеров. Мотивация этого направления, конечно, та, что чем глубже динамический поиск, тем точнее будут оценки, которые его завершают. Эта экономия достигается не столько за счет меньшей по сравнению с шахматными программами глубины поиска, сколько за счет очень редкого и избирательного ветвления в каждой вершине. Без ухудшения качества оценок это возможно лишь при встраивании большей избирательности в; сам генератор, чтобы он мог выбирать для порождения лишь те ветви, которые с очень высокой вероятностью дадут важную и нужную информацию о качестве позиции. [46]
Например, попытки научить современные машины хорошо играть в шахматы, используя метод просмотра всех ветвей дерева игры на несколько ходов вперед, оказались непрактичными. По-видимому, вместо этого необходимо снабдить машины эвристическими методами, позволяющими выбирать ход из ограниченного числа ходов, заслуживающих внимания, а первоначальную цель нахождения наилучшей позиции заменить некоторой более специальной тактической подцелью. Работающие над этой проблемой, наверное, чувствуют, что наиболее перспективными являются шахматные программы, которые просматривают лишь несколько сотен возможных позиций и производят достаточно тщательный анализ избранных ходов. [47]
Можно ли создать алгоритмы, сложность которых была бы сравнима со сложностью рассуждений шахматиста. Нет необходимости, чтобы они играли точно таким же образом: копирование действий человека вовсе не есть наша непосредственная задача. Но мы утверждаем, что сложность - это существенная характеристика умственной деятельности и что сложность удачной шахматной программы должна приближаться к сложности мыслительных процессов опытного шахматиста. Сложность решения диктуется сложностью задачи, а не какими-то особыми свойствами человеческого мозга. [48]
В этот основной словарь входит около 100 терминов. Собственно шахматная программа, как видно из этой статьи, широко использует термины шахматного словаря. Таким образом, в программе имеются четыре языковых уровня: машинный код JOHNNIAC, обычный IPL, основной шахматный словарь и собственно шахматная программа. [49]
Для игр, представляющих интерес, деревья возможных продолжений слишком велики, чтобы можно было говорить о полном переборе, поэтому необходимы какие-то другие подходы. Один из таких методов, основанный на минимаксном принципе, имеет эффективную реализацию, известную под названием альфа-бета алгоритм. В дополнение к этому стандартному методу, мы разработаем в этой главе программу на основе Языка Советов ( Advice Language), который дает возможность вносить в шахматную программу знания о типовых ситуациях. Этот довольно подробный пример может послужить еще одной иллюстрацией того, насколько хорошо Пролог приспособлен для реализации систем, основанных на знаниях. [50]
Сердцевину программы образует детерминированный генератор гипотез. Этот генератор работает на основе предложенного Лидербергом алгоритма Дендрал, обеспечивающего воспроизведение всех топологических возможных изомеров для данной химической формулы. По сути дела этот генератор представляет собой тополога, не располагающего какими-либо химическими сведениями, за исключением валентности атомов; сам алгоритм, однако, гарантирует полноту пространства гипотез подобно тому, как это делает генератор допустимых ходов в шахматной программе. Так как в основе процесса генерации лежит комбинаторная процедура, для всех молекул, кроме самых простейших, предлагается огромное количество структур, возможных топологически, но маловероятных с точки зрения химических реальностей. Процесс генерации предполагает существование некоторого дерева Потенциальных гипотез. Присутствие всех атомов, не объединенных в какую-либо структуру, соответствует вершине дерева, концевым же точкам соответствуют только полные структуры и отсутствие нелокализованных атомов. Каждая из промежуточных вершин дерева определяет некоторую часть структуры и группу атомов, которая осталась нелокализованной. [51]