Лекция
Публичная демонстрация программ ведения игр представляет собой для искусственного интеллекта примерно то же, что и участие в автогонках международного масштаба для автомобильной промышленности — суперсовременные игровые программы действуют поразительно быстро, чрезвычайно тщательно настроенные компьютеры воплощают в себе наиболее качественные инженерные решения, но это все не предназначено для рядового покупателя. А некоторые исследователи даже считают, что ведение игр представляет собой нечто, не имеющее отношения к основному направлению развития искусственного интеллекта. Тем не менее эта область продолжает порождать не только всеобщее восхищение, но и постоянный поток инноваций, которые затем усваиваются более широким сообществом разработчиков.
Компьютерные игры, основанные на классических настольных играх, таких как шахматы, шашки, го, нарды и бридж, представляют собой уникальное сочетание традиций и современных технологий. Эти игры, которые веками привлекали внимание любителей интеллектуальных развлечений, теперь стали доступны в цифровом формате. Они не только сохраняют глубокие стратегические аспекты оригиналов, но и предлагают новые возможности для обучения, анализа и многопользовательских сражений по всему миру.
Шахматы, вероятно, являются самой популярной стратегической игрой, с тысячелетней историей, охватывающей культуру и математику. В компьютерной версии игры шахматы дают возможность играть с искусственным интеллектом разного уровня сложности, что делает ее доступной как для новичков, так и для профессионалов.
Шашки, игра с простыми правилами и глубокой тактической составляющей, также пользуется спросом в цифровом виде. Ее компьютерные версии предлагают широкий выбор уровней сложности, а также вариации правил в зависимости от предпочтений игрока.
Го — древняя восточная игра, знаменитая своей стратегической глубиной, где победа зависит от умения игрока захватывать и окружать территории. Компьютерные реализации го открыли для игроков новые горизонты, предложив обучение и анализ партий на высоком уровне с использованием машинного обучения.
Нарды, игра, которая сочетает стратегию с элементами случайности, также получила свое продолжение в цифровом мире. Компьютерные версии нард позволяют быстро играть с оппонентами из любой точки мира и дают возможность практиковать тактику в любой момент.
Наконец, бридж, одна из самых сложных карточных игр, требует как командного взаимодействия, так и глубоких знаний правил и тактики. Компьютерные версии бриджа предоставляют широкий спектр возможностей для обучения и игры, а также турниров для игроков разного уровня.
Таким образом, цифровизация этих классических игр позволяет сохранить их культурное и интеллектуальное наследие, одновременно предлагая новые способы их изучения и развития навыков в виртуальном пространстве.
В 1957 году Герберт Саймон предсказал, что через 10 лет компьютеры победят человека — чемпиона мира по шахматам. Через сорок лет программа Deep Blue победила Гарри Каспарова в показательном матче из шести игр. Саймон ошибся, но лишь с коэффициентом 4. Каспаров писал:
Решающей игрой в этом матче была вторая партия, которая оставила глубокий след в моей памяти... Мы наблюдали события, которые намного превосходили самые невероятные ожидания в отношении того, насколько хорошо компьютер будет способен предвидеть долговременные позиционные последствия своих решений. Машина отказалась перейти в позицию, имеющую явное, но кратковременное преимущество, продемонстрировав вполне человеческое ощущение опасности.
Программа Deep Blue была создана Мьюрреем Кэмпбеллом, Фенгсюнг Су и Джозефом Хоаном из компании IBM на основе проекта 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, с другой стороны, утверждают, что важную роль сыграло также расширение поиска и применение продуманной функции оценки.
Более того, нам известно, что некоторые новейшие алгоритмические усовершенствования позволяют программам, работающим на стандартных персональных компьютерах, побеждать на каждом мировом чемпионате по компьютерным шахматам с 1992 года и часто наносить поражение противникам с массовой параллельной архитектурой, способным выполнять поиск в 1000 раз большего количества узлов в секунду.
Для сокращения эффективного коэффициента ветвления меньше чем до 3 (по сравнению с фактическим коэффициентом ветвления, составляющим около 35) применяются всевозможные эвристики отсечения. Наиболее важной из них является эвристика с пустым ходом, в которой вырабатывается хороший нижний предел значения позиции с использованием поверхностного поиска, в котором противнику в начале игры разрешается сделать ход дважды. Этот нижний предел часто позволяет выполнять альфа-бета-отсечение без затрат на полный поиск в глубину. Является также важным метод отсечения ненужных ходов, который позволяет решить заранее, какие ходы ызовут альфа-бета-отсечение в узлах-преемниках.
Группа разработчиков Deep Blue отказалась воспользоваться шансом провести матч-реванш, предложенный Каспаровым. Вместо этого в одном из самых последних крупных соревнований в 2002 году против чемпиона мира Владимира Крамника выступила программа Fritz. Матч из восьми игр окончился ничьей. Условия этого матча были гораздо более благоприятными для человека, и в качестве аппаратного обеспечения использовался обычный персональный компьютер, а не суперкомпьютер. Тем не менее Крамник прокомментировал этот матч так: "Теперь очевидно, что эта самая лучшая программа и чемпион мира играют примерно на равных".
Начиная с 1952 года Артур Самюэл из компании IBM в свое свободное время занимался разработкой программы игры в шашки, которая совершенствовала с помощью обучения свою собственную функцию оценки, играя сама с собой тысячи раз. Программа Самюэла вначале играла на уровне новичка, но всего лишь через несколько дней игры с самой
собой усовершенствовалась до такого уровня, что стала побеждать Самюэла (хотя он не был сильным игроком).
В 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 Torris (Мельница).
В замечательной работе Кена Томпсона и Льюиса Стиллера приведены решения всех шахматных эндшпилей с пятью фигурами и некоторых эндшпилей с шестью фигурами, причем эти результаты предоставлены для всеобщего доступа в Internet. Стиллер обнаружил один вариант, в котором достигался форсированный мат, но он состоял из 262 ходов; этот результат вызвал некоторый пнереполох, поскольку в шахматных правилах установлено, чтобы в течение 50 ходов происходил хоть какой-то "прогресс", иначе засчитывается ничья.
Реверси, по-видимому, более популярна как компьютерная игра, а не настольная. Она имеет меньшее пространство поиска, чем шахматы, поскольку в ней обычно имеется от 5 до 15 допустимых ходов, но опыт в оценке позиций в ней пришлось накапливать буквально с нуля. В 1997 году программа Logistello победила человека — чемпиона мира, Такеси Мураками, со счетом 6:0. Теперь общепризнано, что люди не могут соревноваться с компьютерами игре "Отелло".
Нарды. В разделе 6.5 описано, почему из-за включения элемента неопределенности, вызванного метанием жребия, глубокий поиск становится дорогостоящей роскошью. В области игры в нарды было предпринято много усилий по усовершенствованию функции оценки. Гэри Тесауро использовал сочетание метода обучения с подкреплением Самюэла и методов нейронных сетей для разработки удивительно точного средства оценки, которое использовалось при поиске на глубину 2 или 3.
Сыграв против самой себя больше миллиона тренировочных игр, разработанная Гэри Тесауро программа TD-Gammon по праву заняла место среди лучших трех игроков мира. Некоторые рекомендации этой программы по выбору дебютных ходов в начальной стадии игры в нарды радикально расходились с "мудрыми" оветами, передававшимися из поколения в поколение в течение многих веков.
Го — это наиболее популярная настольная игра в Азии, которая для полного владения мастерством требует от профессионалов столько же усилий, как шахматы. Поскольку в ней доска имеет размеры 19x19, коэффициент ветвления начинается с 361, а эта величина слишком обременительна для обычных методов поиска. Вплоть до 1997 года вообще не было ни одной достаточно компетентной программы, но теперь программы часто делают ходы, достойные уважения.
В течение долгого времени считалось, что компьютерное го имеет существенные различия по сравнению с компьютерными шахматами, поскольку методы, основанные на быстром поиске по сравнению с человеческим опытом, объединенные с относительно низким знанием предметной области не будут эффективны для го. Поэтому большие усилия в области компьютерного го были потрачены на объединение экспертных знаний с локальным поиском для нахождения ответа на вопросы тактической природы игры. Результатом этих усилий были программы, способные находить хорошие решения в некоторых локальных ситуациях, но имевшие явные слабости в полной обработке игры. Кроме того, эти классические программы с увеличением мощности аппаратуры мало получали в плане силы игры и поэтому развитие этой области было в целом медленным. Поэтому считалось, что программа, хорошо играющая в го, может быть создана только в далеком будущем и только с помощью накопленных к тому времени общих знаний в области искусственного интеллекта. Даже написание программы, способной определить победителя в законченной игре, воспринималось как нетривиальная задача.
В 2006 году появились программы, основанные на поиске Монте-Карло. Сила игры искусственного интеллекта улучшилась. Но разрыв с уровнем игры профессиональных игроков в го оставался, и причем значительный.
Однако в 2015 году компьютерная программа (AlphaGo, компании DeepMind) впервые выиграла у профессионала (Фань Хуэя, 2 профессиональный дан) равный матч (со счетом 5—0).
В марте 2016 года AlphaGo победила профессионала Ли Седола в первых трех партиях из пяти игр. Это был первый случай, когда профессионал 9 дана, один из сильнейших игроков мира, играл с компьютером без гандикапа. В четвертой игре Ли смог одержать победу, но пятую партию выиграл компьютер, таким образом матч закончился со счетом 4：1
В большинстве наилучших программ сочетаются методы распознавания шаблонов (в которых используется принцип — при появлении такого-то шаблона из камней необходимо рассмотреть такой-то ход) с ограниченным поиском (для выработки решения о том, следует ли стремиться к захвату таких-то камней, не выходя за пределы данной локальной области). Ко времени написания данной книги, по-видимому, самыми сильными программами были Goemate Чен Жишинга и Go4++ Майкла Рейса, каждая из которых достигает рейтинга, примерно равного 10 ку (уровень слабого любителя).
В шахматах, как и во многих других играх, в течение партии фигур на доске становится меньше, что упрощает перебор ходов. В го каждый следующий ход, наоборот, добавляет на доску один камень (хотя возможны и снятия), создавая дополнительные игровые моменты.
ногда упоминается, что некоторые трудные комбинаторные проблемы (фактически любая NP-полная задача) могут быть преобразованы применительно к го; однако то же верно и для других настольных игр, подобных шахматам, обобщенным для доски произвольной размерности. NP-полные задачи не могут решаться людьми быстрее, чем компьютерами: сомнительно, что человек в состоянии, например, решить Задачу коммивояжера за время, сопоставимое с тем, за которое ее решает компьютер. Следовательно, возможность применить методы решения NP-полных задач к компьютерному го не позволяет объяснить превосходства человека над компьютером в этой игре.
Люди чувствуют, что играют в го лучше, чем компьютеры, потому что сравнивают их с людьми. «Возможно это не компьютеры играют в го плохо, а люди играют в него слишком хорошо»[12]. Го, по сравнению с другими играми с полной информацией, имеет особенности, которые делают ее особенно легкой для людей. Камни не перемещаются, как фигуры в шахматах, не меняют цвет, как в реверси. Эти особенности позволяют людям просчитывать длинные цепочки ходов, что очень сложно для машины.
Однако в тех редких случаях, когда камни неоднократно захватываются и переигрываются на тех же самых пунктах, у людей есть проблемы, в то время как они легки для компьютеров.
Ведение игры го — это такая область, которая, скорее всего, достигнет развития в результате интенсивных исследований с использованием более сложных методов формирования рассуждений. Успех может быть достигнут в результате обнаружения способов интеграции нескольких линий локальных рассуждений о каждой из многих слабо связанных "субигр", на которые может быть выполнена декомпозиция всей игры го. Подобные методы имели бы колоссальную ценность для всех интеллектуальных систем в целом.
Шахматная техника не может быть применена в го Компьютерные го-программы долгое время были значительно более слабы, чем шахматные программы. Подходы, которые были применены в шахматных программах, показали себя посредственными в компьютерном го.
Шахматные правила легко формализуемы и могут быть представлены машине в удобной форме, которая позволит ей играть на высоком уровне.
Но простые позиционные правила, применяемые в шахматах, не будут эффективны в го . Для определения ценности камня необходим сложный анализ, хотя бы для определения того, жива ли группа, которой он принадлежит, как велико влияние группы и какие опасности ей грозят.
Бридж — это игра с неполной информацией: карты любого игрока скрыты от других игроков. Кроме того, бридж — это игра с несколькими игроками, в которой участвуют четыре игрока, а не два, хотя игроки разбиты по парам на две команды. Оптимальная игра в бридж может включать элементы сбора информации, передачи информации, введения в заблуждение и тщательного взвешивания вероятностей. Многие из этих методов используются в программе Bridge Baron™, которая выиграла в 1997 году чемпионат мира по бриджу среди компьютеров. Хотя программа Bridge Baron не играет оптимальным образом, она представляет собой одну из немногих успешно действующих систем ведения игры, в которой используются сложные, иерархические планы, основанные на таких идеях высокого уровня, как импас (finessing) и сквиз (squeezing), которые знакомы игрокам в бридж.
Чемпионат мира 2000 года с большим отрывом от соперников выиграла программа GIB. В программе GIB используется метод "усреднения по прогнозам" двумя важными модификациями. Во-первых, в этой программе вместо исследования того, насколько удачным окажется каждый вариант игры по отношению к каждому варианту возможного расположения скрытых карт (количество которых может достигать 10 миллионов), исследуется случайно выбранный образец из 100 расположений. Во-вторых, в программе GIB используется обобщение на основе объяснения для вычисления и кэширования общих правил оптимальной игры в виде определений различных стандартных классов ситуаций. Это позволяет данной программе принимать точное решение в отношении каждой раздачи. Тактическая точность программы GIB компенсирует ее неспособность формировать рассуждения в отношении имеющейся информации. Она финишировала на 12-м месте среди 35 участников в парных соревнованиях (в которых предусматривался только розыгрыш карт, имеющихся на руках) в чемпионате мира среди людей в 1998 году, значительно превзойдя ожидания многих специалистов в этой области.
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Разработка компьютерных игр, гейм-дизайн
Термины: Разработка компьютерных игр, гейм-дизайн