«Компьютер впервые побеждает чемпиона в Го»

Начиная с 1990-х годов компьютеры непрерывно завоевывали все новые вершины в играх против нас таких как шахматы, шашки, покер или «Своя Игра» (Jeopardy! - https://ru.wikipedia.org/wiki/Jeopardy!). Но есть одна игра, в которую люди-эксперты продолжают доминировать над машинами: Го. Настольная игра с более чем 2500-летней историей, в которой два игрока, используя черные и белые камни, пытаются занять большую территорию, чем оппонент, чрезвычайно разнообразна, что сделало ее трудной для постижения машинами. Но кажется, что превосходство человека в Го в конце концов может закончиться - исследователи из Google DeepMind сегодня объявили, что они создали сложную программу искусственного интеллекта (AI) – комбинацию нейронных сетей глубинного обучения и специального алгоритма поиска – которая смогла победить чемпиона по Го впервые в истории.

В октябре прошлого года в Лондоне команда DeepMind пригласила Fan Hui (действующего чемпиона Европы по Го) сыграть с их программой AlphaGo (https://googleblog.blogspot.com/2016/01/alphago-machine-learning-game-go.html). Матч, свидетелями которого стали всего несколько зрителей, был приватным. Fan Hui и AlphaGo играли на полноразмерной доске 19х19. До этого AlphaGo была протестирована в игре против лучших программ (например, Crazy Stone и Zen) и выиграла все за исключением одного из 495 соревнований. Но игра против эксперта-человека – намного более сложная задача, чем игра против компьютеров, потому что профессионалы до сих пор настолько лучше – у них за плечами годы опыта в игре и вполне определенная интуиция. Таким образом, когда AlphaGo выиграла матч со счетом 5-0, это был большой успех.

Многие предрекали, что компьютеры не смогут победить чемпиона по Го, по крайней мере, в ближайшие 10 лет. «Этот прорыв в эффективности в игре – что-то невероятное и непредсказуемое», заявил David Fotland, разработчик программного обеспечения в Amazon, а также создатель компьютерной программы для игры в Го (http://www.smart-games.com/manyfaces.html), не принимавший участия в проекте.

Чтобы понять, что разработчики из DeepMind проделали, чтобы создать настолько впечатляющую программу, вы должны оценить, почему игра Го так сложна для компьютеров, чтобы они могли играть в нее хорошо. Во-первых, в Го существует абсурдное число возможных ходов и позиций – согласно исследователям, возможных позиций в Го больше, чем атомов во Вселенной. Один из авторов исследования, Demis Hassabis, соучредитель DeepMind, провел сравнение с шахматами, говоря, что в игре в шахматы есть в среднем 20 возможных ответов на каждый ход оппонента, в то время как в Го их существует в среднем 200. Это значит, что если компьютер искал бы все возможные ходы и комбинации в Го, это потребовало бы невообразимую вычислительную мощность для выполнения задачи, кто-то бы сказал, что это даже невозможно.

Другая причина, по которой у компьютеров в Го были трудные времена, поясняет Jonathan Schaeffer, ученый в области информатики в Университете Альберты (Канада), такая, что игрокам в Го требуется чрезвычайно большой пул знаний – основанный на прошлом опыте – для выбора ходов. «В шахматах можно все упаковать в небольшой объем знаний, чтобы создать сильно играющую компьютерную программу», – говорит Schaeffer, который не был вовлечен в проект, – «в Го это невозможно». Это потому, что в шахматах компьютер может следовать запрограммированным правилам, но применение такой стратегии в Го не сработает, потому что эта игра больше о структурах камней («паттернах»), чем о наборе вполне формализуемых логических правил.

Система, разработанная командой DeepMind, решает обе задачи: интенсивного поиска и недостатка знаний. В новой публикации в еженедельнике Nature они описывают комбинирование техники поиска и глубинного обучения (прим. “deep learning” - https://ru.wikipedia.org/wiki/Глубинное_Обучение), чтобы преодолеть указанные трудности. (Scientific American – часть Nature Publishing Group).

Для решения проблемы недостатка знаний они использовали так называемые нейронные сети с глубинным обучением – в данном случае две 13-слойных сети, состоящие из миллионов соединений наподобие нейронов в человеческом мозге. Исследователи обучали эти сети двумя методами: для одной сети они продемонстрировали компьютеру более 30-ти миллионов ходов, сыгранных в партиях между людьми-экспертами (это помогло системе «понять», каким образом лучшие игроки выигрывают); а для обеих сетей исследователи дали возможность компьютеру сыграть с самим собой тысячи партий, чтобы он мог созидать новые стратегии и самообучаться в игре. Эти две стратегии обучения позволили компьютеру распознавать структуры в игре и идентифицировать ходы, приводящие к успеху с наибольшими шансами.

Для трудноразрешимой проблемы поиска исследователи воспользовались эвристическим методом поиска MCTS (Monte Carlo Tree Search - https://en.wikipedia.org/wiki/Monte_Carlo_tree_search). Этот метод, разработанный годы тому назад и использовавшийся в других игровых программах, в своей основе позволяет использовать статистику как короткий путь в принятии решения относительно лучшего хода, нежели просчет каждого возможного исхода в данной позиции (что в Го было бы бесконечно долгим).

Этот метод поиска вместе с инструментами глубинного обучения, использованные командой DeepMind, сами по себе не новые. Многие компьютерные программы для игры в Го тоже используют MCTS, да и нейронные сети были внедрены до этого. Но что делает AlphaGo от DeepMind настолько продвинутой, так это способ, которым удалось скомбинировать эти инструменты, вкупе с высокой производительностью нейронных сетей глубинного обучения. «Главное новшество в том, как все эти ингредиенты были смешаны», – говорит Yoshua Bengio, ученый-информатик из Университета Монреаля (Канада), который не был вовлечен в проект. Schaeffer говорит, что он потрясен результатами: «Это более простой, всеобъемлющий подход, чем те, которые люди применяли в прошлом, и он более элегантный», – говорит он, – «Я вижу в этом гигантский рывок вперед». И это в точности то, что дало AlphaGo преимущество над Fan Hui в их матче – компьютер победил 5-0.

И хотя не каждому есть дело до того, как компьютер обыграл чемпиона в Го, этот прорыв является важным и для других отраслей. Исследователи, построившие систему с «методами общего назначения», а не специфично ориентированную на игру в Го, подразумевают «в конечном счете применять эти методы для важнейших проблем реальной жизни». Hassabis говорит, – «Мы надеемся, что однажды они могут быть расширены, чтобы помочь нам найти решение сложнейших и наиболее сильно довлеющих проблем общества от моделирования климатических изменений до анализа и диагностики сложных заболеваний». Yoshua Bengio говорит, что другое возможное применение – это компьютеризированный диалог, а Schaeffer говорит, что в будущем эти программы возможно будут способны получить ответ на абстрактные социальные проблемы, которые могут быть выражены в игровой форме, например, межнациональная политика или международные переговоры по изменению климата.

Но перед AlphaGo прежде всего стоит более актуальная проблема: как обыграть лучшего игрока в Го (Lee Sedol). В марте этого года они сыграют между собой матч в Сеуле. И хотя AlphaGo играла успешно против Fan Hui, Schaeffer и Fotland все еще сходятся в прогнозе, что Lee Sedol выиграет матч. «Я думаю, профессионал победит», – говорит Fotland, – «Но я думаю, что он будет потрясен фактом, насколько сильна программа». На сегодня по крайней мере некоторые люди все еще ставят на людей.

Автор перевода: Игорь Магдеев, https://www.linkedin.com/in/igor-magdeev-b3b74043

Источник:
Scientific American, 27 January 2016. “Computer Beats Go Champion for First Time” by Annie Sneed.
http://www.scientificamerican.com/article/computer-beats-go-champion-for-first-time/