Новый алгоритм, разработанный командой под руководством UMD, способен решить сценарий полковника Блотто. Являясь заметным достижением, этот алгоритм может также предоставить политическим стратегам, бизнес-лидерам и другим лицам, принимающим решения, новый мощный инструмент для принятия осознанного выбора.«Наш алгоритм потенциально может быть использован для расчета наилучшей стратегии инвестирования ресурсов для любого конкурента в сравнении с одним противником», — сказал Мохаммад Хаджиагайи, доцент кафедры компьютерных наук Университета Мэриленда Джека и Риты Минкер, возглавляющий проект. «Пока у нас достаточно данных по данному сценарию, мы можем использовать наш алгоритм, чтобы найти лучшую стратегию для самых разных лидеров, таких как политические кандидаты, спортивные команды, компании и военные лидеры».
Полковник Блотто натравливает двух конкурентов друг на друга и требует от каждого принимать трудные решения о том, как использовать ограниченные ресурсы. В простейшей форме каждый игрок назначает ограниченное количество ресурсов или войск на несколько полей сражений. Игроки должны делать это, не зная стратегии своего оппонента.
Игроки выигрывают данное поле битвы, если они выделяют больше войск, чем их противник; Игрок, выигравший наибольшее количество полей сражений, также побеждает в игре.Игра может быть расширена до реальных сценариев, таких как всеобщие президентские выборы в США. В этом примере каждый кандидат — игрок; ресурсы, такие как штаб кампании, время на пень и финансирование, — это войска; и каждое государство — это поле битвы. Игра также может применяться к высококлассной конкуренции потребительских товаров, такой как продолжающаяся битва между Apple iPhone и продуктами Google для мобильных телефонов Android.
«От президентских выборов до маркетинговых решений конкуренция за внимание и лояльность является частью повседневной жизни. Однако поведение людей в ответ на такие соревнования еще недостаточно изучено», — сказал Хаджиагайи, который также имеет совместное назначение в университете. Института перспективных компьютерных исследований Мэриленда (UMIACS). «Мы показываем, что такое стратегическое поведение поддается вычислению.
Учитывая описание конкуренции, мы можем определить, какие стратегии будут максимизировать результаты для данного игрока».Хотя правила полковника Блотто относительно просты, потенциальные стратегии, которые может использовать игрок, практически безграничны, в зависимости от количества полей битвы и общих ресурсов, доступных каждому игроку. Решение, достигнутое Хаджиагайи и его коллегами, не обязательно отдает предпочтение одному игроку по сравнению с другим, но скорее представляет собой равновесие, в котором оба игрока развернули лучшую стратегию, которую они могут использовать в отношении стратегии своего оппонента.
Большое разнообразие возможных стратегий было ключевым препятствием на пути к поиску вычислительного решения игры. Хаджиагайи и его команда решили эту проблему, ограничив общее количество возможных стратегий небольшим количеством репрезентативных вариантов.
«Мы обнаружили, что стратегии игроков могут быть точно представлены с помощью достаточно небольшого количества возможностей», — сказал Хаджиагайи. «Это более общий подход, но он хорошо работает как доказательство концепции. Многие другие пытались решить проблему полковника Блотто для конкретных сценариев, но мы первые, кто выбрал более общий подход и решил теорию».Это решение позволило команде разработать обобщенный алгоритм, который теперь можно применять к конкретным сценариям, таким как президентские выборы 2016 года.«Наш алгоритм работает только для двух конкурентов, поэтому нам нужно будет дождаться всеобщих выборов, чтобы попробовать это», — сказал Саид Седдигин, аспирант по информатике в UMD, который представит результаты группы на собрании AAAI. «Если мы знаем, как данный штат проголосовал на предыдущих выборах относительно ресурсов, которые каждый кандидат вложил в этот штат, то мы можем использовать те же данные об инвестициях из избирательного цикла этого года, чтобы предсказать, применил ли каждый кандидат свою наилучшую стратегию в масштабах всей страны. . "Исследование «От дуэлей к полям сражений: вычисление равновесия блотто и других игр» Амира Махди Ахмадинежада, Сины Дехгани, Мохаммада Таги Хаджагайи, Брендана Люсьера, Хамида Махини и Саида Седдигина будет представлено 15 февраля 2016 года в Ассоциации Конференция по развитию искусственного интеллекта (AAAI) в Фениксе, штат Аризона.
Эта работа была поддержана Национальным научным фондом (награды № 1053605 и CCF-1161626), Управлением военно-морских исследований (награда № 000141110662), Агентством перспективных исследовательских проектов Министерства обороны (награда № FA9550-12-1-0423). и Google. Содержание этой статьи не обязательно отражает взгляды этих организаций.