Чемпион мира Гарри Каспаров победил компьютер IBM Deep Blue в 1996 году, но потерпел поражение в 1997 году, проиграв со счётом 4 к 2.
Произошедшая в 1997 году победа компьютера IBM Deep Blue над гроссмейстером и чемпионом мира Гарри Каспаровым считается триумфальным водоразделом в истории технологий, сравнимым с высадкой на Луну. Кажется, что она продемонстрировала, что компьютеры могут побеждать людей в том, что считалось свойственным только нам: в мышлении1. Технологии символического ИИ, которые использовались компьютером DeepBlue, сегодня считаются устаревшими, особенно для более сложных игр наподобие го, которая была изобретена в Китае две с половиной тысячи лет назад. Но в 2016 году чемпиона мира по го Ли Седоля победила система ИИ AlphaGo подразделения Google DeepMind. Это событие исследователь и венчурный капиталист Ли Кайфу назвал «моментом „Спутника“» для Китая2: он считает, что именно оно заставило Китай вложить миллиарды долларов в исследования ИИ, чтобы догнать и, возможно, даже перегнать США. Победа AlphaGo иллюстрирует расцвет новой парадигмы ИИ — глубокого обучения и нейронных сетей, ставшей основой современной революции искусственного интеллекта.
Почему игры наподобие шахмат и го были столь важны в истории ИИ? Пионеры исследований искусственного интеллекта, среди которых были Герберт Саймон, Аллен Ньюэлл, Джон Маккарти и Марвин Минский, рассматривали интеллект человека сквозь традиционную призму западной философии, основы которой заложил ещё Аристотель. Этот маскулинный, евроцентричный взгляд на интеллект, корнями уходивший в декартово разделение мышления и тела, отдавал приоритет мозговым навыкам — логике, математике и способности решать задачи в ущерб телесным, эмоциональным, социальным и культурным формам интеллекта. Они считали, что если Разум (т.е. Логика) отличает Человека от Зверя, то именно Логика должна быть основой интеллекта.
Блез Паскаль был философом и математиком. В 1640-х он изобрёл в помощь своему отцу, сборщику налогов, машину, способную выполнять сложение.
Многие западные философы и математики, от Блеза Паскаля до Джорджа Буля и Бертрана Рассела, стремились или сделать вычисления/логику, которые они приравнивали к самой мысли, более строгими математически (более «формальными»), или предпринять ещё один шаг — механизировать их. Сам Паскаль изготовил для этих целей вычислительную машину, а кульминацией этого импульса западной мысли стало изобретение в 20-м веке цифрового компьютера. Пионеры изучения ИИ 1950-х и 1960-х рассматривали игры как ещё один способ демонстрации людьми интеллекта решением задач. Если бы исследователям ИИ удалось бы имитировать то, как это делают игроки, то они бы смогли автоматизировать этот процесс. Отрасль математики под названием «теория игр», применяемая в экономике и военном деле, была основана математиком и компьютерным пионером Джоном фон Нейманом; она обеспечила оптимизацию стратегий и алгоритмов, широко применяемых в компьютерных науках. Пионер исследования ИИ Герберт Саймон применял данные теории и в информатике, и в экономике (в этой области он получил Нобелевскую премию). Следовательно, мысль о том, что игры могут серьёзно моделировать аспекты реального мира, была центральной на ранних этапах развития компьютерных наук. В частности, поскольку первые компьютеры испытывали трудности с моделированием сложности реального мира, игры считались упрощённым «микромиром», ограничения и правила которого хорошо понятны компьютерам, обеспечившим возможность быстрого прогресса в 1960-х.
Шахматный автомат Вольфганга фон Кемпелена «Турок», управлявшийся спрятанным внутри живым игроком.
Шахматы, в частности, исторически считались на Западе вершиной интеллектуальной деятельности. Это была интеллектуальная игра, ассоциирующаяся с логикой и стратегией. Вспомните мистера Спока из «Звёздного пути», побеждающего игроков-людей в 3D-шахматы. Даже в 18-м веке европейская элита была восхищена идеей машин, способных играть в шахматы. Вольфганг фон Кемпелен получил известность благодаря своему «Механическому турку» — шахматному автомату, изготовленному для австрийской императрицы Марии-Терезии и победившему Бенджамина Франклина и Наполеона. Позже выяснилось что «турок» был фальшивкой и внутри него прятался живой игрок; тем не менее, он поразил воображение Эдгара Аллана По и Чарлза Бэббиджа. Интерес к шахматам как к показателю интеллекта распространился и на математиков, заложивших теорию вычислений в 20-м веке: Алана Тьюринга, Клода Шеннона, Джона фон Неймана, Норберта Винера и, разумеется, на пионеров ИИ Герберта Саймона, Аллена Ньюэлла и Джона Маккарти. В частности, Ньюэлл и Саймон считали шахматы образцовой задачей для ИИ, идеально подходящей для предпочитаемого ими решения: поиска.
В 1947 году первопроходец в области компьютерных наук Алан Тьюринг разработал свою первую теоретическую шахматную программу как пример машинного интеллекта.
Исследователь MIT и Bell Labs Клод Шеннон (справа) разработал современную теорию информации и опубликовал в 1950 году первую статью о том, как писать компьютерные шахматные программы. Также он создал в MIT эту шахматную машину на основе реле (на фото). Слева чемпион по шахматам Эд Ласкер (прибл. 1950 год).
Бетти и Клод Шенноны на третьем Чемпионате мира по компьютерным шахматам в Линце, Австрия, 1980 год.
В поисках решения
Что такое поиск, и как его можно использовать при игре в шахматы? В контексте ИИ под поиском подразумевается не поиск текста в вебе с помощью Google (хотя движок веб-поиска может использовать понятие поиска в контексте ИИ). В сфере ИИ под поиском подразумевают процесс проб и ошибок при обходе возможных путей решения задачи. Поиск — это один из фундаментальных методов классического ИИ, также известного как «символический» ИИ, потому что такие методы включают в себя манипуляции со списками символов, например, как при решении задач алгебры. Все виды процессов решения задач, например, доказательство теорем, решение головоломок, игры и движение по лабиринту, включают в себя принятие решения о том, что попробовать в первую очередь. Такие варианты выбора можно смоделировать в виде дерева разветвляющихся решений.
Иллюстрация решения произвольного дерева игры.
Минимакс
Ветвящееся дерево решений игры в крестики-нолики. Как и в шахматы, а также во множество других игр на двух игроков, в крестики-нолики можно играть при помощи алгоритма «минимакс».
Допустим, нам нужно создать робомышь, ищущую выход из лабиринта (примерно этим занимался Клод Шеннон в 1950 году). Если она попадает на перекрёсток с четырьмя дверьми, то может двигаться вправо, вперёд и влево, но ей запрещается возвращаться назад. Так мы получаем три возможных варианта выбора. Компьютерные учёные сказали бы, что мышь имеет «коэффициент ветвления», равный 3. Простейший способ программирования компьютера для прохождения (решения) лабиринта заключался бы в проверке по очереди каждого варианта, или ветви. Это называется поиском методом «грубого перебора» (brute force): мы тестируем каждый вариант. Однако наша мышь, разумеется, попадёт на ещё один перекрёсток, прежде чем ей предоставится возможность вернуться, чтобы проверить все остальные варианты на первом перекрёстке. Каждый раз, когда она достигает нового перекрёстка, мышь может выбрать между ещё тремя новыми путями. Мы можем задать количество перекрёстков, которое мышь может обыскать в глубину, прежде чем вернуться назад и попробовать другой путь.
Клод Шеннон передвигает свою электрическую мышь в лабиринте (прибл. 1952 год).
Это называется глубиной поиска, а в контексте игр — «упреждающим просмотром» (look ahead). Как видите, количество путей, которые необходимо обыскать мыши, очень быстро нарастает: как 3 (коэффициент ветвления), умножаемый на себя же столько раз, сколько мы упреждающе проверяем в дереве решений. Другими словами, задача растёт экспоненциально. В отрасли ИИ это часто называют проблемой «комбинаторного взрыва».
Шахматная доска в первых теориях
Подобный метод можно использовать и в шахматах. На каждом ходе игрока у нас есть выбор из максимум 38 возможных допустимых ходов, то есть шахматная задача имеет коэффициент ветвления 38. Для выбора лучшего из этих 38 ходов используется количественный метод оценки относительной выгоды одной шахматной позиции по сравнению с другой. Это называется «оценочной функцией». Среднестатистическая партия в шахматы проходит за 42 хода, и поскольку игроков двое, это нужно умножить на два, что даёт нам приблизительно 3884 — больше, чем количество звёзд во Вселенной. Ещё на ранних этапах истории ИИ стало понятно, что такой поиск грубым перебором шахмат и других задач просто не сработает на оборудовании того времени; вариантов слишком много, а компьютеры слишком слабы. Клод Шеннон одним из первых использовал алгоритм «минимакс» в компьютерной шахматной программе (этот алгоритм и сегодня является основой большинства шахматных программ), заметив, что благодаря человеческому знанию и опыту в игре можно быстро отсечь множество ветвей, не рассматривая их. Герберт Саймон и Аллен Ньюэлл предложили использовать «эвристики», или эмпирические правила, которые люди частью используют при решении задач; чаще всего они срабатывают, но это случается не всегда. Эвристики — это тот вид человеческого знания, который можно запрограммировать в компьютер.
Шахматы
Шахматы имеют намного больше ветвей в своём дереве решений, чем крестики-нолики. Подсчитано, что количество вариантов шахматных партий примерно равно 10120, а это больше, чем количество атомов во Вселенной.
Bounded Lookahead
Учитывая огромное количество ветвей, шахматные программы могут заглядывать вперёд по дереву поиска только на конечную глубину, иначе перебор будет длиться вечно.
Одной такой эвристикой, доказавшей свою полезность в шахматах, является «альфа-бета-отсечение«. Это означает, что если программа определила, что одному из ходов может с лёгкостью противодействовать противник, то другие способы, которыми он может противодействовать тому же ходу, искать не нужно. Дальнейший поиск по этому пути можно игнорировать, отсекая всю эту ветвь от дерева решений. Это может значительно уменьшать коэффициент ветвления, с 38 до 6, а иногда и до 3. Кроме того, учитывая ограничения компьютеров того времени, большинство программ могли заглядывать только на 4 хода вперёд. Одна из первых шахматных программ, способных компетентно играть против любителей, была создана приблизительно в 1959-1962 гг студентом MIT Аланом Котоком под руководством Джона Маккарти. В программе Котока-Маккарти использовалось альфа-бета-отсечение.
Джон Маккарти, играющий в шахматы на IBM 7090 Стенфордского университета. Маккарти использовал усовершенствованную версию программы Котока для игры в шахматы по переписке с советской программой, разработанной в московском Институте теоретической и экспериментальной физики Георгием Адельсоном-Вельским и его коллегами. В 1967 году матч из четырёх партий, продолжавшийся в течение девяти месяцев, был выигран со счётом 3-1 советской программой.
История Алана Котока из первых уст
В 1959 году первокурсники MIT Алан Коток, Элвин Р. Берлекамп, Майкл Либерман, Чарльз Ниссен и Роберт А. Вагнер начали работу над шахматной программой на основе исследований пионера искусственного интеллекта Джона Маккарти. Ко времени их выпуска в 1962 года программа уже могла выигрывать у любителей.
Ньюэлл и Саймон считали, что все задачи ИИ, например, шахматы, можно решить поиском в сочетании с эвристиками, или «эвристическим поиском». Эвристический поиск был центральной идеей, лежавшей в основе первых прорывов Ньюэлла и Саймона — программ Logic Theorist и General Problem Solver, а также стал важнейшим столпом в их теории о том, что интеллект и людей, и машин заключается в простой манипуляции символами, фундаментальными строительными кирпичиками математики и языка. Эта гипотеза «физической системы символов» стала тем предположением, на котором был основан весь проект символического искусственного интеллекта, от его зарождения в 1950-х до начала 2000-х. Эта теория, постулировавшая эквивалентность «мозга» компьютеров и человека, стала чрезвычайно влиятельной и в когнитивной психологии, а в позже даже попала в популярную культуру благодаря произведениям в жанре «киберпанк», в которых люди могли загружать свои мозги в Интернет или заменять их чипами.
Пионеры исследований искусственного интеллекта Аллен Ньюэлл (справа) и Герберт Саймон, которые совместно с Клиффом Шоу разработали такие ИИ-программы, как Logic Theorist, General Problem Solver и шахматную программу NSS (в которой использовалась аппроксимация альфа-бета-отсечения). Все эти программы работали на компьютере JOHNNIAC корпорации RAND.
Компьютеры становились быстрее, а компьютерные учёные, сами бывшие опытными игроками в шахматы, например, Ричард Гринблатт и Ханс Берлинер, создавали собственные шахматные программы. Они выяснили, что первые шахматные программы (например, написанная Котоком) играли чрезвычайно плохо, и добавили в свои программы собственные знания о том, как живые игроки подходят к игре; эти знания приняли форму дополнительных эвристик для улучшения оценки позиций фигур, баз данных дебютных ходов и эндшпилей, а также распознавателей паттернов игрового поля. Однако со временем выяснилось, что шахматные программы, запущенные на более быстрых компьютерах или на специализированном оборудовании, способны выигрывать у программ, в которые встроен большой объём человеческих знаний. Так получилось, потому что ни одна эвристика не идеальна и не может учесть все ситуации. Иногда гениальные ходы возникают потому, что игрок пробует сделать нечто, что большинство людей посчитало бы плохим ходом. Большинство эвристик отсекло бы такой ход без дальнейшего поиска, а значит, программы, использующие человеческие знания, никогда бы не сделали такой ход.
Ханс Берлинер (на заднем плане), Мюррей Кэмпбелл (слева) и Фэн Сюн Сюй на 20-м ежегодном Чемпионате по компьютерным шахматам ACM в Рино, Невада. Первое место поделили две команды — HiTech (команда Берлинера) и Deep Thought (команда Кэмпбелла и Сюя); обе они представляли Университет Карнеги — Меллона. Трёх участников команды Deep Thought (в том числе Кэмпбелла и Сюя) позже наняла компания IBM для создания Deep Blue.
Когда компьютеры стали быстрее, они смогли заглядывать вперёд более глубоко, на 6, 7, 8 ходов, с лёгкостью побеждая программы, прогнозировавшие всего на 4 хода вперёд. Был обнаружен более эффективный алгоритм поиска, называющийся «поиском с итеративным углублением»; он мог постепенно увеличивать глубину поиска по тому пути, который выглядел наиболее перспективным. Впервые он был применён в Chess 4.53 Дэвида Слейта и Ларри Эткинса — первой программе, выигравшей в 1976 году в человеческом турнире по шахматам. Увеличение объёма памяти также позволило программам сохранять ранее рассмотренные позиции, ещё сильнее уменьшая объём необходимых поисков. Всеми этими инновациями (альфа-бета-отсечение, итеративное углубление, сохранение проверенных позиций и базы данных дебютов и эндшпилей) свободно обменивались разработчики шахматных программ на турнирах по компьютерным шахматам, поэтому они стали стандартными приёмами.
В 1977 году Кен Томпсон (более известный как соавтор операционной системы Unix) и Джо Кондон из Bell Laboratories спроектировали Belle — специализированную машину для игры в шахматы. Специализированное шахматное оборудование Belle и база данных эндшпилей совершили революцию в компьютерных шахматах.
Один из разработчиков Belle Кен Томпсон на 13-м Североамериканском чемпионате по компьютерным шахматам. Специализированная шахматная машина Belle победила в турнире, а второе место заняла программа Cray Blitz. С 1970 по 1994 годы Ассоциация вычислительной техники (Association for Computing Machinery, ACM) проводила ежегодные компьютерные шахматные турниры с целью создания платформы для обмена идеями.
На протяжении 1980-х Belle, разработанная Кеном Томпсоном и Джо Кондоном из Bell Labs, была сильным соперником на шахматных турнирах. На фото показаны шахматные программы Belle и CHAOS на WCCC 1980 года, проводившейся в Линце, Австрия. Belle играла с программой CHAOS Университета Мичигана в примерно равном по силам матче и победила.
Belle сражается с Chess 4.0 на 4-м Чемпионате мира по компьютерным шахматам (WCCC), проводившемся в Нью-Йорке в 1983 году. На заднем плане слева направо: Кен Томпсон, Фредерик Фриндел и Джо Кондон. На переднем плане слева направо: разработчики Chess Дэвид Слейт и Уильям Бланчард. Турнир выиграла работавшая на суперкомпьютере шахматная программа Cray Blitz, второе место заняла Bebe.
Несмотря на прогресс программного обеспечения, с ростом скоростей компьютеров в 1970-х шахматные программы автоматически становились лучше без каких-либо инноваций в ПО. К 1980-м годам доминирующим фактором прогресса в компьютерных шахматах стало использование оборудования для ускорения поиска. Они превратились в задачу проектирования компьютеров, а не задачу для ИИ. В 1997 году Deep Blue по-прежнему в основном использовал те же программные приёмы, что и шахматные программы за 20 лет до него; тем не менее, ему удалось победить Каспарова в основном благодаря тому, что он был быстрым компьютером со множеством специализированных параллельных процессоров. В каком-то смысле, в процессе роста скорости компьютеров шахматные программы становились менее интеллектуальными.
Печатная плата Deep Thought I, 1988 год. Специализированная шахматная машина Deep Thought, разработанная студентами Университета Карнеги — Меллона, стала предшественницей Deep Blue.
Deep Blue.
Команда разработчиков IBM Deep Blue (Джо Хоун, Джоел Бенджамин, Джерри Броди, Фэн Сюн Сюй, С. Дж. Тан и Мюррей Кэмпбелл).
Гарри Каспаров пожимает руку Фэн Сюн Сюю в первой повторной игре 1997 года против Deep Blue (Нью-Йорк).
В 1980-х поиск в глубину как доминирующая тематика в исследованиях ИИ уже находилась в упадке. Начиная с 1960-х, такие исследователи, как Эд Фейгенбаум из Стэнфорда, создавали так называемые «экспертные системы», в которых большие объёмы экспертных человеческих знаний вкладывались в программы ИИ в виде правил if-then. Как и в случае с первыми эвристическими программами, эти правила программировались в код ПО, но в отличие от эвристических систем, «базы знаний» отделялись от логических частей программы («машин вывода»). Фейгенбаум и другие приверженцы экспертных систем утверждали, что «знание — сила». Другими словами, они считали, что большая база знаний компенсирует отсутствие сложных рассуждений: чем больше знаний, тем меньше поиска, и наоборот.
Тигр в клетке: применение систем баз знаний, лекция Эдварда Фейгенбаума, 1993 год
Обсуждение истории ИИ на AAAI-17: экспертные системы, 2017 год
В 1980-х экспертные системы породили множество коммерческих компаний. Вся эта деятельность почти никак не коснулась шахматных программ, которые в то время разворачивались в другом направлении: обратно к поиску грубым перебором при помощи специализированного оборудования. Ведущими шахматными машинами этого типа были Belle Кена Томпсона из Bell Labs и два отдельных проекта Университета Карнеги — Меллона: HiTech Ханса Берлинера с Фэн Сюн Сюем и Deep Thought Мюррея Кэмпбелла, который позже превратился в Deep Blue компании IBM. То есть к моменту, когда машина победила Каспарова, шахматные программы уже практически перестали быть связанными с общей сферой исследования ИИ, хоть и обеспечивали хорошую рекламу.
Однако бОльшую тревогу вызывало то, что к началу 1990-х подвергся атаке проект символического ИИ, основанный на гипотезе физической системы символов Ньюэлла и Саймона. Его критики, в частности, философ Хьюберт Дрейфус, начали подвергать сомнению проект символического ИИ ещё в 1960-х, обосновывая это тем, что философское предположение о разделённости мозга и тела было неверным и устаревшим. Философы 20-го века, например, Мартин Хайдеггер, утверждали, что человеческую мысль невозможно отделить от телесного опыта и непосредственного культурного окружения субъекта.
Исследователи ИИ очень резко реагировали на критику Дрейфуса (впрочем, он и сам был не особо дипломатичен): ведущие авторитеты в области ИИ угрожали журналам, когда те публиковали работы Дрейфуса. Они злорадствовали, когда Дрейфуса, который не очень хорошо играл в шахматы, победила шахматная программа MacHack Ричарда Гринблатта. Однако успех программ в шахматах не доказывал ошибочности критики Дрейфуса. На самом деле, сам факт того, что шахматные программы наподобие Deep Blue использовали поиск грубым перебором, означал, что они не играют особой роли в более масштабном проекте создания ИИ общего назначения. Драма оглушительного поражения Каспарова превозносилась как веха победы Машин над Человеком, но на самом деле это был триумф инженеров Deep Blue над одним игроком в шахматы. И создатели Deep Blue не утверждали, что их компьютер обладал интеллектом. Они говорили: если бы в здании начался пожар, то Каспаров был бы достаточно умён, чтобы убежать, а машина осталась бы на месте. И хотя ранее пионер ИИ Джон Маккарти считал шахматы главной задачей ИИ, после победы Deep Blue он критиковал шахматы за то, что с их помощью не удалось разработать ни одной новой теории о том, как можно имитировать человеческий интеллект.
СМИ изображали повторную игру 1997 года между чемпионом мира по шахматам Гарри Каспарова и специализированного суперкомпьютера IBM Deep Blue как битву между человеком и машиной. На обложке Newsweek её назвали «Последней линией обороны мозга». Подобные взгляды преувеличивали мощь компьютера и минимизировали труд людей, создавших саму машину.
К началу 1990-х исследователи начали воспринимать критику Дрейфуса серьёзно и стали придумывать новые виды ИИ, например такие, которые подчёркнуто имеют тело, типа роботов Родни Брукса4, или те, которые имеют дело с эмоциями. Как мы увидим во второй части статьи, в 2000-х заменять символический ИИ начинает совершенно другая традиция ИИ, называемая машинным обучением. Машинное обучение способно выполнять задачи, с которыми символический ИИ никогда не умел справляться лучше человека, например, распознавание лиц или понимание человеческой речи. Это же относится и к игре, в которую машины не могли конкурентоспособно играть при помощи эвристического поиска, а именно к го.
Тем не менее, хотя поиск потерял своё величие в качестве основной методики ИИ, он никогда не терял своей пользы в более широкой области компьютерных наук. Был достигнут значительный прогресс в совершенствовании алгоритмов поиска для оптимального и эффективного решения задач. Эта методика настолько фундаментальна, что создание деревьев решений и поиск по ним распространены чрезвычайно широко; почти невозможно перечислить все программы, в которых она используется.
Поиск играет определённую роль в любой задаче получения информации, от выполнения запросов к базам данных до поиска по вебу. Алгоритм поиска A*, впервые изобретённый для робота Shakey института SRI, повсеместно используется для построения маршрутов для автономных транспортных средств и GPS-приложений. И даже сегодня ИИ-программы, играющие в игры при помощи машинного обучения, применяют разные виды поиска, пусть он и не является больше самым интересным их компонентом. Однако, как и другие техники, которые раньше считались «искусственным интеллектом», современный поиск считается просто ещё одной базовой компьютерной техникой, не более интеллектуальной, чем обычная программа. Это иллюстрирует исторический паттерн развития ИИ: как только он становится стандартным и автоматическим, люди больше не считают его «интеллектом». Раньше когда говорили об «ИИ», то, скорее всего, имели в виду поиск. Когда «ИИ» упоминают сегодня, то обычно подразумевается преемник символического ИИ — машинное обучение.
Во второй части статьи мы расскажем о революции, совершённой в искусственном интеллекте машинным обучением, о глубине различий глубинного обучения от поиска и символического ИИ, а также о том, как AlphaGo компании DeepMind использовал глубинное обучение для победы над чемпионом мира по го Ли Седолем.
Примечания
1. Nathan Ensmenger, “Is Chess the Drosophila of Artificial Intelligence? A Social History of an Algorithm,” Social Studies of Science 42, no. 1 (February 2012): 22, https://doi.org/10.1177/0306312711424596.
2. Kai-Fu Lee, AI Superpowers: China, Silicon Valley, and the New World Order. (Boston; New York: Houghton Mifflin Harcourt, 2019), 1–5.
3. Stuart J. Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd ed., Prentice Hall Series in Artificial Intelligence (Upper Saddle River, NJ: Pentice Hall, 2010), 110.
4. Rodney A. Brooks, “Elephants Don’t Play Chess,” Robotics and Autonomous Systems, Designing Autonomous Agents, 6, no. 1 (June 1, 1990): 3–15, https://doi.org/10.1016/S0921-8890(05)80025-9.
На правах рекламы
Если для работы необходимы серверы с мгновенной активацией на Linux или Windows, то вам однозначно к нам — сервер готов к работе через минуту после оплаты!
