5.16. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ

Развитие методов перебора на «И/ИЛИ» графах

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

В 60-х годах Слейджл и его сотрудники провели много экспериментов с различными стратегиями перебора для игровых деревьев и «И/ИЛИ» деревьев. Обзор стратегий для игровых деревьев содержится в статье Слейджла и Диксона (1969). В самой сложной из этих стратегий используется динамическое упорядочение раскрытия вершин. Программа Слейджла и

Бурского (1968), названная MULTIPLE (MULTIpurpose Program that LEarns), включает некоторую универсальную стратегию для перебора на «И/ИЛИ» графах. В этой стратегии используется понятие «вероятности того, что предположение верно», а затем определяется «функция качества», заданная на множестве открытых вершин дерева. Вершина, оказывающая наибольшее влияние на вероятность того, что первоначальное предположение верно, считается обладающей наиболее высоким «качеством». Последняя и выбирается для раскрытия.

Амарель (1967) предложил стратегию «контроля внимания» для упорядочения процесса раскрытий в «И/ИЛИ» дереве. Эта стратегия связана с попыткой найти решение минимальной стоимости. Автор этой книги (Нильсон, 1969) также предложил одну стратегию минимизации стоимости, и позже понял, что она по существу совпадает со стратегией Амареля. В работе Нильсона (1969) доказывается, что эта стратегия действительно позволяет найти решения минимальной стоимости. Это доказательство, так же как и доказательство, приведенное в настоящей главе, похоже на доказательство Харта, Нильсона и Рафаэля (1968) для графов в пространстве состояний. Стратегия Амареля — Нильсона мало отличается от метода динамического упорядочения Слейджла и Диксона. Описание алгоритма упорядоченного поиска, приведенное в настоящей главе, является просто попыткой дать достаточно ясное и общее представление об этой основной стратегии.

Развитие методов перебора на игровых деревьях

Клод Шеннон (1950) рассмотрел некоторые вопросы, относящиеся к созданию программ для машины, играющей в такие сложные игры, как шахматы. Он предложил применять минимаксную поисковую процедуру вместе со статической оценочной функцией. Ньюэлл, Шоу и Саймон (1958) использовали его идеи при конструировании первых программ для игры в шахматы. Им принадлежит также блестящий обзор этой области исследований. Дополнительное обсуждение программ для игры в шахматы вместе с «пятилетним планом работ» в области автоматической шахматной игры можно найти в статье Гуда (1968), содержащей также некоторые ссылки.

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

блестяще играет в шашки и выигрывает у всех, за исключением лишь очень сильных игроков. Она по-прежнему остается одним из лучших примеров применения методов искусственного интеллекта. Дальнейшая работа над этой программой описана в работе Сэмюэля (1967). Одной из особенностей самых последних вариантов программы Сэмюэля является динамическое упорядочение процедуры перебора, до некоторой степени похожее на упорядочение Слейджла и Диксона (1969).

Альфа-бета процедура обычно представляется довольно очевидным развитием минимаксного подхода и поэтому независимо «открывалась» рядом исследователей. Впервые она была описана Ньюэллом, Шоу и Саймоном (1958) и была предметом глубокого изучения, проведенного Маккарти и его учениками (Эдвардс и Харт, 1963) в Массачусетском технологическом институте. Существует несколько ясных изложений этого метода и его свойств. Хорошее его описание содержится во второй статье Сэмюэля (1967), посвященной игре в шашки, а также в статье Слейджла и Диксона (1969). Результаты, касающиеся эффективности перебора в альфа-бета процедуре, впервые были установлены Эдвардсом и Хартом (1963) на основе теоремы, которую они приписывают Михаэлу Левину. Позднее Слейджл и Диксон (1969) привели, как они полагают, первое опубликованное доказательство этой теоремы. Они рассмотрели несколько вариантов альфа-бета процедуры, в том числе (наилучший вариант) использование динамического упорядочения. Сравнение работы этих различных стратегий было проведено на примере старинной игры калах.

Наше исследование возможных усовершенствований методов, основанных на минимаксе, исходит из некоторых предложений Слейджла (19636) и Слейджла и Диксона (1970). В последней статье описываются эксперименты с «Программой перебора на деревьях M&N», в которой при вычислении обращенных величин добавляется (или вычитается) фиксированная величина.

Некоторые характерные игровые программы

Шахматы

Кистер и др. (1957) описали самую первую шахматную систему, запрограммированную на вычислительной машине (MANIAC I в Лос-Аламосе). В ней используется уменьшенная доска (), и ее игра представляется довольно бедной.

Бернштейн и др. (1958) описали шахматную систему, запрограммированную на машине IBM. Она также играет довольно плохо, но на доске обычных размеров ().

Ньюэлл, Шоу и Саймон (1958) дали другой пример ранней шахматной программы, разработанной в Карнеги.

Коток (1962) изложил первый вариант программы, составленной в Массачусетском технологическом институте, которая позже была взята Маккарти в Станфорд и слетка модифицирована. Она уже достигает уровня игры посредственного игрока.

Г. М. Адельсон-Вельский и др. (в нашем распоряжении нет их работы) написали программу в Институте теоретической и экспериментальной физики (Москва). Эта программа победила в турнире программу Котока-Маккарти. (См. SIGART Newsletter, № 4 (июнь 1967), стр. 11.)

Гринблатт и др. (1967) описали программу, составленную в Массачусетском технологическом институте, которая теперь называется Мэк Хак. Уровень ее игры можно охарактеризовать как уровень «среднелюбительский». Она является почетным членом Массачусетского шахматного общества и получила категорию С. Некоторое другие примеры игр содержатся в следующих выпусках SIGART Newsletter, № 6 (октябрь 1967), стр. 8 (здесь вычислительная машина выигрывает у X. Дрейфуса, который прежде выражал сомнение в том, что машина вообще способна выиграть у игрока-любителя); № 9 (апрель 1968), стр. 9—10, № 15 (апрель 1969), стр. 8—10; № 16 (июнь 1969), стр. 9—11.

Шашки

Сэмюэль (1959, 1967) продолжает усовершенствовать программу, которая великолепно играет в шашки, но не может нанести поражение чемпиону мира.

Калах

Первую программу для этой игры написал Рассел (1964).

Слейджл и Диксон (1969) описали эксперименты с использованием игры калах и (1970) результаты экспериментов, в которых калах используется для испытания «процедуры M&N».

(По-видимому, в игре калах человек неспособен выиграть у машины.)

Гоу

Зобрист (1969) написал программу для игры в старинную и трудную игру гоу. С точки зрения человека, эта программа играет довольно плохо и не производит перебора по дереву. Примеры работы программы Зобриста можно найти в SIGART Newsletter, № 18 (октябрь 1969), стр. 20—22.

Задачи

(см. скан)

(см. скан)