Теория игр и Искусственный Интеллект

Сегодня в рубрике #чтопочитать статья с сайта Medium из раздела Data Driven Investor.

Игры занимают ключевое место в эволюции искусственного интеллекта (ИИ). Этому свидетельствует то, что игровые среды становятся популярным тренировочным механизмом в таких областях, как обучение с подкреплением (reinforcement learning) и имитационное обучение (imitation learning). В теории, любая многоагентная система ИИ может работать с геймифицированными взаимодействиями участников. Раздел математики, который формулирует игровые принципы, называется теорией игр. В контексте искусственного интеллекта и систем глубокого обучения теория игр обеспечивает некоторые ключевые возможности, необходимые в многоагентных средах, в которых различные программы ИИ должны взаимодействовать или соревноваться друг с другом для достижения какой-либо цели.

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

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

Хотя игры, очевидно, и являются наиболее наглядным воплощением теории игр, они далеко не единственное пространство, в котором применяются эти концепции. Существует множество других областей, на которые может положительно повлиять сочетание теории игр и ИИ. Дело в том, что большинство ситуаций, в которых несколько участников сотрудничают или соревнуются за достижение какой-либо цели могут быть геймифицированы и улучшены с помощью методов ИИ. Несмотря на то, что предыдущее утверждение является обобщением, я надеюсь, что оно передает основную мысль: теория игр и искусственный интеллект — это способ мышления и моделирования программных систем, а не определенная методика.

Хорошими претендентами на использование теории игр являются ситуации, включающие в себя больше одного участника. Например, система искусственного интеллекта, занимающаяся оптимизацией прогнозов продаж, такая как Salesforce Einstein, не является идеальным кандидатом для применения принципов теории игр. Однако, в многопользовательской среде теория игр может быть невероятно эффективной. Структуру игровой динамики в системах ИИ можно обобщить двумя элементами:

• Дизайн участников: Теория игр может быть использована для оптимизации решения одного из участников с целью получения максимальной полезности.
• Дизайн механизмов: Обратная ("inverse") теория игр ориентирована на проектировании игры для группы толковых участников. Аукционы являются классическим примером дизайна механизмов.
  

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

Одна из простейших классификаций игр основана на их симметрии. Симметричная игра описывает среду, в которой все игроки имеют одну и ту же цель, а результат будет зависеть только от их стратегий. Шахматы - классический пример симметричной игры. В реальном мире многие ситуации не являются симметричными, так как у участников часто бывают разные и даже противоречивые цели. Деловые переговоры — это пример несимметричной игры, в которой каждая из сторон имеет свои цели и оценивает результаты с разных точек зрения (например: подписание контракта против минимизации инвестиций)

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

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

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

Игра с нулевой суммой относится к ситуации, в которой доход одного игрока всегда приводит к потерям других игроков. Настольные игры — это примеры игр с нулевой суммой. Игры с ненулевой суммой часто встречаются в ситуациях, в которых несколько игроков могут извлечь выгоду из действий одного игрока. Экономическое взаимодействие, при котором несколько участников сотрудничают для увеличения размера рынка (market size), является примером игры с ненулевой суммой.

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

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

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

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

Многоагентные системы ИИ - одно из самых увлекательных направлений исследований в области искусственного интеллекта. Принципы теории игр, сформулированные легендами информатики, такими как Алан Тьюринг и Джон фон Нейман, в настоящее время находятся в центре некоторых из самых интеллектуальных систем в мире, а последние достижения в области ИИ способствуют продвижению исследований в области теории игр.

Оригинальная статья