Hitech logo

Обучение машин

Алгоритм DeepMind обыгрывает людей благодаря новой стратегии

TODO:
Георгий Голованов29 января 2019 г., 11:21

Для победы в StarCraft II и других играх с неполной информацией специалисты DeepMind разработали новый метод подготовки алгоритмов, основанный на теории игр.

Самые интересные технологические и научные новости выходят в нашем телеграм-канале Хайтек+. Подпишитесь, чтобы быть в курсе.

Возможности ИИ в области настольных игр воплощены в программе AlphaGo, которая в 2017 смогла победить чемпионов древней игры го исключительно благодаря самообучению. Улучшенная ее версия, AlphaZero, обыграла людей еще в две игры: шахматы и японские шашки. Однако не все игры поддаются такому методу обучения, пишет ZDNet.

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

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

И вскоре мы узнаем, как это стало возможным. Научная статья, описывающая эту технологию, еще не издана, но на arXiv появился тизер, позволяющий сделать кое-какие выводы. Работа называется  «Open-ended Learning in Symmetric Zero-sum Games» («Открытое обучение в симметрических играх с нулевой суммой»).

В отличие от шахмат или го, StarCraft II — игра с неполной информацией, и предвидеть все возможные ходы противника невозможно. Игроки не имеют точных данных о том, что именно предпринимает оппонент, и видят лишь часть карты.

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

Для решения этой проблемы авторы обратились к анализу самих игроков, попытавшись выявить закономерности в стилях игры.

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

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

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

Наблюдавшие за противостоянием ИИ и профессиональных игроков в Starcraft II отмечали необычные действия алгоритма. И это неспроста.

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

Исследователи протестировали свой подход на классической стратегической игре «Colonel Blotto» 1921 года, так же нетранзитивной, как и StarCraft II. Результат показал, что новый метод превосходит альтернативные, включая метод самообучения AlphaZero. Ученые считают, что это «открытое обучение» способно объединить современные градиентные методы и обучение с подкреплением с адаптивными задачами теории игр.