Intel_Nils (526801), страница 33
Текст из файла (страница 33)
В этой стратегии используется понятие «вероятности того, что предположение верно», а затем определяется «функция качества», заданная на множестве открытых вершин дерева. Вершина, оказываюшая наибольшее влияние на вероятность того, что первоначальное предположение верно, считается обладаюшей наиболее высоким «качеством». Последняя и выбирается для раскрытия. Амарель (!967) предложил стратегию «контроля внимания» для упорядочения процесса раскрытий в «И!ИЛИ» дереве. Эта стратегия связана с попыткой найти решение минимальной стоимости. Автор этой книги (Нильсон, 1969) также предложил одну стратегию минимизации стоимости.
и позже понял, что она по существу совпадает со стратегией Амареля. В работе Нильсона (!969) доказывается, что эта стратегия действительно позволяет найти решения минимальной стоимости. Это доказа. тельство, так же как и доказательство, приведенное в настоящей главе, похоже на доказательство Харта, Нильсона и Рафаэля (1968) для графов в пространстве состояний.
Стратегия Амареля — Нильсона мало отличается от метода динамического упорядочения Слейджла и Диксона. Описание алгоритма упо рядоченного поиска, приведенное в настоящей главе, является просто попыткой дать достаточно ясное и общее представление об этой основной стратегии. Развитие методов перебора на игровых деревьях Клод Шеннон (1950) рассмотрел некоторые вопросы, относящиеся к созданию программ для машины, играющей в такие сложные игры, как шахматы. Он предложил применять минимаксную поисковую процедуру вместе со статической оценочной функцией. Ньюэлл, Шоу и Саймон (1958) использовали его идеи при конструировании первых программ для игры в шахматы.
Им принадлежит также блестящий обзор этой области исследований. Дополнительное обсуждение программ для игры в шахматы вместе с «пятилетним планом работ» в области автоматической шахматной игры можно найти в статье Гуда (1968), содержащей также некоторые ссылки. В 1959 г. Сэмюэль описал программу игры в шашки, в которой использовались полиномиальные оценочные функции, минимаксные методы перебора и различные стратегии «обучения», позволяющее совершенствовать игру '). Программа Сэмюэлн ') Позднее Сзмюзль отмечал (частное сообщение), что в его программе применяется также альфа-бета процедура, но в то время он полагал, что ее использование носит слишком очевидный характер, чтобы стоило включать ее в статью.
б.!б. Библиографические и исторические еоиечокия 169 блестяще играет в шашки и выигрывает у всех, за исключением лишь очень сильных игроков. Она по-прежнему остается одним из лучших примеров применения методов искусственного интеллекта. Дальнейшая работа над этой программой описана в работе Сэмюэля (1967). Одной из особенностей самых последних вариантов программы Сэмюэля является динамическое упорядочение процедуры перебора, до некоторой степени похожее на упорядочение Слейджла и Диксона (1969). Альфа-бета процедура обычно представляется довольно очевидным развитием минимаксного подхода и поэтому независимо «открывалась» рядом исследователей.
Впервые она была описана Ньюэллом, Шоу и Саймоном (1958) и была предметом глубокого изучения, проведенного Маккарти и его учениками (Эдвардс и Харт, 1963) в Массачусетском технологическом институте. Существует несколько ясных изложений этого метода и его свойств. Хорошее его описание содержится во второй ,статье Сэмюэля (!967), посвященной игре в шашки, а также в статье Слейджла и Диксона (1969). Результаты, касающиеся эффективности перебора в альфа-бета процедуре, впервые были установлены Эдвардсом и Хартом (1963) на основе теоремы, которую они приписывают Михаэлу Левину. Позднее Слейджл и Диксон (1969) привели, как они полагают, первое опублико.
ванное доказательство этой теоремы. Они рассмотрели несколько вариантов альфа-бета процедуры, в том числе (наилучшнй вариант) использование динамического упорядочения. Сравнение работы этих различных стратегий было проведено на примере старинной игры калах. Наше исследование возможных усовершенствований методов, основанных на минимаксе, исходит из некоторых предложений Слейджла (1963б) и Слейджла и Диксона (1970). В последней статье описываются эксперименты с «Программой перебора на деревьях МЬИ», в которой при вычислении обращенных величин добавляется (или вычитается) фиксированная величина. Некоторые характерные игровые программы Шахматы Кистер и др.
(!957) описали самую первую шахматную систему, запрограммированную на вычислительной машине (МАН1АС 1 в Лос=Аламосе). В ней используется уменьшенная доска (6 Х 6), и ее игра представляется довольно бедной. Бернштейн и др. (!958) описали шахматную систему, запрограммированную на машине !ВМ. Она также играет довольно плохо, но на доске обычных размеров (8 Х 8). Ньюэлл, Шоу н Саймон (1958) дали другой пример ранней шахматной программы, разработанной в Карнеги.
170 Гл. 5. Методы поиска при сведении задач к подзадачам Коток (1962) изложил первый вариант программы, составленной в Массачусетском технологическом институте, которая позже была взята Маккарти в Станфорд и слегка модифицирована. Она уже достигает уровня игры посредственного игрока. Г. М. Адельсон-Вельский и др. (в нашем распоряжении нет их работы')) написали программу в Институте теоретической и экспериментальной физики (Москва). Эта программа победила в турнире программу Котока — Маккарти.
(См. Б!ОАГсТ )ч)етуз1е1!ег, № 4 (июнь !967), стр. 11.) Гринблатт и др. (1967) описали программу, составленную в Массачусетском технологическом институте, которая теперь называется Мэк Хак. Уровень ее игры можно охарактеризовать как уровень «среднелюбительский». Она является почетным членом Массачусетского шахматного общества и получила категорию С. Некоторые другие примеры игр содержатся в следующих выпусках $1ОАЯТ )ч)ечез!е11ег, № 6 (октябрь 1967), стр.
8 (здес( вычислительная машина выигрывает у Х. Дрейфуса, который прежде выражал сомнение ~в том, что машина вообще способна выиграть у игрока-любителя); № 9 (апрель 1968), стр. 9 — 10, еч» 15 (апрель 1969), стр. 8 — 10; № 16 (июнь 1969), стр. 9 — ! 1. Шашки Сэмюэль (1959, 1967) продолжает усовершенствовать программу, которая великолепно играет в шашки, но не может нанести поражение чемпиону мира. Калах ') Первую программу для этой игры написал Рассел (1964). Слейджл и Диксон (1969) описали эксперименты с использованием игры калах и (1970) результаты экспериментов, в которых калах используется для испытания «процедуры Мйг)ч)». (По-видимому, в игре калах человек неспособен выиграть у машины.) Гоу Зобрист (1969) написал программу для игры в старинную и трудную игру гоу.
С точки зрения человека, эта программа играет довольно плохо и не производит перебора по дереву. Примеры работы программы Зобриста можно найти в 81ОАГсТ )ч)етнз!е!!ег, № 18(октябрь !969), стр. 20 — 22. Задачи 5.1. Прн проведеннн индукции в лемме 5.! мы получили доказательство для случая, когда дочерними вершинами начальной вершины являются «ИЛИ» вершины, н отметили, что подобные рассуждения можно прнменнть н тогда, ') См. статью Адельсона-Вельского н др., 1тМН, 25, вып.
2(152), (1970).— Прим. перев. е) См. примечание переводчика на стр. 166. — Прим. перев. 17! когда дочерними вершинами являются «И» вершины. Дайте доказательство лля этого случая, закончив, таким образом, доказательство леммы 5.! 5.2. (Для играющих в шахматы.) Возьмите какой-нибудь шахматный эндшпиль (скажем, из шахматного раздела газеты) и решите его, построив полное игровое дерево. Нарисуйте зто дерево перебора, указав все ходы, которые вы рассмотрели, и отметьте «И/ИЛИ» поддерево решения. Какие специфически шахматные эвристики вы использовали при построении дерева пере.
борз? *5.3. Постройте алгоритм упорядоченного перебора для «И/ИЛИ» графов (обобщив соответствующий алгоритм для деревьев, описанный в равд. 5.7). 5.4. Проведите альфа. бета перебор на игровом дереве, изображенном на рдс. 5.!4, строя в первую очередь самые. правые вершины. Укажите, где делаются отсечения, и сравните с. рис. 5.!4, на котором в первую очередь строились самые левые вершины. «5.5.
(Для программистов на языке ЫЯР.) Напишите на ЫБР функцию ЕЕАЕСН(БТАЙТ, ОЕРТН), которая строит игровое дерево, применяя построитель допустимых ходов на ЫЗР вида ЕЕОАЕБ (РОЯ!Т!ОМ) сначала к исходной позиции АСТАРТ, а затем к ее дочерним позициям и т. д. вплоть до некоторой максимальной глубины РЕРТН. (Предположите, что в позиции БТАЙТ ходит игрок ПЛЮС, а затем ходы чередуютсн.) Функция БЕАЙСН должна применять статическую оценочную функцию ЧАЕ (Р08!Т10Н) к вершинам с глубиной, равной ОЕРТН, и производить альфа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
