БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Ранняя история развития механических средств ведения игр была запятнана многочисленными случаями мошенничества. Наиболее известным из них был "Турок" барона Вольфганга фон Кемпелена (1734—1804). Это устройство выдавали за автомат для игры в шахматы и смогли с его помощью обмануть очень многих, в том числе Наполеона. Лишь в дальнейшем выяснилось, что это устройство представляет собой хитроумный ящик фокусника, в котором сидит человек, хорошо играющий в шахматы [919]. Игры с участием этого устройства проводились с 1769 по 1854 годы. В 1846 году Чарльз Бэббидж (который был в восторге от "Турка") участвовал в одной из первых серьезных дискуссий на тему осуществимости задачи ведения игр в шахматы и шашки с помощью вычислительного устройства [1089]. Он также спроектировал, но не построил машину специального назначения для игры в крестики-нолики. Первая настоящая машина для ведения игры была построена примерно в 1890 году испанским инженером Леонардо Торресом и Кеведо. Она была специально предназначена для ведения шахматного эндшпиля "KRK" (King and Rook vs. King — король и ладья против короля) и гарантировала победу из любой позиции в игре с этими тремя фигурами.
В качестве первоисточника идеи алгоритма минимаксного поиска часто называют статью, опубликованную в 1912 году Эрнстом Цермело, основоположником современной теории множеств [1642]. К сожалению, эта статья содержала несколько ошибок, а алгоритм минимаксного поиска не был в ней описан правильно. Солидный фундамент теории игр был создан в оригинальной работе Theory of Games and Economic Behavior [1546], которая содержала анализ, показывающий, что для некоторых игр требуются стратегии, которые являются рандомизированными (или становятся непредсказуемыми для противников по каким-то иным причинам). Дополнительная информация на эту тему приведена в главе 17.
На заре компьютерной эры возможность создания компьютерных шахмат интересовала многих важных деятелей в этой области. Конрад Цузе [1651] (первый, кто спроектировал программируемый компьютер) разработал довольно подробные предложения, касающиеся того, как может быть решена эта задача. Во влиятельной книге Cybernetics {Кибернетика) Норберта Винера [1589] обсуждался один возможныйпроект создания шахматной программы и были высказаны идеи минимаксного поиска, останова на заданной глубине и применения функций оценки. Клод Шеннон [1395] изложил основные принципы создания современных программ ведения игр гораздо более подробно, чем Винер. Он ввел понятие поиска спокойной позиции, а также высказал некоторые идеи в отношении избирательного (неисчерпывающего) поиска в дереве игры. Слейтор [1430] и комментаторы его статьи также рассматривали возможности ведения игры в шахматы с помощью компьютера. В частности, Гуд [574] разработал понятие спокойной позиции независимо от Шеннона.
В 1951 году Алан Тьюринг написал первую компьютерную программу, способную вести полную игру в шахматы [1521]. Но программа Тьюринга фактически никогда не эксплуатировалась на компьютере; она была испытана путем моделирования вручную в партии против очень слабого игрока-человека, который ее победил. Между тем, Д. Г. Принц [1238] написал и проверил на практике программу, которая решала шахматные задачи, но не могла вести полную игру. Первая программа3, способная вести полную игру в стандартные шахматы, была написана Алексом Бернстейном [112], [113].
Джон Маккарти сформулировал идею альфа-бета-поиска в 1956 году, но не опубликовал свое открытие. В шахматной программе NSS [1128] используется упрощенная версия альфа-бета-поиска; она представляет собой первую шахматную программу, в которой было введено это усовершенствование. По данным Нильссона [1141], в программе игры в шашки Артура Самюэла [1349], [1350] также использовался альфа-бета-поиск, хотя Самюэл об этом не упоминал в опубликованных отчетах о своей системе. Статьи с описанием альфа-бета-поиска были опубликованы вначале 1960-х годов [198], [625], [1427]. Одна из реализаций полного альфа-бета-поиска описана Слаглем и Диксоном [1428] применительно к программе ведения игры калах. Кроме того, альфа-бета-поиск использовался в шахматной программе "Kotok-McCarthy", написанной студентом Джоном Маккарти [847]. Кнут и Мур [810] изложили историю создания алгоритма альфа-бета-поиска, а также привели доказательство его правильности и представили результаты анализа временной сложности. Проведенный ими анализ альфа-бета-поиска со случайным упорядочиванием преемников показал его асимптотическую сложность 0( (b/logb)d), что представляло собой довольно мрачный прогноз, поскольку соответствующий ему эффективный коэффициент ветвления b/logb не намного меньше, чем само значение Ь. После этого они отметили, что указанная асимптотическая формула является точной только для Ь>10 0 0 или таких порядков величин, тогда как часто упоминаемое значение 0(b3d/4) относится к тому диапазону коэффициентов ветвления, который чаще всего встречается в настоящих играх. Перл [1187] показал, что альфа-бета-поиск является асимптотически оптимальным среди всех алгоритмов поиска в дереве игры на постоянную глубину.
В первом шахматном матче между компьютерами участвовала программа Kotok-McCarthy и программа "ITEP" (Institute of Theoretical and Experimental Physics), написанная в середине 1960-х годов в Московском институте теоретической и экспериментальной физики (ИТЕФ) [4]. Этот межконтинентальный матч проводился по телеграфу. Он закончился в 1967 году победой программы ITEP со счетом 3:1. Первой шахматной программой, которая успешно соревновалась с людьми, была программа МасНаск 6 [594]. Ее рейтинг, примерно равный 1400, был намного выше 1000 — уровня начинающего, но все же далеко не достигал рейтинга 2800 или больше, который требовался для выполнения предсказания Герберта Саймона, высказанного в 1957 году, что компьютерная программа станет чемпионом мира по шахматам через 10 лет [1419].
Начиная с первого Североамериканского чемпионата АСМ по компьютерным шахматам, проведенного в 1970 году, между шахматными программами разгорелась серьезная конкуренция. Программы, разработанные в начале 1970-х годов, стали чрезвычайно сложными, насыщенными всевозможными ухищрениями, которые были предназначены для устранения некоторых ветвей поиска, выработки приемлемых ходов и т.д. В 1974 году в Стокгольме проводился первый чемпионат мира по компьютерным шахматам, в котором победила Kaissa [5], еще одна программа, разработанная в ИТЕФ. В программе Kaissa использовался гораздо более прямолинейный подход к организации исчерпывающего альфа-бета-поиска в сочетании с поиском спокойных позиций. Перспективность этого подхода была подтверждена убедительной победой программы Chess 4.6 на чемпионате мира по компьютерным шахматам в 1977 году. Программа Chess 4.6 исследовала до 400 000 позиций за каждый ход и имела рейтинг 1900.
Последняя версия разработанной Гринблаттом программы МасНаск 6 была первой шахматной программой, которая эксплуатировалась на специализированном аппаратном обеспечении, разработанном специально для шахмат [1094], но первой программой, в которой удалось добиться заметного успеха благодаря использованию заказного аппаратного обеспечения, была программа Belle [286]. Применявшееся в программе Belle аппаратное обеспечение для выработки ходов и оценки позиции позволяло ей исследовать несколько миллионов позиций за каждый ход. Программа Belle достигла рейтинга 2250 и стала первой программой уровня мастера. В университете CMU бывшим чемпионом мира по игре в шахматы по переписке Хансом Берлинером и его студентом Карлом Эбелингом была разработана система Hitech, также представлявшая собой компьютер специального назначения, который обеспечивал быстрое вычисление функций оценки [428], [108]. Система Hitech, которая вырабатывала около 10 миллионов позиций за ход, стала чемпионом Северной Америки по компьютерным шахматам в 1985 году и оказалась первой программой, которая смогла победить гроссмейстера-человека в 1987 году. Система Deep Thought, которая также была разработана в университете CMU, явилась еще одним шагом в направлении чистого ускорения поиска [697]. Она достигла рейтинга 2551 и стала предшественником системы Deep Blue. В 1980 году была основана премия Фредкина (Fredkin), в которой было предложено 5000 долларов за первую программу, достигшую уровня мастера, 10 000 долларов за первую программу, достигшую рейтинга 2500 USCF (United States Chess Federation — Шахматная федерация США) (что примерно соответствует уровню гроссмейстера), и 100 000 долларов за первую программу, победившую чемпиона мира по шахматам. Премию 5000 долларов получила программа Belle в 1983 году, премию 10 000 долларов — система Deep Thought в 1989 году, а премию 100 000 долларов — система Deep Blue за победу над Гарри Каспаро-вым в 1997 году. Необходимо учитывать, что успех Deep Blue был обусловлен не только усовершенствованием аппаратных средств, но и применением лучших алгоритмов [216], [696]. Применение таких методов, как эвристика нулевого хода [90], привело к созданию программ, которые стали весьма избирательными в своих поисках. В последних трех чемпионатах мира по компьютерным шахматам, проводившихся в 1992, 1995 и 1999 годах, победили программы, работающие на стандартных персональных компьютерах. По-видимому, наиболее полное описание современной шахматной программы предоставлено Эрнстом Хейнцем [644], чья программа DarkThought получила самый высокий рейтинг среди некоммерческих программ для персональных компьютеров на чемпионате мира 1999 года.
Для преодоления проблем, связанных со "стандартным подходом", кратко описанных в разделе 6.7, было предпринято несколько попыток. По-видимому, первым избирательным алгоритмом поиска, в котором учитывались некоторые теоретические обоснования методов сокращения поиска, был В* [105], в котором предпринята попытка устанавливать интервальные пределы возможных значений узла в дереве игры, а не давать единственную точечную оценку. Листовые узлы выбираются для развертывания в целях уточнения пределов верхнего уровня до тех пор, пока не обнаруживается ход, который "безусловно является наилучшим". Палей [1165] развил идею алгоритма В*, используя распределения вероятностей значений вместо интервалов. В алгоритме поиска конспиративного числа (conspiracy number search) Дэвида Маккаллестера [1004] предусмотрено развертывание листовых узлов, которые, изменяя свои значения, могут вынудить программу предпочесть новый ход от корня. В алгоритме MGSS* [1331] используются описанные в главе 16 методы теории решений для оценки стоимости развертывания каждого листа с точки зрения ожидаемого усовершенствования качества решения, формируемого от корня. Этот алгоритм превзошел альфа-бета-алгоритм, применяемый в игре "Отелло", несмотря на то, что в нем проводился поиск среди узлов, количество которых было на порядок меньше. Вообще говоря, подход, принятый в алгоритме MGSS*, может применяться для управления размышлениями в любой форме.
Альфа-бета-поиск во многих отношениях представляет собой аналог поиска на основе метода ветвей и границ, который был превзойден поиском А* в случае с одним агентом, если не считать того, что альфа-бета-поиск рассчитан на двух игроков. Алгоритм SSS* [1466] может рассматриваться как поиск А* для двух игроков; в нем для достижения того же решения никогда не развертывается больше узлов, чем в алгоритме альфа-бета-поиска. В его первоначальной форме алгоритм SSS* предъявлял чрезмерные требования к памяти и характеризовался значительными вычислительными издержками на сопровождение очереди, поэтому был практически не применимым. Тем не менее на основе алгоритма RBFS была разработана версия SSS* с линейно возрастающими потребностями в пространстве [843]. Плат и др. [1214] разработали новый подход к реализации алгоритма SSS* как комбинации альфа-бета-поиска и таблиц транспозиции, показали, как преодолеть недостатки первоначального алгоритма, и создали новый вариант, называемый MTD(f), который нашел свое применение во многих превосходных программах.
Д.Ф. Бил [89] и Дана Hay [1113], [1114] изучали недостатки минимаксного поиска, касающиеся приближенных оценок. Они показали, что при некоторых предположениях о независимости распределения листовых значений в дереве применение минимаксного поиска может привести к получению таких значений для корня, которые фактически являются менее надежными, чем полученные с помощью непосредственного использования самой функции оценки. В книге Перла Heuristics [1188] дано частичное объяснение этого кажущегося парадокса и приведен анализ многих алгоритмов ведения игр. Баум и Смит [83] предложили заменить алгоритм минимаксного поиска алгоритмом, основанном на учете вероятностей, и показали, что он приводит к осуществлению лучших вариантов выбора в некоторых играх.
Но объем теоретических результатов исследования влияния останова поиска на разных уровнях и применения функций оценки все еще остается недостаточным.
Алгоритм поиска на основе ожидаемого минимаксного значения был предложен Дональдом Мичи [1043], хотя, безусловно, он непосредственно следует из принципов оценки дерева игры, выдвинутых фон Нейманом и Моргенштерном. Брюс Бол-лард [65] распространил метод альфа-бета-отсечения на деревья с узлами жеребьевки. Первый успешно действующей программой игры в нарды была разработанная Берлинером программа BKG [104], [107]; в ней использовалась сложная, сконструированная вручную функция оценки, а поиск осуществлялся только на глубину 1. Это была первая программа, которая смогла победить чемпиона мира — человека в одной из основных классических игр [106]. По завершении соревнований Берлинер сразу же объявил, что это был очень короткий показательный матч (а не матч чемпионата мира) и что программе BKG очень повезло со жребием. Работа Герри Тесауро, приведшая вначале к созданию программы Neurogammon [1498], а затем TD-Gammon [1500], показала, что гораздо лучшие результаты могут быть достигнуты с помощью обучения с подкреплением. Эта тема будет рассматриваться более подробно в главе 21.
Первой из классических игр, полное решение которой было найдено компьютером, оказались не шахматы, а шашки. Кристофер Стрейчи [1469] написал первую работоспособную программу игры в шашки. Шеффер [1357] составил очень доступный отчет о разработке программы Chinook, ставшей чемпионом мира по шашкам, в котором все факты изложены "без прикрас".
Первые программы для игры го были разработаны немного позднее по сравнению с программами для шашек и шахмат [906], [1281], а их развитие происходило более медленно. Райдер [1334] использовал подход, основанный исключительно на использовании поиска в сочетании с всевозможными методами избирательного отсечения для преодоления колоссального коэффициента ветвления, характерного для этой игры. Зобрист [1650] применил правила "условие—действие", которые способны предложить приемлемые ходы при обнаружении известных шаблонов. Рейтман иУилкокс [1280] добились хороших результатов, сочетая применение правил и поиска, поэтому большинство современных программ было разработано на основе этого гибридного подхода. Мюллер [1103] подытожил современное состояние работы в области компьютеризации игры го и привел в своей книге много ссылок. Анше-левич [33] использовал подобные методы для создания программы для игры гекс. Описания современных разработок можно найти в журнале Computer Go Newsletter, который публикует организация Computer Go Association.
Работы по компьютерному ведению игры появляются во многих разных источниках. В трудах конференции Heuristic Programming in Artificial Intelligence, имеющей довольно дезориентирующее название, публикуются отчеты о компьютерных олимпиадах, в рамках которых проводятся весьма разнообразные игры. Имеется также несколько отредактированных сборников важных статей об исследованиях в области ведения игр [920], [921], [988]. Международная ассоциация компьютерных шахмат (International Computer Chess Association — ICCA), основанная в 1977 году, публикует ежеквартальный журнал ICGA Journal (который раньше носил название ICCA Journal). В серийно выпускаемой антологии Advances in Computer Chess публикуются важные статьи, начиная со статьи Кларке [268]. В томе 134 журнала Artificial Intelligence (2002) содержатся описания современных программ для шахмат, "Отелло", гекса, сёги (японские шахматы), го, нард, покера, Scrabble™ ("Эрудит") и др.