Лекция: Современные игровые программы.

Публичная демонстрация программ ведения игр представляет собой для искусст­венного интеллекта примерно то же, что и участие в автогонках международного масштаба для автомобильной промышленности — суперсовременные игровые про­граммы действуют поразительно быстро, чрезвычайно тщательно настроенные ком­пьютеры воплощают в себе наиболее качественные инженерные решения, но это все не предназначено для рядового покупателя. А некоторые исследователи даже счита­ют, что ведение игр представляет собой нечто, не имеющее отношения к основному направлению развития искусственного интеллекта. Тем не менее эта область про­должает порождать не только всеобщее восхищение, но и постоянный поток инно­ваций, которые затем усваиваются более широким сообществом разработчиков.

Шахматы. В 1957 году Герберт Саймон предсказал, что через 10 лет компьюте­ры победят человека — чемпиона мира по шахматам. Через сорок лет программа Dеер Вlue победила Гарри Каспарова в показательном матче из шести игр. Саймон

ошибся, но лишь с коэффициентом 4. Каспаров писал:

«Решающей игрой в этом матче была вторая партия, которая оставила глубокий след в мо­ей памяти… Мы наблюдали события, которые намного превосходили самые невероятные ожидания в отношении того, насколько хорошо компьютер будет способен предвидеть долговременные позиционные последствия своих решений. Машина отказалась перейти в позицию, имеющую явное, но кратковременное преимущество, продемонстрировав вполне человеческое ощущение опасности.»

Программа Dеер Вlue была создана Мьюрреем Кэмпбеллом, Фенгсюнг Су и Джо­зефом Хоаном из компании IВM на основе проекта Dеер Thought, разработан­ного ранее Кэмпбеллом и Су в университете Карнеги-Меллона (Carnegie-Mellon University — CMU). Компьютер-победитель представлял собой параллельный ком­пьютер с 30 процессорами IВM RS/6000. На этом компьютере эксплуатировались средства «программного поиска» и 480 специализированных СБИС шахматных процессоров, которые осуществляли выработку ходов (включая упорядочение ходов), «аппаратного поиска» для последних нескольких уровней дерева и проводилась оценка листовых узлов. В программе Dеер Вlue в среднем осуществлялся поиск 126 миллионов узлов в секунду, а пиковая скорость достигала 330 миллионов узлов в секунду. Эта программа формировала вплоть до 30 миллиардов позиций в расчете на каждый ход, обычно достигая глубины поиска 14. Основой этой программы являет­ся стандартный альфа-бета-поиск с итеративным углублением на основе таблицы транспозиций, но ключом к успеху этой программы, по-видимому, стала ее способ­ность вырабатывать расширения, выходящие за пределы глубины поиска для доста­точно интересных линий форсирующих/форсированных ходов. В некоторых случаях этот поиск достигал глубины в 40 полуходов. Функция оценки охватывала свыше 8000 характеристик, причем многие из них описывали в высшей степени специфич­ные шаблоны расположения фигур. Использовался справочник дебютов, состоящий примерно из 4000 позиций, а также база данных с 700 000 игр гроссмейстеров, из ко­торой программа могла извлекать согласованные рекомендации. Кроме того, в этой системе применялась большая база данных эндшпилей, состоящая из позиций с ре­шениями, в которой содержались все позиции с пятью фигурами и многие позиции с шестью фигурами. Использование этой базы данных привело к значительному увеличению эффективной глубины поиска, что позволило программе Dеер Вlue в некоторых случаях играть идеально даже за много ходов до мата.

Успех программы Dеер Вlue укрепил и без того широко распространенное мне­ние, что прогресс в области ведения компьютерных игр достигается главным обра­зом за счет все более мощного аппаратного обеспечения; к тому же распространение таких взглядов стимулировалось компанией IВM. Создатели программы Dеер Вlue, с другой стороны, утверждают, что важную роль сыграло также расширение поиска и применение продуманной функции оценки. Более того, нам известно, что не­которые новейшие алгоритмические усовершенствования позволяют программам, работающим на стандартных персональных компьютерах, побеждать на каждом миpoвoм чемпионате по компьютерным шахматам с 1992 года и часто наносить пора­жение противникам с массовой параллельной архитектурой, способным выполнять поиск в 1000 раз большего количества узлов в секунду. Для сокращения эффектив­ного коэффициента ветвления меньше чем до 3 (по сравнению с фактическим ко­эффициентом ветвления, составляющим около 35) применяются всевозможные эв­ристики отсечения. Наиболее важной из них является эвристика с пустым ходом, в которой вырабатывается хороший нижний предел значения позиции с исполь­зованием поверхностного поиска, в котором противнику в начале игры разреша­ется сделать ход дважды. Этот нижний предел часто позволяет выполнять альфа-­бета-отсечение без затрат на полный поиск в глубину. Является также важным метод отсечения ненужных ходов, который позволяет решить заранее, какие ходы вызовут альфа-бета-отсечение в узлах-преемниках.

Группа разработчиков Dеер Вlue отказалась воспользоваться шансом провести матч-реванш, предложенный Каспаровым. Вместо этого в одном из самых последних крупных соревнований в 2002, году против чемпиона мира Владимира Крамника выступила программа Fritz. Матч из восьми игр окончился ничьей. Условия. этого матча были гораздо более благоприятными для человека, и в качестве аппаратного обеспечения использовался обычный персональный компьютер, а не суперкомпью­тер. Тем не менее Крамник прокомментировал этот матч так: «Теперь очевидно, что эта самая лучшая программа и чемпион мира играют примерно на равных».

Шашки. Начиная с 1952 года Артур Самюэл из компании IВM в свое свобод­ное время занимался разработкой программы игры в шашки, которая совершенст­вовала с помощью обучения свою собственную функцию оценки, играя сама с собой

тысячи раз. Программа Самюэла вначале играла на уровне новичка, но всего лишь через несколько дней игры с самой собой усовершенствовалась до такого уровня, что стала побеждать Самюэла (хотя он не был сильным игроком). В 1962 году эта программа победила Роберта Нили, чем­пиона игры в шашки «вслепую», благодаря ошибке с его стороны. Многие в то вре­мя посчитали, что компьютеры уже играют в шашки лучше людей, но фактически этого еще не произошло. Тем не менее, если учесть то, что вычислительное оборудо­вание, использовавшееся Самюэлом (компьютер IВM 704), имело 10000 слов ос­новной памяти, магнитную ленту для долговременного хранения и процессор с час­тотой 0,000001 ГГц, эта победа остается большим достижением.

Превзойти данное достижение пытались многие, и, наконец, Джонатан Шеффер со своими коллегами разработал программу Chinook, которая работает на обычных персональных компьютерах и использует альфа-бета-поиск… В программе Chinook применяется заранее вычисленная база данных из всех 444 миллиардов позиций с восьмью или меньшим количеством. шашек на доске, что позволяет ей играть в энд­шпиле безошибочно. Программа Chinook заняла второе место в 1990 году на открытом чемпионате США и завоевала право сделать заявку на участие в мировом чемпионате. Но затем эта программа столкнулась с проблемой в лице Мэриона Тинсли. Доктор Тинсли был чемпионом мира свыше 40 лет, проиграв за все это время только три пар­тии. В первом матче против программы Chinook Тинсли потерпел свое четвертое и пя­тое поражение, но выиграл матч со счетом 20,5-18,5. Матч на звание чемпионата мира в августе 1994 года между Тинсли и программой Chinook закончился преждевременно, поскольку Тинсли был вынужден сдаться из-за ухудшения состояния здоровья. Про­грамма Chinook была официально признана чемпионом мира.

Шеффер считает, что при наличии достаточной вычислительной мощи база дан­ных с эндшпилями может быть увеличена до такой степени, что прямой поиск изначальной позиции будет всегда достигать решенных позиций, Т.е. задача игры в шашки должна быть полностью решена. (Программа Chinook иногда объявляла о своем выигрыше на пятом ходу.) Исчерпывающий анализ такого рода может быть выполнен вручную для игры в крестики-нолики 3х3 и с помощью компьютера для игр Qиbic (объемные крестики-нолики 4 х 4 х 4), гомоку (пять в ряд) и Nine-Men's Morris (Мельница). В замечательной работе Кена Томпсона и Льюиса Стилле­ра приведены решения всех шахматных эндшпилей с пятью фигурами и некоторых эндшпилей с шестью фигурами, причем эти результаты предоставлены для всеобщего доступа в Internet. Стиллер обнаружил один вариант, в котором достигал­ся форсированный мат, но он состоял из 262 ходов; этот результат вызвал некоторый переполох, поскольку в шахматных правилах установлено, чтобы в течение 50 ходов происходил хоть какой-то «прогресс», иначе засчитывается ничья.

Нарды. В этой игре из-за наличия элемента неопреде­ленности, вызванного метанием жребия, глубокий поиск становится дорогостоящей роскошью. В области игры в нарды было предпринято много усилий по усовершен­ствованию функции оценки. Гэри Тесауро использовал сочетание метода обу­чения с подкреплением Самюэла и методов нейронных сетей для разра­ботки удивительно точного средства оценки, которое использовалось при поиске на глубину 2 или 3. Сыграв против самой себя больше миллиона тренировочных игр, разработанная Гэри Тесауро программа TD-Gammon по праву заняла место среди лучших трех игроков мира. Некоторые рекомендации этой программы по выбору де­бютных ходов в начальной стадии игры в нарды радикально расходились с «мудрыми» советами, передававшимися из поколения в поколение в течение многих веков.

Го — это наиболее популярная настольная игра в Азии, которая для полного овладения мастерством требует от профессионалов столько же усилий, как шахматы. Поскольку в ней доска имеет размеры 19Х19, коэффициент ветвления начинается с 361, а эта величина слишком обременительна для обычных методов поиска. Вплоть до 1997 года вообще не было ни одной достаточно компетентной программы, но те­перь программы часто делают ходы, достойные уважения. В большинстве наилуч­ших программ сочетаются методы распознавания шаблонов (в которых используется принцип — при появлении такого-то шаблона из камней необходимо рассмотреть такой-то ход) с ограниченным поиском (для выработки решения о том, следует ли стремиться к захвату таких-то камней, не выходя за пределы данной локальной об­ласти). К настоящему времени, самыми сильными программами были Goemate Чен Жишинга и G04++ Майкла Рейса, каждая из кото­рых достигает рейтинга, примерно равного 10 кю (уровень слабого любителя). Веде­ние игры го — это такая область, которая, скорее всего, достигнет развития в результате интенсивных исследований с использованием более сложных методов форми­рования рассуждений. Успех может быть достигнут в результате обнаружения способов интеграции нескольких линий локальных рассуждений о каждой из мно­гих слабо связанных «субигр», на которые может быть выполнена декомпозиция всей игры го. Подобные методы имели бы колоссальную ценность для всех интеллектуальных систем в целом..

Бридж — это игра с неполной информацией: карты любого игрока скрыты от других игроков. Кроме того, бридж — это игра с несколькими игроками, в которой участвуют четыре игрока, а не два, хотя игроки разбиты по парам на две команды. Оптимальная игра в бридж может включать элементы сбора информации, передачи информации, введения в заблуждение и тщатель­ного взвешивания вероятностей. Многие из этих методов используются в программе Bridge BaronTM, которая выиграла в 1997 году чемпионат мира по бриджу среди компьютеров. Хотя программа Bridge Baron не играет оптимальным образом, она представляет собой одну из немногих успешно действующих систем ведения игры, в которой используются сложные, иерархические планы, основанные на таких идеях высокого уровня, как импас (finessing) и сквиз(squeezing), которые знакомы игрокам в бридж.

Чемпионат мира 2000 года с большим отрывом от соперников выиграла программа GIB. В программе GIВ используется метод «усреднения по прогнозам» с двумя важными модификациями. Во-первых, в этой программе вместо исследова­ния того, насколько удачным окажется каждый вариант игры по отношению к каж­дому варианту возможного расположения скрытых карт (количество которых может достигать 10 миллионов), исследуется случайно выбранный образец из 100 располо­жений. Во-вторых, в программе GIВ используется обобщение на основе объяснения для вычисления и кэширования общих правил оптимальной игры в виде определе­ний различных стандартных классов ситуаций. Это позволяет данной программе принимать точное решение в отношении каждой раздачи. Тактическая точность программы GIВ компенсирует ее неспособность формировать рассуждения в отно­шении имеющейся информации. Она финишировала на 12-м месте среди 35 участ­ников в парных соревнованиях (в которых предусматривался только розыгрыш карт, имеющихся на руках) в чемпионате мира среди людей в 1998 году, значительно пре­взойдя ожидания многих специалистов в этой области.