Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 67
Текст из файла (страница 67)
Поиск в условиях противодействия 265 секунду. Эта программа формировала вплоть до 30 миллиардов позиций в расчете на каждый ход, обычно достигая глубины поиска 14. Основой этой программы является стандартный альфа-бета-поиск с итеративным углублением на основе таблицы транспозиций, но ключом к успеху этой программы, по-видимому, стала ее способность вырабатывать расширения, выходящие за пределы глубины поиска для достаточно интересных линий форсирующих/форсированных ходов.
В некоторых случаях этот поиск достигал глубины в 40 полуходов. Функция оценки охватывала свыше 8000 характеристик, причем многие из них описывали в высшей степени специфичные шаблоны расположения фигур. Использовался справочник дебютов, состояший примерно из 4000 позиций, а также база данных с 700 000 игр гроссмейстеров, из которой программа могла извлекать согласованные рекомендации. Кроме того, в этой системе применялась большая база данных эндшпилей, состоящая из позиций с решениями, в которой содержались все позиции с пятью фигурами и многие позиции с шестью фигурами.
Использование этой базы данных привело к значительному увеличению эффективной глубины поиска, что позволило программе Реер В!це в некоторых случаях играть идеально даже за много ходов до мата. Успех программы Реер В1це укрепил и без того широко распространенное мнение, что прогресс в области ведения компьютерных игр достигается главным образом за счет все более мощного аппаратного обеспечения; к тому же распространение таких взглядов стимулировалось компанией 1ВМ. Создатели программы Реер В!ие, с другой стороны, утверждают, что важную роль сыграло также расширение поиска и применение продуманной функции оценки !216!. Более того, нам известно, что некоторые новейшие алгоритмические усовершенствования позволяют программам, работающим на стандартных персональных компьютерах, побеждать на каждом мировом чемпионате по компьютерным шахматам с 1992 года и часто наносить поражение противникам с массовой параллельной архитектурой, способным выполнять поиск в 1000 раз большего количества узлов в секунду.
Для сокращения эффективного коэффициента ветвления меньше чем до 3 (по сравнению с фактическим коэффициентом ветвления, составляюшим около 35) применяются всевозможные эвристики отсечения. Наиболее важной из них является эвристика с 'ъ пустым холом, в которой вырабатывается хороший нижний предел значения позиции с использованием поверхностного поиска, в котором противнику в начале игры разрешается сделать ход дважды.
Этот нижний предел часто позволяет выполнять альфа- бета-отсечение без затрат на полный поиск в глубину. Является также важным метод Ж отсечения ненужных ходов, который позволяет решить заранее, какие ходы вызовут альфа-бета-отсечение в узлах-преемниках. Группа разработчиков Реер В!це отказалась воспользоваться шансом провести матч-реванш, предложенный Каспаровым. Вместо этого в одном из самых последних крупных соревнований в 2002 году против чемпиона мира Владимира Крамника выступила программа Бг!рк Матч из восьми игр окончился ничьей. Условия этого матча были гораздо более благоприятными для человека, и в качестве аппаратного обеспечения использовался обычный персональный компьютер, а не суперкомпьютер.
Тем не менее Крамник прокомментировал этот матч так: "Теперь очевидно, что эта самая лучшая программа и чемпион мира играют примерно на равных". 'ж Шашки. Начиная с 1952 года Артур Самюэл из компании 1ВМ в свое свободное время занимался разработкой программы игры в шашки, которая совершенствовала с помощью обучения свою собственную функцию оценки, играя сама с собой 266 Часть П. Решение проблем тысячи раз. Эта идея будет описана более подробно в главе 21. Программа Самюэла вначале играла на уровне новичка, но всего лишь через несколько дней игры с самой собой усовершенствовалась до такого уровня, что стала побеждать Самюэла (хотя он не был сильным игроком). В 1962 году эта программа победила Роберта Нили, чемпиона игры в шашки "вслепую", благодаря ошибке с его стороны. Многие в то время посчитали, что компьютеры уже играют в шашки лучше людей, но фактически этого еше не произошло.
Тем не менее, если учесть то, что вычислительное оборудование, использовавшееся Самюэлом (компьютер 1ВМ 704), имело 10000 слов основной памяти, магнитную ленту для долговременного хранения и процессор с частотой 0,000001 ГГц, эта победа остается большим достижением. Превзойти данное достижение пытались многие, и, наконец, Джонатан Шеффер со своими коллегами разработал программу СЫпоо[г, которая работает на обычных персональных компьютерах и использует альфа-бета-поиск.
В программе СЫпоо]г применяется заранее вычисленная база данных из всех 444 миллиардов позиций с восьмью или меньшим количеством шашек на доске, что позволяет ей играть в эндшпиле безошибочно. Программа СЫпоо[г заняла второе место в 1990 году на открытом чемпионате США и завоевала право сделать заявку на участие в мировом чемпионате. Но затем эта программа столкнулась с проблемой в лице Мэриона Тинсли. Доктор Тинсли был чемпионом мира свыше 40 лет, проиграв за все это время только три партии. В первом матче против программы СЫпоо[г Тинсли потерпел свое четвертое и пятое поражение, но выиграл матч со счетом 20,5 — 18,5.
Матч на звание чемпионата мира в августе 1994 года между Тинсли и программой СЫпоой закончился преждевременно, поскольку Тинсли был вынужден сдаться из-за ухудшения состояния здоровья. Программа СЫпоо]г была официально признана чемпионом мира. Шеффер считает, что при наличии достаточной вычислительной мощи база данных с эндшпилями может быть увеличена до такой степени, что прямой поиск из начальной позиции будет всегда достигать решенных позиций, т.е.
задача игры в шашки должна быть полностью решена. (Программа СЫпоо[г иногда объявляла о своем выигрыше на пятом ходу.) Исчерпывающий анализ такого рода может быть выполнен вручную для игры в крестики-нолики ЗхЗ и с помошью компьютера для игр ОиЬ[с (объемные крестики-нолики 4х4х4), гомоку (пять в ряд) и %пе-Меп'з Могпз (Мельница) [524[. В замечательной работе Кена Томпсона и Льюиса Стиллера [1464] приведены решения всех шахматных эндшпилей с пятью фигурами и некоторых эндшпилей с шестью фигурами, причем эти результаты предоставлены для всеобщего доступа в 1пгегпек Стиллер обнаружил один вариант, в котором достигался форсированный мат, но он состоял из 262 ходов; этот результат вызвал некоторый переполох, поскольку в шахматных правилах установлено, чтобы в течение 50 ходов происходил хоть какой-то "прогресс", иначе засчитывается ничья.
Игра еь "Отелло", называемая также "Реверси", по-видимому, более популярна как компьютерная игра, а не настольная. Она имеет меньшее пространство поиска, чем шахматы, поскольку в ней обычно имеется от 5 до 15 допустимых ходов, но опыт в оценке позиций в ней пришлось накапливать буквально с нуля. В 1997 году программа [.ой!зГе!1о [209] победила человека — чемпиона мира, Такеси Мураками, со счетом 6;О.
Теперь общепризнано, что люди не могут соревноваться с компьютерами в игре "Отелло". 'в. Нарды. В разделе 6.5 описано, почему из-за включения элемента неопределенности, вызванного метанием жребия, глубокий поиск становится дорогостоящей Глава 6. Поиск в условиях противодействия 267 роскошью. В области игры в нарды было предпринято много усилий по усовершенствованию функции оценки.
Гэри Тесауро «1499«использовал сочетание метода обучения с подкреплением Самюэла и методов нейронных сетей (глава 20) для разработки удивительно точного средства оценки, которое использовалось при поиске на глубину 2 или 3. Сыграв против самой себя больше миллиона тренировочных игр, разработанная Гэри Тесауро программа ТР-Сапппоп по праву заняла место среди лучших трех игроков мира. Некоторые рекомендации этой программы по выбору дебютных ходов в начальной стадии игры в нарды радикально расходились с "мудрыми" советами, передававшимися из поколения в поколение в течение многих веков. 'дх Го — это наиболее популярная настольная игра в Азии, которая для полного овладения мастерством требует от профессионалов столько же усилий, как шахматы.
Поскольку в ней доска имеет размеры 19х19, коэффициент ветвления начинается с 361, а эта величина слишком обременительна для обычных методов поиска. Вплоть до 1997 года вообще не было ни одной достаточно компетентной программы, но теперь программы часто делают холы, достойные уважения. В большинстве наилучших программ сочетаются методы распознавания шаблонов (в которых используется принцип — при появлении такого-то шаблона из камней необходимо рассмотреть такой-то ход) с ограниченным поиском (для выработки решения о том, следует ли стремиться к захвату таких-то камней, не выходя за пределы данной локальной области).
Ко времени написания ланной книги, по-видимому, самыми сильными программами были Соеша1е Чен Жишинга и Оо4++ Майкла Рейса, каждая из которых достигает рейтинга, примерно равного 10 кю (уровень слабого любителя). Ведение игры го — это такая область, которая, скорее всего, достигнет развития в результате интенсивных исследований с использованием более сложных методов формирования рассуждений. Успех может быть достигнут в результате обнаружения способов интеграции нескольких линий локальных рассуждений о каждой из многих слабо связанных "субигр", на которые может быть выполнена декомпозиция всей игры го. Подобные методы имели бы колоссальную ценность для всех интеллектуальных систем в целом. Ъ.
Бридж — это игра с неполной информацией: карты любого игрока скрыты от других игроков. Кроме того, бридж — это игра с несколькими игроками, в которой участвуют четыре игрока, а не два, хотя игроки разбиты по парам на две команды. Как было показано в разделе 6.5, оптимальная игра в бридж может включать элементы сбора информации, передачи информации, введения в заблуждение и тщательного взвешивания вероятностей. Многие из этих методов используются в программе ВгЫяе Вагоп™ «1441«, которая выиграла в 1997 году чемпионат мира по бриджу среди компьютеров.
Хотя программа ВгЫяе Вагоп не играет оптимальным образом, она представляет собой одну из немногих успешно действующих систем ведения игры, в которой используются сложные, иерархические планы (см, главу 12), основанные на таких идеях высокого уровня, как импас (блеза«пя) и сквиз (зг)иеех)пя), которые знакомы игрокам в бридж. Чемпионат мира 2000 года с большим отрывом от соперников выиграла программа О1В [559«. В программе б! В используется метод "усреднения по прогнозам" с двумя важными модификациями. Во-первых, в этой программе вместо исследования того, насколько удачным окажется каждый вариант игры по отношению к каждому варианту возможного расположения скрытых карт (количество которых может достигать 10 миллионов), исследуется случайно выбранный образец из 100 располо- 268 Часть П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
