Как шашки изменили мир и позволили зародиться искусственному интеллекту
Когда человек играет в компьютерные игры, объясняя это саморазвитием, его снисходительно называют геймером. Когда в игры играет сам компьютер с той же самой целью, это называют машинным обучением и искусственным интеллектом. Логические настольные игры — действительно один из лучших способов «прокачки» самообучающихся систем. О том, кто придумал эту технологию, и причем здесь шашки, мы расскажем в сегодняшней статье.
В 1950 году разумные машины все еще были фантастикой. Но в фантастике пятидесятых потому и превалировало направление «научная», что некоторые идеи о дальнейшем направлении технического прогресса вполне могли стать реальностью. Ученые всерьез разрабатывали обитаемые орбитальные станции и исследовательские межпланетные корабли для колонизации Марса. В октябре 1950 года в журнале «Mind» математик Алан Тьюринг опубликовал статью «Вычислительные машины и разум», в которой описал эксперимент, позже получивший известность под названием «Тест Тьюринга». В те времена казалось, что до появления самообучающихся компьютерных программ еще очень и очень далеко. Однако первая такая программа была создана уже спустя два года.
Основоположник технологии машинного обучения на основе игровых механик, американский ученый и специалист в области информатики Артур Самуэль, родился 5 декабря 1901 года в городе Эмпория, штат Канзас. В 1923 году он окончил местный колледж, после чего поступил в Массачусетский технологический институт, отучившись в котором, остался в качестве преподавателя. В 1928 году Самуэль устроился на работу в Bell Laboratories, где занимался разработкой приборов на базе вакуумных ламп, в основном, военных радаров. После войны он перебрался в Университет Иллинойса в Урбане-Шампейне, где под началом Самуэля начали создавать компьютер ILLIAC, но в 1949 году молодой ученый покинул университет и перешел на работу в корпорацию IBM. Там он занялся созданием программ для компьютера IBM 701, и именно на этом компьютере он написал свою знаменитую самообучающуюся программу для игры в шашки, после публичной демонстрации которой акции компании IBM разом взлетели на 15 пунктов.
Работу над этим проектом Артур Самуэль начал еще в 1949 году, когда трудился в Университете Иллинойса. Он считал, что в будущем компьютерные программы должны не только строго исполнять заложенные в них инструкции, но также самообучаться, корректируя свое поведение в зависимости от меняющихся обстоятельств на основе набора базовых алгоритмов. А самый эффективный способ натренировать такую программу — это игровые механики, полагал Самуэль.
В качестве игры, на основе которой он решил разработать самообучаемую программу, Артур Самуэль взял шашки. Во-первых, ему самому очень нравилась эта игра, а во-вторых, ее правила весьма просты, а число возможных стратегий — наоборот, крайне велико. Большинство разработанных в то время игровых алгоритмов последовательно перебирали все возможные варианты следующего хода, а затем выбирали среди них оптимальный. Самуэль не мог строить свой проект на базе такой модели поведения, поскольку IBM 701 использовал память на электронно-лучевых трубках Уильямса ёмкостью 512 слов по 36 бит, и столь небольшого объема было для этого попросту недостаточно. Благодаря стараниям Самуэля память машины была в итоге увеличена до 2048 слов, среднее время отказа возросло до получаса, а в систему команд IBM 701 был добавлен целый ряд разработанных им директив для нечисловых вычислений.
Поэтому Артур Самуэль применил иной подход: для расчета ходов в игре он использовал механизм поиска решений, известный как «альфа-бета-отсечение». Чтобы понять, что это такое, сначала нужно рассмотреть алгоритм минимакса и концепцию игровых деревьев. Алгоритм минимакса обычно используется в играх с нулевой суммой для двух игроков, где выигрыш одного означает проигрыш другого. Игровые деревья описывают все возможные ходы и их результаты в игре, причем каждый узел представляет собой определенное состояние игры и связанное с ним значение.
Алгоритм минимакса предполагает, что игроки стремятся максимизировать свое преимущество, одновременно пытаясь минимизировать преимущество соперника. Математическая модель оценивает состояние игры после каждого хода, чередуя максимизирующие и минимизирующие ходы с текущего положения и двигаясь вниз по игровому дереву до достижения конечного результата — победы одного из игроков. Этот алгоритм способен выбрать оптимальную тактику, однако без применения каких-либо методов оптимизации будут оцениваться все возможные ходы и их последствия, что приведет к непрактичному и неэффективному процессу принятия решений. Именно поэтому Самуэль использовал технику, которая значительно сокращает количество оцениваемых алгоритмом минимакса узлов путем удаления ненужных ветвей игрового дерева, которые не влияют на окончательное решение.
Созданная Артуром Самуэлем программа для игры в шашки использовала оценочные функции, каждая из которых имела собственный «вес». «Вес» функции менялся в процессе игры, если один из игроков просчитывал партию на большее количество ходов вперед и играл сильнее. Более того, в программу был заложен справочник с описанием партий, сыгранных профессиональными шашистами — за основу Самуэль взял популярную книгу Джеймса Лиса «Руководство по шашкам». Справочник использовался в случае, когда на доске складывалась похожая ситуация: если в справочнике уже имелась подходящая запись, «вес» функции менялся таким образом, что компьютер повторял ход, сделанный ранее в аналогичной диспозиции человеком.
Машина «запоминала» все сыгранные партии (этот алгоритм Самуэль назвал «rote learning», «зубрёжка»), учитывала неудачные ходы, и применяла полученные знания при подсчете следующего хода, увеличивая тем самым глубину поиска оптимального решения. Таким образом, программа получилась самообучающейся: она итеративно улучшала свою производительность, играя сама против себя и обучаясь на результатах. Полученные в ходе игры данные накапливались, а затем использовались для определения «весовой» функции последующих ходов и адаптации игровой стратегии на основе наблюдаемых результатов.
Программа Самуэля заложила основу для использования алгоритмов машинного обучения не только в игровой индустрии, но также в других областях, и открыла дорогу будущим достижениям в области искусственного интеллекта. Разработанные Артуром Самуэлем концепции и методы, такие как самообучение путем игры «сам с собой», итеративное улучшение поиска решений и внедрение функции оценки, повлияли на разработку более сложных алгоритмов, включая обучение с подкреплением. Схожие принципы используются сегодня при создании технологий машинного обучения в таких направлениях, как распознавание образов, обработка естественного языка, робототехника и автономные системы.
Безусловно, наиболее существенным ограничивающим фактором для проекта Самуэля были весьма скромные аппаратные возможности компьютера IBM 701, хотя для 50-х годов его программа была самым настоящим научно-техническим прорывом. Уже тогда она могла соперничать с опытными игроками в шашки практически на равных, при этом Самуэль продолжал развивать и совершенствовать приложение вплоть до середины 70-х.
В 1961 году Эд Фейгенбаум и Джулиан Фельдман решили написать научно-популярную книгу «Компьютеры и мышление». Соавторы попросили Самуэля дополнить издание описанием самой лучшей игры в шашки в исполнении его программы. Самуэль использовал это предложение, как повод бросить вызов чемпиону штата Коннектикут по шашкам, который считался четвертым по силе игроком на территории США. Программа Артура Самуэля победила в этом поединке, а описание партии вошло в антологию Фейгенбаума и Фельдмана. Позже на заложенном Самуэлем фундаменте были построены самообучающиеся программы для игры в Го и шахматы, а самого создателя технологии по праву называли «пионером искусственного интеллекта».
Собственно, ограниченные аппаратные возможности так или иначе тормозили развитие машинного обучения и интеллектуальных компьютерных систем, пока не стали широко доступны облачные технологии. Именно их распространение и стало своего рода катализатором, подарившим развитию искусственного интеллекта второе дыхание.
Современные системы, работающие на основе алгоритмов машинного обучения, подразумевают обработку больших массивов данных и запуск сложных моделей, что, в свою очередь, требует значительных вычислительных мощностей. Облачные платформы предлагают эластичные ресурсы, которые можно легко увеличивать или уменьшать в зависимости от текущих потребностей, а это дает возможность исследователям и разработчикам обойтись без предварительных инвестиций в аппаратную инфраструктуру. Тем более, при использовании такой схемы оплачиваются только фактически потребляемые ресурсы, что, опять же, означает экономию.
Используя облачные платформы, разработчики могут развернуть свои модели в виде сервисов или API, что делает их доступными для сторонних приложений и заметно облегчает интеграцию возможностей ИИ в различные системы и сервисы, включая мобильные приложения, веб-платформы и устройства IoT. Кроме того, в облаке намного проще реализовать централизованное и безопасное хранилище огромных объемов данных, необходимых для работы самообучающейся системы.
Экспоненциальный рост числа построенных на базе искусственного интеллекта проектов во втором десятилетии XXI века во многом обусловлен заметным снижением входного барьера в этой сфере. Благодаря доступности вычислительных мощностей, предварительно сконфигурированных сред и заранее обученных моделей на современных облачных платформах, исследователям и разработчикам намного проще сосредоточиться на внедрении инноваций, а не на настройке и управлении инфраструктурой.
К сожалению, Артур Самуэль не увидел столь бурного прогресса технологий, основы которых он заложил в пятидесятых. Помимо инженерных разработок и компьютерных наук, Самуэль занимался управленческой деятельностью. Он сыграл большую роль в создании европейских лабораторий IBM в Вене и Цюрихе, активно трудился над технологиями распознавания речи, пока эти проекты не перешли из лабораторий IBM в ведение DARPA.
В 1966 году он уволился из IBM и стал профессором в Стэнфордском университете, где проработал остаток своей жизни. Артур Самуэль тесно сотрудничал с Дональдом Кнутом при создании проекта TeX, и самостоятельно написал часть технической документации для этого стандарта. Во второй половине восьмидесятых у него диагностировали болезнь Паркинсона, с которой Артур Самуэль мужественно боролся, и от последствий которой скончался 29 июля 1990 года в возрасте 88 лет. Но, тем не менее, он продолжал дистанционно работать на машинах Стэнфордского факультета компьютерных наук и писать приложения для обработки текстов в формате TeX. Серверы Стэнфордского университета зафиксировали его последний вход в систему 2 февраля 1990 года, менее чем за шесть месяцев до смерти, когда болезнь Артура достигла уже критической стадии.
Сэмуэль был членом международного Института инженеров по электротехнике и электронике, Американского физического общества, Института радиоинженеров, Американского института инженеров-электриков, а также членом Ассоциации вычислительной техники и Американской ассоциации содействия развитию науки. У него остались две дочери и четверо внуков.
Программа Артура Самуэля «Шашки» стала важной вехой в области искусственного интеллекта и машинного обучения. Впервые продемонстрировав способность компьютерного ПО обучаться и совершенствовать свои навыки поиска решений на основе меняющегося набора исходных данных, работа Самуэля открыла новые возможности для применения алгоритмов машинного обучения в различных областях. Влияние его программы продолжает сказываться на развитии ИИ, вдохновляя исследователей расширять границы того, чему могут научиться и чего способны достичь машины.
Источники: Arthur Samuel, Emporia, Kansas, Arthur Samuel, IBM 701, Alpha–beta pruning, Minimax algorithm.
