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
Список литературы 20
В двадцать первом веке появилась игровая индустрия, ориентированная на массовую аудиторию “казуальных” пользователей [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-трудной задачей, открывающей перед нами вселенную возможностей для создания эффективных алгоритмов.
С нашими новыми знаниями мы получим уникальную возможность разработать точные экспоненциальные, параметризованные алгоритмы для решения данной задачи, а также в некоторых случаях решить ее за полиномиальное время. Это открывает необычайно широкие перспективы для применения методов и техник, которые помогут нам решать самые разнообразные задачи в различных областях.
Рисунок 1.
Поэтому мы приглашаем вас присоединиться к нашему увлекательному путешествию по миру алгоритмической сложности и насладиться процессом изучения и разработки новых алгоритмов и методов для решения самых интересных и актуальных задач!
1.1. Игра Merge War
Merge War (ссылка) — однопользовательская мобильная игра, ключевой механикой в этой игре является merge. Игрок проходит уровни, сражаясь с ботами на двумерной карте. Одной из стратегий в игре является призыв как можно большего количество героев с целью увеличения своей силы. Так как свободных клеток на карте ограниченное число, возникает задача разрушения камней для освобождения свободного места.
Таким образом, по мотивам данной игры возникает следующая задача. Игра происходит на двумерной карте, разбитой на клетки. В некоторых клетках стоят камни, в некоторых клетках стоят герои. Каждый герой характеризуется типом и уровнем — натуральным числом, изначально у всех героев уровень 1. Каждый камень характеризуется целочисленными очками здоровья hp. Цель игры — уничтожить как можно больше камней.
Для этого можно произвольное количество раз выполнять следующую операцию — выбрать двух героев одинакового уровня, и объединить их в одного героя уровнем на 1 выше. Новый герой помещается в любую из клеток, где стояли объединенные в него герои, и наносит урон 1 соседним по стороне камням.
Рис. 2. Объединение (merge) героев
На рисунке 2 герои изображены в виде кругов разных цветов. Каждый цвет обозначает свой тип героев, а число внутри круга - это их уровень. Камни нарисованы в виде квадратов, а число внутри каждого квадрата показывает количество очков здоровья hp. В конкретном случае два зеленых героя 3 уровня объединились в нового зеленого героя 4 уровня, и нанесли урон камню, уменьшив очки здоровья камня с 7 до 6.
В нашей работе мы определили вычислительную задачу MERGE-GAME, основанную на компьютерной игре Merge War. Было показано, что MERGE-GAME является NP-полной задачей, и, более того, в этой задаче можно создать большое количество ограничений так, что упрощенная версия игры MERGE-GAME-SIMPLE все еще будет NP-полной.
Для задачи MERGE-GAME и некоторых ее модификаций были предложены экспоненциальные алгоритмы, детерменированно находящие точное решение. Была изучена алгоритмическая сложность задачи после упрощения вектора атаки героев. Получилось доказать, что в такой постановке существуют полиномиальные алгоритмы.
Также по результатам нашего исследования мы предлагаем несколько открытых задач, ответ на которые интересно было бы узнать.
• Является ли задача MERGE-GAME NP-полной, если у героев могут быть различные вектора атаки (например, герои одного типа могут бить вверх, а другого типа - вправо)?
• Существует ли полиномиальный алгоритм для задач из теорем 4-7, если убрать ограничение ONE-HP (то есть у камней может быть произвольный изначальный hp) и не ограничивать максимальный уровень героев?
