1. Введение 3
1.1. Игра Merge War 4
2. Определения и постановка задачи 5
2.1. Основные определения 5
2.2. Задача MERGE-GAME и её версии 7
3. Результаты 7
3.1. Сложность MERGE-GAME 7
3.2. Алгоритмы 14
3.3. Полиномиальные модификации 16
4. Заключение 20
5. Список литературы 21
В двадцать первом веке появилась игровая индустрия, ориентированная на массовую аудиторию “казуальных” пользователей [KANP07]. С развитием технологий и распространением игровых устройств стало возможным создавать более простые и доступные игры, которые могут быть быстро запущены и которые будут занимать пользователя на короткое время. Казуальные игры также обычно имеют более низкий порог входа и могут привлечь широкую аудиторию, поскольку основаны на очень простых правилах.
Большое количество мобильных игр основаны на общей merge механике, среди них так называемые Match-3 (три в ряд), например, Bejeweled, AniPang, Aurora Feint, Beghouled & Beghouled Twist, Candy Crush Saga, Diamond Twister, Gweled, Goober’s Lab, Jewel Quest, King Boo’s Puzzle Attack, Magic Duel, “Puzzle Quest: Challenge of the Warlords”, Sutek’s Tomb, Switch, The Treasures of Montezuma, Zoo Keeper и многие другие. На рисунке 1 (взято из [GLN14]) изображена хронология появления некоторых merge-игр.
Несмотря на простые правила, достаточно часто сами игры оказываются NP-полными, если рассматривать их обобщения на большие карты с сохранением игровой механики. В частности, одни из самых популярных казуальных игр современности — 2048 и Candy Crush Saga являются NP-полными, если сделать размеры игровых карт параметром.
Связанные работы. Связанные работы в данной области включают исследования сложности различных игровых механик и алгоритмов для их решения. В работе [GLN14] авторы исследуют сложность Match-3 игр, анализируя количество возможных комбинаций и сравнивая их с другими известными задачами, такими как задача о рюкзаке. Результаты показали, что большинство Match-3 игр являются NP-полными.
В статье [Hay16] авторы сводят обобщенную версию игры Судоку к поиску гамильтонова цикла в графе. Также было проведено исследование игры 2048, которая стала популярной после ее появления в 2014 году. В статье [AAD15, AAD16] авторы доказали NP-полноту для классической версии игры и предложили эффективный алгоритм для нахождения решения. В статье [KPS08] можно найти обширный обзор множества разнообразных NP-полных пазлов, включая карточную игру Solitaire и популярную игру из 80-х Sokoban.
Обзор результатов. Данная работа представляет собой захватывающее путешествие в мир алгоритмической сложности, основанное на увлекательной компьютерной игре Merge War. Мы предлагаем доказательство того, что упрощенная версия этой игры является NP-трудной задачей, открывающей перед нами вселенную возможностей для создания эффективных алгоритмов.
С нашими новыми знаниями мы получим уникальную возможность разработать точные экспоненциальные, параметризованные алгоритмы для решения данной задачи, а также в некоторых случаях решить ее за полиномиальное время. Это открывает необычайно широкие перспективы для применения методов и техник, которые помогут нам решать самые разнообразные задачи в различных областях.
Поэтому мы приглашаем вас присоединиться к нашему увлекательному путешествию по миру алгоритмической сложности и насладиться процессом изучения и разработки новых алгоритмов и методов для решения самых интересных и актуальных задач!
В нашей работе мы определили вычислительную задачу MERGE-GAME, основанную на компьютерной игре Merge War. Было показано, что MERGE-GAME является NP-полной задачей, и, более того, в этой задаче можно создать большое количество ограничений так, что упрощенная версия игры MERGE-GAME-SIMPLE все еще будет NP-полной.
Для задачи MERGE-GAME и некоторых ее модификаций были предложены экспоненциальные алгоритмы, детерменированно находящие точное решение. Была изучена алгоритмическая сложность задачи после упрощения вектора атаки героев. Получилось доказать, что в такой постановке существуют полиномиальные алгоритмы.
Также по результатам нашего исследования мы предлагаем несколько открытых задач, ответ на которые интересно было бы узнать.
• Является ли задача MERGE-GAME NP-полной, если у героев могут быть различные вектора атаки (например, герои одного типа могут бить вверх, а другого типа - вправо)?
• Существует ли полиномиальный алгоритм для задач из теорем 4-7, если убрать ограничение ONE-HP (то есть у камней может быть произвольный изначальный hp) и не ограничивать максимальный уровень героев?
