С начала компьютерной эры люди сравнивают возможности «электронного мозга» со своими собственными.

Один из способов подойти к этому вопросу - использовать абстракцию игры, в частности такую, которая имеет определенный набор правил и условий победы, и посмотреть, сможет ли компьютерный игрок победить игрока-человека. Другими словами, может ли компьютер перехитрить человеческого противника?

Такие игры, как шахматы, позволяют нам тестировать и тренировать ИИ, так что однажды они смогут не только решать проблемы быстрее, чем мы, но и решать вопросы, на которые мы еще не ответили.

Тем не менее, это был постепенный путь, и все более совершенные ИИ разрабатывались для более сложных сценариев и игр. В этой статье мы проследим за соревнованием между нами и компьютерами, поскольку это относится к игровым играм различной сложности и свойств. В этой первой части мы рассмотрим некоторые из старейших испытаний, такие как нарды, шахматы или го, в которые играли веками, а также более молодые изобретения, такие как Scrabble, или даже современное телешоу, такое как Jeopardy!

1950-е - Объединение игр и искусственного интеллекта

Искусственный интеллект, как отрасль науки, имеющая решающее значение в этом начинании, зародился в пятидесятых годах, и примерно в это же время были написаны первые простые программы для игры в крестики-нолики, шашки и шахматы. Однако последствия этой гонки между человеком и машиной выходят далеко за рамки индустрии игр и развлечений.

Но каждая хорошая история должна где-то начинаться, и наш след начинается в 1950 году.

Крестики-нолики - Детские шаги

Крестики-нолики, также известные как крестики-нолики, - это простая классическая игра с ручкой и бумагой, в которой игрок выигрывает, создавая 3 отметки в горизонтальном, вертикальном или диагональном ряду на матрице 3 на 3. Из-за этих ограниченных ходов очень легко обнаружить, что идеальная игра с обеих сторон всегда приводит к ничьей.

Он также был первым, кто принял форму видеоигры. В 1950 году компьютер под названием Bertie the Brain был показан во время Канадской национальной выставки. Он не всегда побеждал, но был способен.

Ситуация изменилась два года спустя, когда была разработана программа под названием OXO, разработанная для EDSAC (Electronic Delay Storage Automatic Calculator). Он смог идеально воспроизвести все 26 830 возможных игровых последовательностей (без учета вращения и отражений доски). Программа была классическим примером минимаксного алгоритма, оценивающего дерево возможных ходов. Проблемное пространство достаточно мало, даже для компьютера семидесятилетней давности, который принимал в качестве входных данных цифры от 1 до 9, выбранные с помощью поворотного контроллера телефона, и отображал результаты на ЭЛТ-дисплее размером 35 на 16 пикселей.

Интересно отметить, что игра «Крестики-нолики» была широко представлена ​​в фильме «Военные игры» 1983 года, где она послужила аналогом глобальной термоядерной войны, чтобы научить искусственный интеллект тому, что в некоторых играх невозможно выиграть.

Нарды - Первый триумф

Нарды - одна из старейших известных настольных игр, появившаяся в древней Месопотамии пять тысячелетий назад. Он включает в себя бросание кубиков и перемещение 15 фигур по доске, состоящей из 24 треугольников. Выигрывает тот, кто первым уберет свои фигуры с доски.

Эта игра жизненно важна для нашей истории, поскольку это был первый случай в истории человечества, когда чемпион-человек был побежден компьютерной программой в признанной интеллектуальной деятельности. В 1979 году программа BKG 9.8 вступила в матч против Луиджи Вилласа и выиграла 7 игр из 1. Программа была основана на эвристике для решения набора линейных уравнений, а также на оригинальном методе SNAC (гладкие нелинейные функции и коэффициенты приложения). .

Черновики - решенная стратегия

Шашки, также известные как шашки, часто называют младшим братом Шахмат, и в них играют на той же доске 8 на 8, но вместо этого используются 12 одинаковых фигур на каждую сторону (хотя существуют и другие варианты). Цель состоит в том, чтобы захватить все фигуры соперника, перепрыгивая их по доске диагональными движениями.

Первая программа для игры в Drafts была написана Артуром Самуэлем и работала на компьютере Ferranti Mark 1 в 1951 году, что сделало ее одной из первых попыток бросить вызов игроку-человеку с машинным противником в нашей истории. К началу шестидесятых он смог победить респектабельных игроков-любителей.

Однако нам пришлось подождать до 1994 года, чтобы увидеть падение человеческого чемпиона. Программа под названием Chinook смогла победить Мэрион Тинсли. Счет стал 4: 2 при 33 ничьих. В 2007 году команда Chinook объявила, что они решили игру в шашки и доказали, что безупречная игра обеих сторон всегда приводит к ничьей.

Шахматы - разнообразие движений и массивный параллелизм

Игра королей, также известная как шахматы, - один из самых ярких способов доказать превосходство над соперником, как мы можем вспомнить из эпохи холодной войны, когда советские шахматисты были важной частью коммунистической пропаганды.

Эта игра более сложна, чем шашки, поскольку у нас есть гораздо больше возможностей для перемещения наших фигур в любой момент игры, что делает более проблематичным использование традиционных методов искусственного интеллекта, основанных на поиске и подсчете дерева возможных ходов на многие раунды вперед.

Тем не менее, в знаменитом матче 1997 года машина IBM Deep Blue смогла обыграть действующего чемпиона мира Гэри Каспарова, используя этот метод, с близким счетом 3,5: 2,5. Deep Blue использовал преимущества массивно распараллеленных микросхем пользовательской сборки VLSI (очень крупномасштабная интеграция - иногда это просто сокращение) для проведения своих вычислений. У него было 30 узлов, каждый из которых содержал один многоцелевой ЦП, управляющий 480 такими микросхемами. Многие журналисты тогда объявили, что это конец гонки «человек против машины» с победителем из силикона.

Однако это было очень преждевременно. Впереди еще много испытаний ...

Scrabble - несовершенная информация и злонамеренные действия

Scrabble существует более 80 лет, но он все еще довольно новый по сравнению с играми, которые мы только что исследовали. В этой игре игроки собирают кроссворд на доске 15 на 15, пытаясь набрать максимальное количество очков, которое зависит от буквы и местоположения.

В отличие от других игр, которые мы рассмотрели до сих пор, в нее вносится элемент несовершенной информации, поскольку мы не знаем, какие буквы есть в распоряжении нашего оппонента. Это означает, что не существует точной информации, и машины должны учитывать данные, которые от них скрыты.

Нам пришлось ждать до 2007 года первой победы ИИ, когда компьютерная программа Quackle победит чемпиона среди людей Дэвида Бойса. Программа использует метод грубой силы, который похож на то, что мы видели раньше, строит и оценивает дерево возможных ходов. Тем не менее, что интересно в компьютерной стратегии Scrabble, так это то, что вместо интуитивной оптимизации, чтобы поместить слово с максимально возможной оценкой, он может попытаться угадать руку своего оппонента и, основываясь на вероятности, попытаться сделать ход с менее прямым выгода для нас, но такая, которая блокирует лучшие варианты оппонента, тем самым более эффективно сдвигая вероятность выигрыша в сторону компьютера.

Опасность! - Понимание естественного языка

Опасность! Это телешоу, в котором участникам предлагаются общие подсказки, и им нужно дать решение в форме вопроса. Чтобы выиграть игру, игрок должен сочетать рассуждения со знаниями в, казалось бы, неограниченном пространстве проблем.

В показательном матче 2011 года машина IBM Watson выиграла матч у двух самых высокооплачиваемых участников профессиональных игр - Кена Дженнингса и Брэда Раттера. Watson - это сложная компьютерная система, которая использует обработку естественного языка, поиск информации, представление знаний, автоматизированное рассуждение и машинное обучение для ответа на произвольные вопросы.

Столкнувшись с предложением, Watson разбивает его на части, параллельно выполняя более 100 различных алгоритмов обработки естественного языка, которые формулируют гипотезы на основе своих баз данных. Затем он выполняет мягкую фильтрацию и сравнивает эти гипотезы с другой базой данных. Затем все эти выходные данные объединяются и сравниваются друг с другом с использованием модели, обученной с помощью машинного обучения. В качестве источников информации Watson использует специально организованные энциклопедии, словари, различные статьи, книги и онлайн-источники. Первоначальное оборудование состояло из 90 восьмиъядерных процессоров POWER7.

Go - Взрыв сложности и глубокое обучение

Го было изобретено в Китае более 2500 лет назад, и в него до сих пор играют в его первоначальном виде. Он состоит из размещения фигур на доске 19 на 19, чтобы окружить большую территорию, чем противник.

Тем не менее, несмотря на простые правила, го для компьютеров намного сложнее, чем шахматы. В последнем случае у нас есть в среднем 37 возможных ходов одновременно, в то время как в Го их более 150. Также труднее подсчитать ценность хода, чем учитывать материальное преимущество, полученное при взятии фигуры противника, как и случай в шахматах.

После победы над Каспаровым многие думали, что нам придется подождать сотню лет, чтобы достичь вычислительной мощности, необходимой для того, чтобы бросить вызов человеческому чемпиону в го, но все обернулось иначе! AlphaGo, созданная командой Deep Mind, выиграла знаменитый матч против профессионального игрока с 9 даном Ли Седола, финишировав со счетом 4: 1 в 2016 году, а всего год спустя победила действующего чемпиона Ке Джи.

AlphaGo использует гораздо более сложный метод, чем тот, который мы обсуждали ранее. Хотя он также строит и ищет дерево, чтобы найти оптимальный ход, он использует знания, полученные в результате тренировки с глубокой нейронной сетью на обширном наборе исторических матчей, все сыгранные между людьми-противниками.

Этот метод глубокого обучения пытается имитировать то, как наш мозг обрабатывает информацию. Сеть состоит из множества уровней, каждый из которых обрабатывает входную информацию на разном уровне абстракции. Более ранняя версия AlphaGo использует графические процессоры для эффективного выполнения матричных операций, лежащих в основе нейронных сетей и использующих преимущества множества ядер, работающих параллельно. Более поздние версии пошли еще дальше, работая на тензорных процессорах - оборудовании, строго оптимизированном для вычислений машинного обучения.

Резюме - что мы узнали на данный момент?

Это не конец нашего пути - на самом деле, есть так много всего, что нужно осветить, я разбил это на две части. Однако даже на этом этапе ясно, что мы прошли долгий путь. Когда возможности ограничены, с установленными ходами и ограниченным / заранее определенным количеством результатов, технологии давно решают такие проблемы - часто это просто случай масштабирования обработки с увеличением масштаба игр.

Однако мы начали замечать проблемы, которые используют скрытую информацию или полагаются на «понимание» вашего оппонента. Именно здесь мы начали разрабатывать новые подходы, по-настоящему демонстрируя потенциал решений ИИ, машинного обучения и глубокого обучения по сравнению с традиционными процессами принятия решений на основе дерева.

Что дальше?

У нас осталось всего два года, чтобы рассказать о нашей истории, но, поверьте мне, именно здесь все становится по-настоящему интересным. Мы поговорим о проблемах с масштабами проблемных пространств за пределами игры в го, в том числе о тех, которые еще недавно считались слишком сложными для решения в ближайшем будущем. Что наиболее важно, мы также обсудим, как эти достижения отражаются во множестве других областей помимо игр, поэтому не пропустите вторую часть этой статьи.

А пока вы можете проверить сообщение в блоге Томаша Зелински о наших собственных попытках в этой области. Мы написали AI-бот для игры в Азул - простую, но очень популярную абстрактную семейную игру!

Деловая перспектива

Машинное обучение набирает обороты. Мы можем создавать искусственных существ, которые самостоятельно успешно понимают, как перемещаться по все более сложной среде. Существует бесчисленное множество вариантов использования во всех сферах человеческой деятельности. Однако стоит также упомянуть, что и облачные вычисления, и доступ к огромному объему данных являются двумя ключевыми факторами в этой области.

Источники:

Первоначально опубликовано на https://www.pgs-soft.com.