Игра началась
С первых дней развития ИИ энтузиасты начали разрабатывать программы, способные побеждать людей в играх. В конце 1940-х годов Алан Тьюринг и Клод Шеннон, стоявшие у истоков компьютерной эры, написали программы для игры в шахматы, хотя в то время еще не было компьютеров, чтобы их запустить. В последующие десятилетия многие молодые любители игр осваивали программирование, чтобы научить компьютеры играть в свои любимые игры – шашки, шахматы, нарды, го, покер, а позже и в видеоигры.
В 2010 году молодой британский ученый и любитель игр Демис Хассабис вместе с двумя близкими друзьями основал в Лондоне компанию DeepMind Technologies. Хассабис – незаурядный человек и легенда современного ИИ. Шахматный вундеркинд, в шесть лет он начал выигрывать турниры, в пятнадцать стал профессионально программировать видеоигры, а уже в двадцать два основал собственную компанию по созданию видеоигр. Помимо занятия предпринимательством, он получил докторскую степень по когнитивной нейробиологии в Университетском колледже Лондона, надеясь тем самым приблизить свою цель – создание ИИ по образцу человеческого мозга. Хассабис с коллегами основали DeepMind Technologies, чтобы “заниматься поистине фундаментальными вопросами” искусственного интеллекта[183]. Возможно, не стоит удивляться, что специалисты DeepMind сочли видеоигры подходящей площадкой для работы над этими вопросами. Видеоигры, по мнению Хассабиса, “сродни микрокосму реального мира, но… понятнее и ограниченнее”[184].
Рис. 27. Иллюстрация игры Breakout, разработанной компанией Atari
Как бы вы ни относились к видеоиграм, если вы предпочитаете “понятную и ограниченную” среду “реальному миру”, вам стоит подумать о создании программ ИИ для видеоигр компании Atari, разработанных в 1970-х и 1980-х годах. Именно этим решили заняться специалисты DeepMind. В зависимости от того, сколько вам лет и какие у вас интересы, вы, возможно, помните некоторые классические игры: Asteroids, Space Invaders, Pong, Ms. Pac-Man. Знакомые названия? Простая графика и управление с помощью джойстика делали эти игры достаточно простыми, чтобы их могли освоить дети, но достаточно сложными, чтобы взрослые тоже не теряли к ним интерес.
Рассмотрим однопользовательскую игру Breakout, показанную на рис. 27. В ней игрок с помощью джойстика передвигает “ракетку” (белый прямоугольник в правом нижнем углу) из стороны в сторону. “Мяч” (белый кружок) отскакивает от ракетки и ударяется о разноцветные прямоугольные “кирпичи”. Мяч также отскакивает от серых “стен” по бокам. Когда мяч попадает по одному из кирпичей (узорчатые прямоугольники), кирпич исчезает, игрок получает очки, а мяч отскакивает назад. Кирпичи с верхних рядов приносят больше очков, чем с нижних. Когда мяч ударяется о “землю” (нижнюю часть экрана), игрок теряет одну из пяти “жизней”, но если у него еще остались “жизни”, то в игру вводится новый мяч. Цель игрока – набрать максимум очков за пять жизней.
Любопытно, что игра Breakout появилась, когда Atari попробовала создать однопользовательскую версию успешной игры Pong. Разработку и внедрение Breakout в 1975 году поручили двадцатиоднолетнему сотруднику по имени Стив Джобс. Да, тому самому Стиву Джобсу, который впоследствии стал одним из основателей Apple. Поскольку Джобсу не хватало навыков, он привлек к работе над Breakout своего друга Стива Возняка, которому тогда было двадцать пять (и который впоследствии стал вторым основателем Apple). Возняк и Джобс спроектировали Breakout за четыре ночи, садясь за работу вечером, когда у Возняка кончался рабочий день в компании Hewlett-Packard. Вскоре Breakout, как и Pong, завоевала огромную популярность у геймеров.
Если вы тоскуете по былым временам, но у вас не сохранилось старой игровой приставки Atari 2600, в интернете есть множество сайтов, где все еще можно сыграть в Breakout и другие игры. В 2013 году группа канадских исследователей ИИ выпустила программную платформу Arcade Learning Environment (“Среда обучения аркадным играм”), которая облегчила тестирование систем машинного обучения на 49 таких играх[185]. Именно эту платформу специалисты DeepMind использовали в своей работе по обучению с подкреплением.
Глубокое Q-обучение
Специалисты DeepMind совместили обучение с подкреплением – в частности, Q-обучение – с глубокими нейронными сетями, чтобы создать систему, которая сумеет научиться играть в видеоигры Atari. Они назвали свой подход глубоким Q-обучением. Я объясню принцип работы глубокого Q-обучения на примере Breakout, но в DeepMind использовали один и тот же метод для всех игр Atari, с которыми велась работа. Впереди нас ждет немало технических подробностей, так что готовьтесь (или переходите к следующему разделу).
Вспомните, как мы использовали Q-обучение для тренировки собаки-робота Рози. В ходе эпизода Q-обучения на каждой итерации обучающийся агент (Рози) делает следующее: определяет свое текущее состояние, сверяет это состояние с матрицей Q, выбирает действие на основе ценностей из матрицы, выполняет это действие, возможно, получает сигнал подкрепления и – обучаясь – обновляет ценности в своей матрице Q.
Глубокое Q-обучение DeepMind работает по тому же принципу, но место матрицы Q занимает сверточная нейронная сеть. По примеру DeepMind я назову ее глубокой Q-сетью (DQN). Показанная на рис. 28 DQN напоминает ту, что использовалась DeepMind для обучения игре Breakout (но при этом проще нее). Входным сигналом для DQN служит состояние системы в конкретный момент времени, которое здесь определяется текущим “кадром” – положением пикселей на текущем снимке экрана – и тремя предыдущими кадрами (положением пикселей на трех предыдущих шагах). Такое определение состояния обеспечивает систему небольшим объемом памяти, что оказывается здесь полезным. На выходе сеть выдает расчетную ценность каждого возможного действия во входном состоянии. Возможные действия таковы: передвинуть ракетку Влево, передвинуть ракетку Вправо или выполнить NOP (“холостую команду”, то есть не передвигать ракетку). Сама сверточная нейронная сеть практически не отличается от той, которую я описала в главе 4. Вместо ценностей в матрице Q, как в примере с Рози, в глубоком Q-обучении система узнает веса в этой сети.
Рис. 28. Схема глубокой Q-сети (DQN) для Breakout
Система DeepMind учится играть в Breakout в ходе множества эпизодов. Каждый эпизод соответствует одному сеансу игры, а каждая итерация в рамках эпизода – одному действию системы. В частности, на каждой итерации система вводит свое состояние в DQN и выбирает действие на основании выходных значений DQN. Система не всегда выбирает действие с наибольшей расчетной ценностью: как я упоминала выше, обучение с подкреплением требует баланса исследования-использования[186]. Система выполняет выбранное действие (например, передвигает ракетку на некоторое расстояние влево) и, возможно, получает вознаграждение, если мяч попадает в один из кирпичей. Затем система совершает обучающий шаг, то есть обновляет веса в DQN по методу обратного распространения ошибки.
Как происходит обновление весов? В этом заключается главное различие обучения с учителем и обучения с подкреплением. Как вы помните из предыдущих глав, метод обратного распространения ошибки подразумевает изменение весов нейронной сети с целью снижения погрешности ее выходных сигналов. При обучении с учителем погрешность оценивается непосредственно. Помните описанную в главе 4 гипотетическую сверточную нейронную сеть, которая училась классифицировать фотографии, распознавая на них кошек и собак? Если на входной обучающей фотографии была собака, но выходная уверенность в категории “собака” составляла всего 20 %, то погрешность такого выходного сигнала равнялась 100 % – 20 % = 80 %. Иными словами, при идеальном раскладе выходная уверенность должна была быть на 80 % выше. Сеть могла рассчитать погрешность, потому что сверялась с меткой, присвоенной человеком.
Но в обучении с подкреплением меток нет. Конкретному кадру игры не присвоена метка с действием, которое необходимо предпринять. Как же в таком случае оценить погрешность выходного сигнала?
Вот ответ. Как вы помните, если вы обучающийся агент, то ценность действия в текущем состоянии определяется на основании вашей оценки того, насколько велико вознаграждение, которое вы получите в конце эпизода, выбрав это действие (и продолжая выбирать высокоценные действия). Эта оценка должна становиться лучше по мере приближения к концу эпизода, когда вы сможете провести учет всех полученных вознаграждений! Главное понимать, что выходные сигналы сети на текущей итерации точнее, чем на предыдущей итерации. В таком случае обучение заключается в том, чтобы корректировать веса сети (используя метод обратного распространения ошибки) с целью минимизации различия между выходными сигналами на текущей и предыдущей итерации. Один из разработчиков этого метода Ричард Саттон говорит, что здесь “догадка уточняется на основе догадки”[187]. Я внесу небольшую поправку: “догадка уточняется на основе лучшей догадки”.
Иными словами, вместо того чтобы учиться приводить свои выходные сигналы в соответствие с присвоенными человеком метками, сеть учится делать их согласованными от одной итерации к другой, полагая, что более поздние итерации рассчитывают ценность лучше, чем более ранние. Такой подход к обучению называется методом временных различий.
Вкратце вот как глубокое Q-обучение работает для игры Breakout (и всех остальных игр Atari). Система сообщает свое текущее состояние, которое становится входным сигналом глубокой Q-сети. Глубокая Q-сеть выдает значение ценности для каждого возможного действия. Система выбирает и выполняет действие, после чего оказывается в новом состоянии. Происходит обучение: система сообщает свое новое состояние сети, которая выдает новые значения ценности для каждого действия. Разница между новым набором ценностей и предыдущим набором ценностей считается “погрешностью” сети, и эта погрешность используется при коррекции весов в сети по методу обратного распространения ошибки. Эти шаги повторяются в ходе множества эпизодов (сеансов игры). На всякий случай уточню, что все элементы системы – глубокая Q-сеть, виртуальный “джойстик” и сама игра – представляют собой программы, работающие на компьютере.
Таков, по сути, алгоритм, разработанный специалистами DeepMind, хотя они прибегли к некоторым хитростям, чтобы усовершенствовать и ускорить его[188]. Сначала, пока система ничему не научилась, сеть выдает случайные выходные сигналы, и система совершает случайные игровые действия. Но постепенно, по мере того как сеть узнает веса, которые улучшают выходные сигналы, игровые навыки системы совершенствуются, часто весьма радикальным образом.
Агент за 650 миллионов долларов
Специалисты DeepMind применили свой метод глубокого Q-обучения к 49 различным играм Atari в Arcade Learning Environment. Хотя программисты DeepMind использовали для каждой игры одну и ту же архитектуру сети и одни и те же настройки гиперпараметров, их система осваивала каждую игру с нуля, то есть знания системы (веса сети), полученные при освоении одной игры, не применялись, когда система начинала обучение другой игре. Чтобы освоить каждую из игр, системе требовалось несколько тысяч обучающих эпизодов, но на мощных компьютерах процесс шел довольно быстро.
Когда глубокая Q-сеть обучилась каждой игре, специалисты DeepMind сравнили навыки машины с навыками “профессионального тестировщика игр”, которому позволили для подготовки по два часа поиграть в каждую игру. Работа мечты, скажете вы? Только если вам нравится позорно проигрывать компьютеру! Программы глубокого Q-обучения, созданные DeepMind, показали лучшие результаты, чем тестировщик, более чем в половине игр. В половине из этих игр результат программ оказался более чем в два раза лучше человеческого. В половине из этих игр результат программ был более чем в пять раз выше. Настоящего триумфа DNQ-программа добилась в игре Breakout, набирая в среднем более чем в десять раз больше очков, чем человек.
Чему именно научились эти сверхчеловеческие программы? Проанализировав результаты, специалисты DeepMind выяснили, что их программы освоили очень хитрые стратегии. Так, программа для игры в Breakout научилась применять великолепную уловку, показанную на рис. 29. Программа поняла, что если выбить кирпичи таким образом, чтобы проложить узкий тоннель у края кладки, то мяч начнет скакать между “потолком” и верхним рядом кирпичей, быстро выбивая дорогие верхние кирпичи при неизменном положении ракетки.
DeepMind впервые представила свою работу в 2013 году на международной конференции по машинному обучению[189]. Собравшиеся были поражены. Менее года спустя Google объявила о покупке DeepMind за 440 миллионов фунтов стерлингов (около 650 миллионов долларов на момент заключения сделки) – вероятно, благодаря этим результатам. Да, обучение с подкреплением порой приносит солидные награды.
Получив огромные деньги и доступ к ресурсам Google, специалисты DeepMind – которая теперь называется Google DeepMind – поставили перед собой более серьезную задачу, входящую в число “больших вызовов” ИИ: создать программу, лучше людей играющую в го. Разработанная DeepMind программа AlphaGo стала логическим продолжением долгой истории ИИ в настольных играх. Давайте для начала кратко изложим эту историю, что поможет нам понять, как работает AlphaGo и почему это так важно.
Рис. 29. Программа компании DeepMind освоила стратегию проброса мяча сквозь кирпичи при игре в Breakout, что позволило ей быстро уничтожать дорогие кирпичи верхних рядов, благодаря отскокам мяча от потолка
Шахматы и шашки
В 1949 году инженер Артур Сэмюэл поступил на работу в лабораторию IBM, расположенную в Покипси, в штате Нью-Йорк, и сразу приступил к программированию ранней версии компьютера IBM 701 для игры в шашки. Если у вас есть опыт в компьютерном программировании, вы оцените стоявшую перед ним задачу: как отметил один историк, “Сэмюэл первым решил написать серьезную программу для IMB 701, а потому не имел возможности использовать системные утилиты [то есть, по сути, не имел операционной системы!]. В частности, у него не было ассемблера, поэтому ему приходилось прописывать все операционные коды и адреса”[190]. Для читателей, не имеющих опыта в программировании, поясню: это все равно что строить дом, имея лишь ручную пилу и молоток. Созданная Сэмюэлом программа для игры в шашки стала одной из первых программ машинного обучения – и именно Сэмюэл ввел в обиход сам термин “машинное обучение”[191].
Программа Сэмюэла для игры в шашки была основана на анализе дерева игры – и такой анализ по-прежнему остается фундаментом всех программ для игры в настольные игры (включая AlphaGo, которую я опишу далее). На рис. 30 показано дерево игры в шашки. “Корнем” дерева (обычно он находится на схемах сверху, в отличие от корней настоящего дерева) служит исходное положение шашек на доске до совершения первого хода. От корня расходятся “ветки”, ведущие ко всем ходам, доступным первому игроку (здесь – черным). Возможных ходов семь (для простоты на рисунке показаны лишь три из них). Для каждого из семи возможных ходов черных есть семь возможных ответов белых (не все они показаны на рисунке) и так далее. На рис. 30 каждая доска показывает возможное положение шашек, называемое позицией на доске.
Рис. 30. Фрагмент дерева игры в шашки. Для простоты на рисунке показано всего по три возможных хода для каждой позиции на доске. Белыми стрелками показано передвижение шашки с предыдущей клетки на текущую
Представьте, что вы играете в шашки. Перед каждым ходом вы, возможно, строите в уме небольшой фрагмент этого дерева. Вы мыслите следующим образом: “Если я схожу вот так, то противник сможет сходить вот так, после чего я схожу вот так и возьму одну шашку”. Большинство людей, включая чемпионов игры, рассматривают лишь несколько возможных ходов, просчитывая лишь несколько шагов, прежде чем сделать ход. Быстрый компьютер, напротив, имеет возможность просчитывать игру гораздо дальше. Что мешает компьютеру рассмотреть все возможные ходы и определить, какая последовательность ходов ведет к победе быстрее всего? Проблема в экспоненциальном росте, пример которого мы видели в главе 3 (помните царя, мудреца и рисовые зерна?). В среднем за партию в шашки совершается около пятидесяти ходов, а это значит, что дерево игры с рис. 30 может иметь пятьдесят уровней. На каждом уровне каждая позиция на доске предполагает в среднем шесть или семь возможных ходов – следовательно, общее количество позиций в дереве может превышать шесть в пятидесятой степени, а это невероятно большое число. Гипотетическому компьютеру, который способен просматривать триллион позиций в секунду, понадобится более 1019 лет, чтобы рассмотреть все позиции единственного дерева игры. (Для наглядности это число можно сравнить с возрастом Вселенной, который составляет всего около 1010 лет.) Таким образом, полный анализ дерева игры не представляется возможным.
К счастью, для успешной игры компьютерам не нужно заниматься столь обстоятельным анализом. Обдумывая каждый ход, шашечная программа Сэмюэла создавала (в компьютерной памяти) небольшой фрагмент дерева игры, как на рис. 30. Корнем дерева служила текущая позиция на доске, и программа, используя встроенные знания правил шашек, генерировала все ходы, которые можно совершить из этой позиции. Затем она генерировала возможные ходы оппонента из каждой из итоговых позиций – и так далее, на четыре-пять ходов (“слоев”) вперед[192].
Затем программа оценивала позиции в конце упреждающего просмотра – на рис. 30 это позиции на нижнем уровне фрагмента дерева игры. Оценка позиции на доске предполагает присвоение ей числового значения ценности, которая определяет, с какой вероятностью конкретная позиция приведет к победе программы в игре. Программа Сэмюэла использовала оценочную функцию, которая присваивала очки различным элементам позиции, таким как численное преимущество черных, количество черных дамок и количество черных шашек, близких к попаданию в дамки. Сэмюэл выбрал эти элементы на основе своих знаний о шашках. Когда каждая из позиций нижнего уровня получала такую оценку, программа применяла классический алгоритм максимин, который использовал значения ценности, присвоенные в конце упреждающего просмотра, чтобы оценить ходы, непосредственно доступные программе в текущей позиции. Затем программа выбирала ход, получивший наивысшую оценку.
Предполагается, что оценочная функция работает точнее при применении к позициям, которые могут возникнуть дальше по ходу игры, и потому программа сначала анализирует все возможные последовательности ходов на несколько шагов вперед, а затем применяет оценочную функцию к итоговым позициям на доске. Затем оценки распространяются обратно по дереву с помощью максимина, который оценивает все возможные ходы из текущей позиции[193].
В процессе обучения программа узнавала, какие именно элементы позиции необходимо включать в оценочную функцию на каждом ходу, а также как взвешивать эти элементы при суммировании их оценок. Сэмюэл попробовал несколько методов обучения системы. В самом интересном варианте система училась, играя сама с собой! Этот метод обучения был довольно сложен, и я не стану описывать его в подробностях, но в некоторых аспектах он стал предтечей современного обучения с подкреплением[194].
В итоге шашечная программа Сэмюэла добилась впечатляющих результатов, сравнимых с показателями игроков “выше среднего уровня”, но не чемпионов игры. Любители назвали программу “сложным, но победимым” соперником[195]. Стоит отметить, что программа стала для IBM неожиданным подарком: на следующий день после того, как Сэмюэл представил ее на национальном телевидении в 1956 году, стоимость акций IBM взлетела на 15 %. Впоследствии компания еще несколько раз наблюдала подобное повышение стоимости акций после демонстрации игровой программы, побеждающей людей: не так давно стоимость акций IBM взлетела после привлекшего огромное количество зрителей выпуска телепрограммы Jeopardy!, в котором разработанная компанией программа Watson одержала победу над людьми.
Несомненно, шашечная программа Сэмюэла стала важной вехой в истории ИИ, но я устроила этот исторический экскурс в основном для того, чтобы на ее примере ввести три важнейших понятия: дерево игры, оценочная функция и обучение посредством игры с самим собой.
Deep Blue
Хотя “сложная, но победимая” шашечная программа Сэмюэла была выдающейся, особенно по тем временам, вряд ли можно сказать, что она заставила людей сомневаться в уникальности собственного разума. Даже если бы машина могла обыграть чемпионов по шашкам (как в итоге произошло в 1994 году[196]), мастерство в шашках никогда не считалось признаком большого ума. С шахматами все иначе. По словам Демиса Хассабиса из DeepMind, “десятки лет ведущие специалисты по информатике полагали, что с учетом традиционного статуса шахмат как мерила человеческого интеллекта умелая шахматная компьютерная программа может превзойти человека и по всем остальным показателям”[197]. Многие, включая пионеров ИИ Аллена Ньюэлла и Герберта Саймона, ставили шахматы на пьедестал. В 1958 году Ньюэлл и Саймон написали: “Если получится создать успешную шахматную машину, получится и проникнуть в самое сердце интеллектуальной деятельности человека”[198].
Шахматы значительно сложнее шашек. Так, выше я упомянула, что в шашках из каждой позиции на доске в среднем можно сделать шесть или семь ходов. В шахматах, однако, из каждой позиции можно сделать в среднем 35 ходов. В связи с этим дерево игры в шахматах гораздо больше, чем в шашках. На протяжении десятилетий шахматные программы совершенствовались синхронно с повышением скорости работы аппаратного обеспечения. В 1997 году IBM второй раз пришла к игровому триумфу с шахматной программой Deep Blue, одержавшей победу над чемпионом мира Гарри Каспаровым в матче из нескольких партий, который привлек огромное внимание общественности.
Deep Blue использовала практически такой же метод, как шашечная программа Сэмюэла: перед каждым ходом она строила фрагмент дерева игры, где корнем становилась текущая позиция на доске, затем применяла свою оценочную функцию к самому дальнему уровню дерева, а после этого с помощью максиминного алгоритма распространяла ценности обратно по дереву, чтобы решить, какой ход сделать. Основные различия между программой Сэмюэла и Deep Blue заключались в том, что Deep Blue заглядывала дальше вперед по дереву игры, использовала более сложную (ориентированную на шахматы) оценочную функцию, обладала запрограммированным шахматным знанием и работала на специальном параллельном аппаратном обеспечении, которое позволяло ей функционировать очень быстро. Кроме того, в отличие от шашечной программы Сэмюэла, Deep Blue не полагалась на машинное обучение.
Как ранее произошло с программой Сэмюэла, победа Deep Blue над Каспаровым привела к значительному повышению стоимости акций IBM[199]. Эта победа также спровоцировала большой переполох в прессе, которая принялась обсуждать последствия создания сверхчеловеческого интеллекта и выразила сомнение, что люди после этого вообще захотят играть в шахматы. Но в последующие десятилетия человечество адаптировалось к существованию Deep Blue. Как Клод Шеннон прозорливо написал в 1950 году, машина, которая превзойдет человека в шахматах, “заставит нас либо признать возможность механизированного мышления, либо дополнительно сузить нашу концепцию мышления”[200]. Случилось второе. Теперь считается, что сверхчеловеческая способность к игре в шахматы не требует общего интеллекта. Deep Blue не обладает интеллектом в том смысле, который мы сегодня вкладываем в это слово. Она умеет только играть в шахматы – и больше ничего. У нее нет представления о том, что для человека значит “игра” и “победа”. (Однажды я услышала такую фразу: “Хотя Deep Blue и победила Каспарова, она не получила от этого никакого удовольствия”.) Более того, шахматы выжили и сохранили свой статус сложной человеческой игры. Сегодня шахматисты используют компьютерные программы для тренировки, как бейсболист использует бейсбольную пушку. Можно ли сказать, что это стало результатом эволюции наших представлений об интеллекте, скорректированных благодаря прорывам в ИИ? Или же это еще один пример максимы Джона Маккарти: “Когда все работает исправно, никто уже не называет это ИИ”?[201]
Большой вызов го
Игра го существует более двух тысяч лет и считается одной из самых сложных настольных игр. Если вы никогда не играли в го, не переживайте: мои рассуждения не требуют от вас знакомства с игрой. При этом полезно знать, что го имеет серьезную репутацию, особенно в Восточной Азии, где игра невероятно популярна. “На досуге в го играют императоры и генералы, интеллектуалы и вундеркинды”, – пишет ученый и журналист Алан Левиновиц, который далее цитирует слова южнокорейского чемпиона по го Ли Седоля: “В западном мире есть шахматы, но го несравнимо изящнее и интеллектуальнее”[202].
Правила го довольно просты, но в процессе игры сложность нарастает. Совершая ход, игрок помещает камень своего цвета (черный или белый) на доску размером 19 x 19 клеток. Правила регламентируют, куда можно помещать камни и как захватывать камни противника. В отличие от шахмат, где пешки, слоны, ферзи и другие фигуры имеют иерархию, все камни го равноценны. Обдумывая ход, игрок должен быстро анализировать конфигурацию камней на доске.
Создание программы для успешной игры в го занимало специалистов по ИИ с самого зарождения отрасли. Сложность го, однако, делала эту задачу на удивление трудновыполнимой. В 1997 году, когда Deep Blue обыграла Каспарова, средние гоисты по-прежнему легко обыгрывали лучшие программы. Как вы помните, Deep Blue просчитывала значительное количество ходов с любой позиции, а затем применяла свою оценочную функцию, чтобы оценить будущие позиции, причем каждая оценка в этом случае прогнозировала, приведет ли конкретная позиция к победе. Программам го такая стратегия недоступна по двум причинам. Во-первых, размер дерева упреждающего просмотра в го значительно больше, чем в шахматах. Если шахматист выбирает в среднем из 35 возможных ходов для каждой позиции, игрок в го имеет в среднем 250 возможных ходов. Даже при наличии специального аппаратного обеспечения метод перебора, который использовала Deep Blue, не применим к дереву игры в го. Во-вторых, никто еще не создал хорошую оценочную функцию для позиций го. Иными словами, никто пока не сумел составить успешную формулу, которая анализирует позицию в го и прогнозирует, кто победит в игре. Лучшие игроки в го полагаются на свои навыки распознавания паттернов и необъяснимую интуицию.
Исследователи ИИ пока не поняли, как закодировать интуицию в оценочную функцию. Именно поэтому в 1997 году – в тот же год, когда Deep Blue обыграла Каспарова, – журналист Джордж Джонсон написал в The New York Times: “Когда или если компьютер одержит победу над чемпионом по го, это станет знаком, что искусственный интеллект действительно начинает приближаться к настоящему”[203]. Звучит знакомо – то же самое раньше говорили о шахматах! Джонсон процитировал прогноз одного энтузиаста го: “Возможно, пройдет сто лет, прежде чем компьютер победит человека в го, а возможно, и того больше”. Всего через двадцать лет AlphaGo, которая научилась играть в го с помощью глубокого Q-обучения, одержала победу над Ли Седолем в матче из пяти партий.
AlphaGo против Ли Седоля
Прежде чем я объясню, как работает AlphaGo, давайте вспомним ее блестящую победу над Ли Седолем, одним из лучших гоистов в мире. Даже увидев, как полугодом ранее AlphaGo обыграла чемпиона Европы Фана Хуэя, Ли не усомнился в своей победе: “Думаю, уровень [AlphaGo] не сравнить с моим… Конечно, в последние четыре-пять месяцев программу сильно усовершенствовали, но этого времени недостаточно, чтобы бросить мне вызов”[204].
Возможно, вы были среди более двухсот миллионов человек, которые в марте 2016 года посмотрели хотя бы фрагмент матча в прямом эфире. Уверена, такой аудитории не собирала ни одна партия в го за все двадцать пять веков ее истории. После первой партии вы, возможно, разделяли чувства потерпевшего поражение Ли: “Признаюсь, я поражен… Я не ожидал, что AlphaGo будет играть безупречно”[205].
“Безупречная” игра AlphaGo включала множество ходов, которые удивляли и восхищали комментаторов матча. В разгар второй партии AlphaGo сделала ход, который ошеломил даже лучших экспертов по игре. В Wired писали:
Сначала Фан Хуэй [вышеупомянутый чемпион Европы по го] счел этот ход довольно странным. Но затем он разглядел его красоту. “Это не человеческий ход. Я никогда не видел, чтобы человек походил таким образом, – говорит он. – Это очень красиво”. Он не перестает повторять это слово. Красиво. Красиво. Красиво… “Это очень неожиданный ход”, – сказал один из англоязычных комментаторов, также весьма талантливый игрок в го. Другой, усмехнувшись, признался: “Я решил, что это ошибка”. Но, пожалуй, сильнее всех удивился Ли Седоль, который поднялся и вышел из зала. “Ему пришлось выйти, чтобы освежиться и взять себя в руки”, – сказал первый комментатор[206].
В The Economist о том же ходе написали: “Любопытно, что порой мастера го делают подобные ходы. Японцы называют их kami no itte («рукой бога», или «божественными ходами»)”[207].
AlphaGo выиграла эту партию и следующую. В четвертой партии Ли сделал свой kami no itte, который показывает сложность игры и силу интуиции лучших игроков. Ход Ли удивил комментаторов, но они сразу распознали в нем приговор противнику. “AlphaGo, однако, не поняла, что происходит, – написал один комментатор. – Она не сталкивалась с подобным… в миллионах партий, сыгранных с самой собой. На послематчевой пресс-конференции Седоля спросили, о чем он думал, когда сделал этот ход. Он ответил, что не смог разглядеть никакого другого хода”[208].
Четвертую партию AlphaGo проиграла, но пятую выиграла. Победа в матче осталась за ней. В прессе снова разгорелись дискуссии, похожие на те, что велись после победы Deep Blue над Каспаровым, и многие рассуждали о том, что победа AlphaGo значит для будущего человечества. Но это было даже важнее триумфа Deep Blue: ИИ справился с более сложной задачей, чем шахматы, и сделал это гораздо более впечатляющим образом. В отличие от Deep Blue, AlphaGo получила свои навыки благодаря обучению с подкреплением во время игры с самой собой.
Демис Хассабис отметил, что “лучших игроков в го отличает интуиция” и “в AlphaGo [мы] с помощью нейронных сетей внедрили, если хотите, именно этот аспект интуиции”[209].
Как работает AlphaGo
Поскольку существовало несколько версий AlphaGo, чтобы различать их, в DeepMind стали называть их по именам чемпионов, которых победила программа, – AlphaGo Fan и AlphaGo Lee, – что навевает мне образ черепов поверженных врагов в коллекции цифрового викинга. Уверена, в DeepMind не хотели таких ассоциаций. Как бы то ни было, и AlphaGo Fan, и AlphaGo Lee использовали сложную комбинацию глубокого Q-обучения, “поиска по дереву методом Монте-Карло”, обучения с учителем и специальных знаний го. Через год после матча против Ли Седоля в DeepMind разработали новую версию программы, которая оказалась одновременно проще и совершеннее предыдущих. Новая версия получила название AlphaGo Zero, потому что в отличие от предыдущей начала обучение, имея ноль знаний о го, не считая правил игры[210]. AlphaGo Zero выиграла сто из ста партий против AlphaGo Lee. Кроме того, специалисты DeepMind применили те же методы (хотя с другими сетями и другими встроенными правилами игры), чтобы научить систему играть в шахматы и сёги (или японские шахматы)[211]. Авторы назвали набор этих методов AlphaZero. В настоящем разделе я опишу, как работала AlphaGo Zero, но для краткости буду называть эту версию просто AlphaGo.
Слово “интуиция” окружено ореолом таинственности, но интуиция AlphaGo (если называть ее именно так) рождается из комбинации глубокого Q-обучения и “поиска по дереву методом Монте-Карло”. Давайте разберемся, что скрывается за этим громоздким названием. В первую очередь в глаза бросается “Монте-Карло”. Конечно, Монте-Карло – это фешенебельный район расположенного на Лазурном берегу крошечного княжества Монако, которое славится модными казино и автомобильными гонками и часто появляется в фильмах о Джеймсе Бонде. Но в естественных науках и математике методом Монте-Карло называют семейство компьютерных алгоритмов, которые были впервые использованы в рамках Манхэттенского проекта по разработке атомной бомбы. Своим названием метод обязан идее о том, что компьютер может использовать некоторую степень случайности – как при вращении легендарной рулетки в казино Монте-Карло – при решении сложных математических задач.
Поиск по дереву методом Монте-Карло разработан специально для игровых компьютерных программ. Подобно оценочной функции Deep Blue, поиск по дереву методом Монте-Карло применяется для присвоения оценки каждому возможному ходу из конкретной позиции на доске. Однако, как я упоминала выше, в го неприменим обстоятельный упреждающий просмотр и пока еще не создана надежная оценочная функция. Поиск по дереву методом Монте-Карло работает иначе.
Рис. 31. Схема поиска по дереву методом Монте-Карло
На рис. 31 показана схема поиска. Взгляните сначала на рис. 31A. Черным кружком на нем обозначена текущая позиция на доске, то есть конфигурация камней на доске на момент текущего хода. Допустим, программа играет в го черными и наступает очередь черных ходить. Для простоты допустим, что у черных есть три возможных хода, показанные тремя стрелками. Какой ход выбрать черным?
Если бы у черных было достаточно времени, они могли бы осуществить “полный поиск” по дереву игры: просчитать все возможные последовательности ходов и выбрать ход, который с наибольшей вероятностью приведет их к победе. Но в го такой обстоятельный поиск невыполним: как я уже упоминала, даже всего времени с момента рождения Вселенной недостаточно, чтобы провести полный поиск по дереву игры в го. Применяя метод Монте-Карло, черные просматривают лишь малую часть возможных последовательностей после каждого хода, подсчитывают количество побед и поражений, к которым ведут эти гипотетические последовательности, и на основе полученных результатов присваивают оценку каждому доступному ходу. Вдохновленная рулеткой случайность нужна, чтобы оценить возможные ходы.
В частности, чтобы выбрать ход из текущей позиции, черные “представляют” (то есть испытывают) несколько возможных сценариев развития игры, как показано на рис. 31B – D. В каждом испытании черные начинают с текущей позиции, случайно выбирают один из доступных ходов, затем (с новой позиции) случайно выбирают ход противника (белых) и так далее, пока моделируемая партия не закончится победой или поражением черных. Такое испытание, начинающееся с конкретной позиции на доске, называется разверткой с этой позиции.
На рисунке видно, что в трех развертках черные один раз победили и два раза проиграли. Теперь черные могут оценить все доступные ходы с текущей позиции на доске (рис. 31E). Ход 1 (левая стрелка) фигурировал в двух развертках, одна из которых закончилась победой, поэтому он получает оценку 1 из 2. Ход 3 (правая стрелка) фигурировал в одной развертке, которая закончилась поражением, поэтому он получает оценку 0 из 1. Ход 2 (центральная стрелка) вообще не проверялся, поэтому он получает оценку 0. Кроме того, программа ведет такую же статистику для всех промежуточных ходов в развертках. Когда очередной раунд поиска по дереву методом Монте-Карло заканчивается, программа использует скорректированные оценки, чтобы решить, какой из доступных ходов кажется наиболее перспективным (здесь – ход 1). Затем программа совершает этот ход в игре.
Я сказала, что в развертке программа выбирает ходы для себя и противника случайным образом, но на самом деле она делает вероятностный выбор, ориентируясь на оценки, которые эти ходы получали в предыдущих раундах поиска по дереву методом Монте-Карло. Когда каждая развертка заканчивается победой или поражением, алгоритм корректирует все оценки сделанных в этой партии ходов, чтобы отразить результат.
Сначала программа выбирает ходы из конкретной позиции на доске случайно (выполняя операцию, эквивалентную вращению рулетки), но в процессе моделирования других разверток, получая дополнительную статистику, все больше склоняется к выбору тех ходов, которые чаще всего приводили к победным разверткам.
Таким образом, алгоритму поиска по дереву методом Монте-Карло не приходится гадать, какой ход с наибольшей вероятностью приведет к победе, ориентируясь лишь на текущую позицию: он использует развертки для сбора информации о том, как часто конкретный ход действительно приводит к победе или поражению. Чем больше разверток строит алгоритм, тем надежнее статистика. Как и раньше, программе необходимо найти баланс между использованием (выбором ходов, получивших самую высокую оценку при развертке) и исследованием (периодическим выбором ходов с низкой оценкой, для которых у программы еще мало статистических данных). На рис. 31 я показала три развертки, но в AlphaGo поиск по дереву методом Монте-Карло строил около двух тысяч разверток при каждом ходе.
Поиск по дереву методом Монте-Карло изобрели не специалисты по компьютерным наукам из DeepMind. Его предложили применить к деревьям игр в 2006 году, и это позволило значительно расширить способности программ для игры в го. Но этим программам оставалось не под силу победить людей. Одна из проблем заключалась в том, что накопление достаточной статистики из разверток занимает немало времени – особенно в го, где существует огромное количество допустимых ходов. Специалисты DeepMind поняли, что могут усовершенствовать систему, дополнив поиск по дереву методом Монте-Карло глубокой сверточной нейронной сетью. AlphaGo сообщает текущую позицию на доске обученной глубокой СНС, которая берет ее в качестве входного сигнала и присваивает расчетные значения ценности всем допустимым из этой позиции ходам. Затем поиск по дереву методом Монте-Карло использует эти значения ценности в качестве отправной точки: вместо того чтобы сначала выбирать ходы случайным образом, он рассматривает выходные сигналы сверточной сети в качестве индикатора предпочтительности начальных ходов. Представьте, что вы AlphaGo и смотрите на доску: прежде чем вы запустите процесс построения разверток из текущей позиции по методу Монте-Карло, сверточная сеть шепнет вам на ухо, какие допустимые из этой позиции ходы, вероятно, окажутся лучшими.
Результаты поиска по дереву методом Монте-Карло, в свою очередь, используются для обучения нейронной сети. Представьте, что вы AlphaGo и уже осуществили поиск. Его результатами стали новые вероятности, присвоенные всем вашим допустимым ходам на основе того, как часто эти ходы приводили к победам или поражениям в построенных развертках. Далее новые вероятности используются для корректировки выходного сигнала сверточной сети с помощью метода обратного распространения ошибки. Затем вы с противником выбираете ходы, после чего позиция на доске меняется – и процесс продолжается. По сути, СНС учится распознавать паттерны, прямо как мастера го. В конце концов сеть начинает играть роль “интуиции” программы, которая подкрепляется поиском по дереву методом Монте-Карло.
Как и ее предшественница, шашечная программа Сэмюэла, AlphaGo учится, играя сама с собой и проводя огромное количество партий (около пяти миллионов). Во время обучения веса сверточной нейронной сети корректируются после каждого хода на основе различий между выходными ценностями сети и уточненными ценностями после проведения поиска по дереву методом Монте-Карло. Затем, когда AlphaGo играет с человеком вроде Ли Седоля, обученная СНС на каждом ходе присваивает ценности, которые становятся отправными точками для поиска.
Создав AlphaGo, специалисты DeepMind продемонстрировали, что один из давних больших вызовов ИИ покорился хитроумной комбинации обучения с подкреплением, сверточных нейронных сетей и поиска по дереву методом Монте-Карло (а также мощной современной вычислительной техники). В результате AlphaGo заняла заслуженное место в пантеоне ИИ. Но что дальше? Научится ли эта действенная комбинация методов генерализации за пределами игрового мира? Об этом я расскажу в следующей главе.