СОВРЕМЕННЫЕ ИГРОВЫЕ ПРОГРАММЫ

Публичная демонстрация программ ведения игр представляет собой для искусственного интеллекта примерно то же, что и участие в автогонках международного масштаба для автомобильной промышленности — суперсовременные игровые программы действуют поразительно быстро, чрезвычайно тщательно настроенные компьютеры воплощают в себе наиболее качественные инженерные решения, но это все не предназначено для рядового покупателя. А некоторые исследователи даже считают, что ведение игр представляет собой нечто, не имеющее отношения к основному направлению развития искусственного интеллекта. Тем не менее эта область продолжает порождать не только всеобщее восхищение, но и постоянный поток инноваций, которые затем усваиваются более широким сообществом разработчиков.
Шахматы. В 1957 году Герберт Саймон предсказал, что через 10 лет компьютеры победят человека — чемпиона мира по шахматам. Через сорок лет программа Deep Blue победила Гарри Каспарова в показательном матче из шести игр. Саймон ошибся, но лишь с коэффициентом 4. Каспаров писал:
Решающей игрой в этом матче была вторая партия, которая оставила глубокий след в моей памяти... Мы наблюдали события, которые намного превосходили самые невероятные ожидания в отношении того, насколько хорошо компьютер будет способен предвидеть долговременные позиционные последствия своих решений. Машина отказалась перейти в позицию, имеющую явное, но кратковременное преимущество, продемонстрировав вполне человеческое ощущение опасности [774].
Программа Deep Blue была создана Мьюрреем Кэмпбеллом, Фенгсюнг Су и Джозефом Хоаном из компании IBM [216] на основе проекта Deep Thought, разработанного ранее Кэмпбеллом и Су в университете Карнеги—Меллона (Carnegie—Mellon University — CMU). Компьютер-победитель представлял собой параллельный компьютер с 30 процессорами IBM RS/6000. На этом компьютере эксплуатировались средства "программного поиска" и 480 специализированных СБИС шахматных процессоров, которые осуществляли выработку ходов (включая упорядочение ходов), "аппаратного поиска" для последних нескольких уровней дерева и проводилась оценка листовых узлов. В программе Deep Blue в среднем осуществлялся поиск 126 миллионов узлов в секунду, а пиковая скорость достигала 330 миллионов узлов в секунду. Эта программа формировала вплоть до 30 миллиардов позиций в расчете на каждый ход, обычно достигая глубины поиска 14. Основой этой программы является стандартный альфа-бета-поиск с итеративным углублением на основе таблицы транспозиций, но ключом к успеху этой программы, по-видимому, стала ее способность вырабатывать расширения, выходящие за пределы глубины поиска для достаточно интересных линий форсирующих/форсированных ходов. В некоторых случаях этот поиск достигал глубины в 40 полуходов. Функция оценки охватывала свыше 8000 характеристик, причем многие из них описывали в высшей степени специфичные шаблоны расположения фигур. Использовался справочник дебютов, состоящий примерно из 4000 позиций, а также база данных с 700 000 игр гроссмейстеров, из которой программа могла извлекать согласованные рекомендации. Кроме того, в этой системе применялась большая база данных эндшпилей, состоящая из позиций с решениями, в которой содержались все позиции с пятью фигурами и многие позиции с шестью фигурами. Использование этой базы данных привело к значительному увеличению эффективной глубины поиска, что позволило программе Deep Blue в некоторых случаях играть идеально даже за много ходов до мата.
Успех программы Deep Blue укрепил и без того широко распространенное мнение, что прогресс в области ведения компьютерных игр достигается главным образом за счет все более мощного аппаратного обеспечения; к тому же распространение таких взглядов стимулировалось компанией IBM. Создатели программы Deep Blue, с другой стороны, утверждают, что важную роль сыграло также расширение поиска и применение продуманной функции оценки [216]. Более того, нам известно, что некоторые новейшие алгоритмические усовершенствования позволяют программам, работающим на стандартных персональных компьютерах, побеждать на каждом мировом чемпионате по компьютерным шахматам с 1992 года и часто наносить поражение противникам с массовой параллельной архитектурой, способным выполнять поиск в 1000 раз большего количества узлов в секунду. Для сокращения эффективного коэффициента ветвления меньше чем до 3 (по сравнению с фактическим коэффициентом ветвления, составляющим около 35) применяются всевозможные эвристики отсечения. Наиболее важной из них является эвристика с пустым ходом, в которой вырабатывается хороший нижний предел значения позиции с использованием поверхностного поиска, в котором противнику в начале игры разрешается сделать ход дважды. Этот нижний предел часто позволяет выполнять альфа-бета-отсечение без затрат на полный поиск в глубину. Является также важным метод отсечения ненужных ходов, который позволяет решить заранее, какие ходы вызовут альфа-бета-отсечение в узлах-преемниках.
Группа разработчиков Deep Blue отказалась воспользоваться шансом провести матч-реванш, предложенный Каспаровым. Вместо этого в одном из самых последних крупных соревнований в 2002 году против чемпиона мира Владимира Крамника выступила программа Fritz. Матч из восьми игр окончился ничьей. Условия этого матча были гораздо более благоприятными для человека, и в качестве аппаратного обеспечения использовался обычный персональный компьютер, а не суперкомпьютер. Тем не менее Крамник прокомментировал этот матч так: "Теперь очевидно, что эта самая лучшая программа и чемпион мира играют примерно на равных".
Шашки. Начиная с 1952 года Артур Самюэл из компании IBM в свое свободное время занимался разработкой программы игры в шашки, которая совершенствовала с помощью обучения свою собственную функцию оценки, играя сама с собой тысячи раз. Эта идея будет описана более подробно в главе 21. Программа Самюэла вначале играла на уровне новичка, но всего лишь через несколько дней игры с самой собой усовершенствовалась до такого уровня, что стала побеждать Самюэла (хотя он не был сильным игроком). В 1962 году эта программа победила Роберта Нили, чемпиона игры в шашки "вслепую", благодаря ошибке с его стороны. Многие в то время посчитали, что компьютеры уже играют в шашки лучше людей, но фактически этого еще не произошло. Тем не менее, если учесть то, что вычислительное оборудование, использовавшееся Самюэлом (компьютер IBM 704), имело 10 000 слов основной памяти, магнитную ленту для долговременного хранения и процессор с частотой 0,000001 ГГц, эта победа остается большим достижением.
Превзойти данное достижение пытались многие, и, наконец, Джонатан Шеффер со своими коллегами разработал программу Chinook, которая работает на обычных персональных компьютерах и использует альфа-бета-поиск. В программе Chinook применяется заранее вычисленная база данных из всех 444 миллиардов позиций с восьмью или меньшим количеством шашек на доске, что позволяет ей играть в эндшпиле безошибочно. Программа Chinook заняла второе место в 1990 году на открытом чемпионате США и завоевала право сделать заявку на участие в мировом чемпионате. Но затем эта программа столкнулась с проблемой в лице Мэриона Тинсли. Доктор Тинсли был чемпионом мира свыше 40 лет, проиграв за все это время только три партии. В первом матче против программы Chinook Тинсли потерпел свое четвертое и пятое поражение, но выиграл матч со счетом 20,5—18,5. Матч на звание чемпионата мира в августе 1994 года между Тинсли и программой Chinook закончился преждевременно, поскольку Тинсли был вынужден сдаться из-за ухудшения состояния здоровья. Программа Chinook была официально признана чемпионом мира.
Шеффер считает, что при наличии достаточной вычислительной мощи база данных с эндшпилями может быть увеличена до такой степени, что прямой поиск из начальной позиции будет всегда достигать решенных позиций, т.е. задача игры в шашки должна быть полностью решена. (Программа Chinook иногда объявляла о своем выигрыше на пятом ходу.) Исчерпывающий анализ такого рода может быть выполнен вручную для игры в крестики-нолики 3x3 и с помощью компьютера для игр Qubic (объемные крестики-нолики 4x4x4), гомоку (пять в ряд) и Nine-Men's Morris (Мельница) [524]. В замечательной работе Кена Томпсона и Льюиса Стилле-ра [1464] приведены решения всех шахматных эндшпилей с пятью фигурами и некоторых эндшпилей с шестью фигурами, причем эти результаты предоставлены для всеобщего доступа в Internet. Стиллер обнаружил один вариант, в котором достигался форсированный мат, но он состоял из 262 ходов; этот результат вызвал некоторый переполох, поскольку в шахматных правилах установлено, чтобы в течение 50 ходов происходил хоть какой-то "прогресс", иначе засчитывается ничья.
Игра "Отелло", называемая также "Реверси", по-видимому, более популярна как компьютерная игра, а не настольная. Она имеет меньшее пространство поиска, чем шахматы, поскольку в ней обычно имеется от 5 до 15 допустимых ходов, но опыт в оценке позиций в ней пришлось накапливать буквально с нуля. В 1997 году программа Logistello [209] победила человека — чемпиона мира, Такеси Мураками, со счетом 6:0. Теперь общепризнано, что люди не могут соревноваться с компьютерами в игре "Отелло".
Нарды. В разделе 6.5 описано, почему из-за включения элемента неопределенности, вызванного метанием жребия, глубокий поиск становится дорогостоящей роскошью. В области игры в нарды было предпринято много усилий по усовершенствованию функции оценки. Гэри Тесауро [1499] использовал сочетание метода обучения с подкреплением Самюэла и методов нейронных сетей (глава 20) для разработки удивительно точного средства оценки, которое использовалось при поиске на глубину 2 или 3. Сыграв против самой себя больше миллиона тренировочных игр, разработанная Гэри Тесауро программа TD-Gammon по праву заняла место среди лучших трех игроков мира. Некоторые рекомендации этой программы по выбору дебютных ходов в начальной стадии игры в нарды радикально расходились с "мудрыми" советами, передававшимися из поколения в поколение в течение многих веков.
Го — это наиболее популярная настольная игра в Азии, которая для полного овладения мастерством требует от профессионалов столько же усилий, как шахматы. Поскольку в ней доска имеет размеры 19x19, коэффициент ветвления начинается с 361, а эта величина слишком обременительна для обычных методов поиска. Вплоть до 1997 года вообще не было ни одной достаточно компетентной программы, но теперь программы часто делают ходы, достойные уважения. В большинстве наилучших программ сочетаются методы распознавания шаблонов (в которых используется принцип — при появлении такого-то шаблона из камней необходимо рассмотреть такой-то ход) с ограниченным поиском (для выработки решения о том, следует ли стремиться к захвату таких-то камней, не выходя за пределы данной локальной области). Ко времени написания данной книги, по-видимому, самыми сильными программами были Goemate Чен Жишинга и Go4++ Майкла Рейса, каждая из которых достигает рейтинга, примерно равного 10 кю (уровень слабого любителя). Ведение игры го — это такая область, которая, скорее всего, достигнет развития в результате интенсивных исследований с использованием более сложных методов формирования рассуждений. Успех может быть достигнут в результате обнаружения способов интеграции нескольких линий локальных рассуждений о каждой из многих слабо связанных "субигр", на которые может быть выполнена декомпозиция всей игры го. Подобные методы имели бы колоссальную ценность для всех интеллектуальных систем в целом.
Бридж — это игра с неполной информацией: карты любого игрока скрыты от других игроков. Кроме того, бридж — это игра с несколькими игроками, в которой участвуют четыре игрока, а не два, хотя игроки разбиты по парам на две команды. Как было показано в разделе 6.5, оптимальная игра в бридж может включать элементы сбора информации, передачи информации, введения в заблуждение и тщательного взвешивания вероятностей. Многие из этих методов используются в программе Bridge Baron™ [1441], которая выиграла в 1997 году чемпионат мира по бриджу среди компьютеров. Хотя программа Bridge Baron не играет оптимальным образом, она представляет собой одну из немногих успешно действующих систем ведения игры, в которой используются сложные, иерархические планы (см. главу 12), основанные на таких идеях высокого уровня, как импас (finessing) и сквиз (squeezing), которые знакомы игрокам в бридж.
Чемпионат мира 2000 года с большим отрывом от соперников выиграла программа GIB [559]. В программе GIB используется метод "усреднения по прогнозам" с двумя важными модификациями. Во-первых, в этой программе вместо исследования того, насколько удачным окажется каждый вариант игры по отношению к каждому варианту возможного расположения скрытых карт (количество которых может достигать 10 миллионов), исследуется случайно выбранный образец из 100 расположений. Во-вторых, в программе GIB используется обобщение на основе объяснения для вычисления и кэширования общих правил оптимальной игры в виде определений различных стандартных классов ситуаций. Это позволяет данной программе принимать точное решение в отношении каждой раздачи. Тактическая точность программы GIB компенсирует ее неспособность формировать рассуждения в отношении имеющейся информации. Она финишировала на 12-м месте среди 35 участников в парных соревнованиях (в которых предусматривался только розыгрыш карт, имеющихся на руках) в чемпионате мира среди людей в 1998 году, значительно превзойдя ожидания многих специалистов в этой области.







Материалы

Яндекс.Метрика