Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 69
Текст из файла (страница 69)
Но программа Тьюринга фактически никогда не эксплуатировалась на компьютере; она была испытана путем моделирования вручную в партии против очень слабого игрока-человека, который ее победил. Между тем, Д.Г. Принц )1238) написал и проверил на практике программу, которая решала шахматные задачи, но не могла вести полную игру. Первая программа', способная вести полную игру в стандартные шахматы, была написана Алексом Бернстейном [112), [113).
Джон Маккарти сформулировал идею альфа-бета-поиска в 1956 году, но не опубликовал свое открытие. В шахматной программе (и'88 [1128) используется упрощенная версия альфа-бета-поиска; она представляет собой первую шахматную программу, в которой было введено это усовершенствование.
По данным Нильссона [114!), в программе игры в шашки Артура Самюэла [1349], [1350] также использовался альфа-бета-поиск, хотя Самюэл об этом не упоминал в опубликованных отчетах о своей системе. Статьи с описанием альфа-бета-поиска были опубликованы в начале 1960-х годов [198], [625], )1427). Одна из реализаций полного альфа-бета- поиска описана Слаглем и Диксоном )1428] применительно к программе ведения игры калах.
Кроме того, альфа-бета-поиск использовался в шахматной программе "Ко(о1с — МсСаг()гу", написанной студентом Джоном Маккарти [847]. Кнут и Мур [8!О) изложили историю создания алгоритма альфа-бета-поиска, а также привели доказательство его правильности и представили результаты анализа временной сложности. Проведенный ими анализ альфа-бета-поиска со случайным упорядочиванием преемников показал его асимптотическую сложность 0( (Ы1одЬ)е), что представляло собой довольно мрачный прогноз, поскольку соответствующий ему эффективный коэффициент ветвления Ь71одЬ не намного меньше, чем само значение Ь.
После этого они отметили, что указанная асимптотическая формула является точной только для Ь>1000 или таких порядков величин, тогда как часто упоминаемое значение 0(Ь'"') относится к тому диапазону коэффициентов ветвления, который чаще всего встречается в настоящих играх. Перл [1187) показал, что альфа- бета-поиск является асимптотически оптимальным среди всех алгоритмов поиска в дереве игры на постоянную глубину.
В первом шахматном матче между компьютерами участвовала программа Ко(о(г— МсСаг((ту и программа "!ТЕР" (!па(!гд(е оГ Тйеоге(1са! апг) Ехрегппеп(а1 Р)туа(са), написанная в середине 1960-х годов в Московском институте теоретической и экспериментальной физики (ИТЕФ) [4]. Этот межконтинентальный матч проводился по телеграфу. Он закончился в 1967 году победой программы 1ТЕР со счетом 3:1. Первой шахматной программой, которая успешно соревновалась с людьми, была про- ' В !1128] упоминается программа, написанная в Советском Союзе для компьютера БЭСМ, которая могла предшествовать программе Бернстейна. Глава 6. Поиск в условиях противодействия 273 грамма МасНас[г 6 [594]. Ее рейтинг, примерно равный 1400, был намного выше 1000 — уровня начинающего, но все же далеко не достигал рейтинга 2800 или больше, который требовался для выполнения предсказания Герберта Саймона, высказанного в 1957 году, что компьютерная программа станет чемпионом мира по шахматам через 10 лет [1419].
Начиная с первого Североамериканского чемпионата АСМ по компьютерным шахматам, проведенного в 1970 году, между шахматными программами разгорелась серьезная конкуренция. Программы, разработанные в начале 1970-х годов, стали чрезвычайно сложными, насыщенными всевозможными ухищрениями, которые были предназначены для устранения некоторых ветвей поиска, выработки приемлемых ходов и тд.
В 1974 году в Стокгольме проводился первый чемпионат мира по компьютерным шахматам, в котором победила Кажа [5], еще одна программа, разработанная в ИТЕФ. В программе Ка!зза использовался гораздо более прямолинейный подход к организации исчерпывающего альфа-бета-поиска в сочетании с поиском спокойных позиций. Перспективность этого подхода была подтверждена убедительной победой программы С[зева 4.6 на чемпионате мира по компьютерным шахматам в 1977 году. Программа СЬезз 4.6 исследовала до 400 000 позиций за каждый ход и имела рейтинг 1900. Последняя версия разработанной Гринблаттом программы МасНас[г 6 была первой шахматной программой, которая эксплуатировалась на специализированном аппаратном обеспечении, разработанном специально для шахмат [1094], но первой программой, в которой удалось добиться заметного успеха благодаря использованию заказного аппаратного обеспечения, была программа Ве!!е [286]. Применявшееся в программе Ве11е аппаратное обеспечение для выработки ходов и оценки позиции позволяло ей исследовать несколько миллионов позиций за каждый ход.
Программа Ве!!е достигла рейтинга 2250 и стала первой программой уровня мастера. В университете СМ() бывшим чемпионом мира по игре в шахматы по переписке Хансом Берлинером и его студентом Карлом Эбелингом была разработана система Нйес[з, также представлявшая собой компьютер специального назначения, который обеспечивал быстрое вычисление функций оценки [428], [108]. Система Нйесй, которая вырабатывала около 10 миллионов позиций за ход, стала чемпионом Северной Америки по компьютерным шахматам в 1985 году и оказалась первой программой, которая смогла победить гроссмейстера-человека в ! 987 году.
Система плеер Тпоцйпг, которая также была разработана в университете СМП, явилась еще одним шагом в направлении чистого ускорения поиска [697]. Она достигла рейтинга 2551 и стала предшественником системы плеер В1це. В! 980 году была основана премия Фредкина (Егеб[г!и), в которой было предложено 5000 долларов за первую программу, достигшую уровня мастера, 10000 долларов за первую программу, достигшую рейтинга 2500 ()БСЕ ((Зш!ег) Бьзгез С[гезз Еедегаг!оп — Шахматная федерация США) (что примерно соответствует уровню гроссмейстера), и 100 000 долларов за первую программу, победившую чемпиона мира по шахматам. Премию 5000 долларов получила программа Ве1!е в 1983 году, премию 10 000 долларов — система Оеер Т(зоцйпг в 1989 году, а премию 100 000 долларов — система Реер В!ие за победу над Гарри Каспаровым в 1997 году. Необходимо учитывать, что успех Оеер В1ве бьп обусловлен не только усовершенствованием аппаратных средств, но и применением лучших алгоритмов [216], [696].
Применение таких методов, как эвристика нулевого хода [90], привело к созданию программ, которые стали весьма избирательными в своих поисках. В последних трех чемпионатах мира по компьютерным шахматам, проводив- 274 Часть 11. Решение проблем шихся в 1992, 1995 и 1999 годах, победили программы, работающие на стандартных персональных компьютерах. По-видимому, наиболее полное описание современной шахматной программы предоставлено Эрнстом Хейнцем ]644], чья программа Оаг[гТ[зоц8Ы получила самый высокий рейтинг среди некоммерческих программ для персональных компьютеров на чемпионате мира 1999 года.
Для преодоления проблем, связанных со "стандартным подходом", кратко описанных в разделе 6.7, было предпринято несколько попыток. По-видимому, первым избирательным алгоритмом поиска, в кагором учитывались некоторые теоретические обоснования методов сокрашения поиска, был В* ]105], в котором предпринята попытка устанавливать интервальные пределы возможных значений узла в дереве игры, а не давать единственную точечную оценку. Листовые узлы выбираются для развертывания в целях уточнения пределов верхнего уровня до тех пор, пока не обнаруживается ход, который "безусловно является наилучшим". Палей [!165] развил идею алгоритма В", используя распределения вероятностей значений вместо интервалов.
В алгоритме поиска конспиративного числа (сопзр1гасу пшпЬег зеагсп) Дэвида Маккаллестера [1004] предусмотрено развертывание листовых узлов, которые, изменяя свои значения, могут вынудить программу предпочесть новый ход от корня. В алгоритме МО88* [1331] используются описанныее в главе 16 методы теории решений для оценки стоимости развертывания каждого листа с точки зрения ожидаемого усовершенствования качества решения, формируемого от корня. Этот алгоритм превзошел альфа-бета-алгоритм, применяемый в игре "Отелло", несмотря на то, что в нем проводился поиск среди узлов, количество которых было на порядок меньше.
Вообще говоря, подход, принятый в алгоритме МО88*, может применяться для управления размышлениями в любой форме. Альфа-бета-поиск во многих отношениях представляет собой аналог поиска на основе метода ветвей и границ, который был превзойден поиском А' в случае с одним агентом, если не считать того, что альфа-бета-поиск рассчитан на двух игроков. Алгоритм 888" [1466] может рассматриваться как поиск А* для двух игроков; в нем лля достижения того же решения никогда не развертывается больше узлов, чем в алгоритме альфа-бета-поиска. В его первоначальной форме алгоритм 888* предьявлял чрезмерные требования к памяти и характеризовался значительными вычислительными издержками на сопровождение очереди, поэтому был практически не применимым.
Тем не менее на основе алгоритма КВРБ была разработана версия 888* с линейно возрастающими потребностями в пространстве [843]. Плат и др. ]1214] разработали новый подход к реализации алгоритма 888* как комбинации альфа-бета-поиска и таблиц транспозиции, показали, как преодолеть недостатки первоначального алгоритма, и создали новый вариант, называемый МТО((], который нашел свое применение во многих превосходных программах. Д.Ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
