Max Home IndustryCandy Crush — это феномен, хотя бы из-за того количества времени, которое мир потратил на это. Вроде простая игра, но, судя по количеству загрузок, качество вызывает привыкание. Теперь мы знаем почему — это NP-сложно.
У Тоби Уолша из Университета Нового Южного Уэльса, Австралия, есть доказательство, которое ставит Candy Crush на его место, и он может даже предложить способы сделать игру лучше.
Если вы не знаете Candy Crush, вы не можете быть одним из примерно полумиллиарда загрузчиков на Facebook, iOS или Android. Это вариант класса игр «три в ряд». В проанализированной игре есть доска нестандартного размера, но в остальном это та же игра:
Доска заполнена конфетами шести разных цветов. Задача состоит в том, чтобы поменять местами соседние конфеты, чтобы создать серию из трех конфет одного цвета. Когда вы получаете набор из трех штук одного цвета, они исчезают, а конфеты сверху падают, чтобы заменить их. Вы получаете по одному за каждый набор из трех, по которому вы исчезаете.
Задача состоит в том, чтобы набрать установленный балл s за k обменов.
Довольно легко показать, что проблема в NP. Если вам дан набор из k свопов, который набирает s, то вы можете проверить, что это так, за полиномиальное время и, следовательно, проблема в NP.
В своей статье Уолш объясняет, как отобразить задачу 3-SAT, которая, как известно, является NP Complete, за полиномиальное время, в Candy Crush, что доказывает, что Candy Crush как минимум NP-сложна.
Грубо говоря, NP-сложные задачи не менее сложны, чем самые сложные задачи в NP. Сокращение от 3-SAT происходит по обычному пути создания «гаджетов», которые преобразуют игру в набор логических функций.
Далее в статье рассматриваются некоторые из измененных игровых процессов на более поздних уровнях Candy Crush, такие как закрытие слоев — это тоже NP-сложно.
Последний вопрос касается того, есть ли несколько решений данной проблемы Candy Crush. По-видимому, в игру лучше играть, если есть только одно решение, и поэтому было бы неплохо узнать, есть ли у данной проблемы уникальное решение. Оказывается, эта проблема является NP-сложной задачей — доказательство того, что существует много решений, является NP-сложной.
Практические мысли о Candy Crush?
NP-hard — это классификация наихудшего случая. Как мы можем изменить сложность задач Candy Crush? Может ли произойти «фазовое изменение» параметров, которое превратит простые проблемы в сложные? У автора статьи есть хорошая идея:
«Многие миллионы часов были потрачены на решение Candy Crush. Может быть, мы сможем использовать это еще лучше, спрятав некоторые практические NP-сложные проблемы в этих головоломках?»