Почему некоторые игры np-complete?

Я прочитал статью в Википедии о « Списке проблем с NP-полнотой » и обнаружил, что такие игры, как Super Mario, Pokemon, Tetris или Candy Crusha Saga, являются NP-полными. Как я могу представить np-полноту игры? Ответы не должны быть слишком точными. Я просто хочу получить общее представление о том, что игры могут быть np-завершены.

Это просто означает, что вы можете создавать уровни или головоломки в этих играх, которые кодируют проблемы NP-Hard. Вы можете взять задачу раскраски графа, создать связанный уровень Super Mario Bros., и этот уровень можно преодолеть тогда и только тогда, когда график имеет 3 цвета.

Если вы хотите увидеть конкретный способ , которым NP-полные задачи переведенные в игры, я рекомендую статью «Классические Nintendo Игр (вычислительном) Hard» . Это хорошо написано и легко следовать.

Важно помнить, что NP-сложность требует обобщения игр «очевидными» способами. Например, тетрис обычно имеет фиксированный размер доски, но для доказательства твердости требуется, чтобы игра допускала сколь угодно большие доски. Другой пример - враги за пределами экрана в Super Mario Bros: доказательство для варианта игры, где враги за пределами экрана продолжают двигаться, как если бы они были на экране, вместо того, чтобы перестать существовать и возвращаться в исходное положение, когда Марио возвращается ,

Я, честно говоря, точно не знаю, какую модель используют люди, делающие эти заявления; однако, то, что мне кажется разумным, это говорить о -полноте принятия решения об игровой ситуации.$\mathcal{NP}$

Давайте возьмем в качестве примера тетрис, так как это единственный из тех, кого вы цитируете, я достаточно понимаю, чтобы говорить о нем. У тетриса есть правило, называемое «совершенная чистка», которое дает игроку большой бонус, если выпадение фигуры полностью очищает игровое поле. Кто-то может задаться вопросом, существует ли допустимая последовательность ходов для кусков заданной упорядоченной последовательностью фигур и целым числом , по крайней мере, совершенных клиров. Постановки задач, подобные тем, которые достаточно абстрактны, могут быть смоделированы с помощью инструментов теории сложности.k P $\{P_i\}$$k$$P$$k$

Короче говоря, « -complete» означает одно и только одно, причудливые утверждения, такие как «Super Mario is -complete», должны быть переведены в формальное утверждение, прежде чем они сделают какие-либо действительные смысл.Н $\mathcal{NP}$$\mathcal{NP}$

Вот упрощенное объяснение для взмахов рук:

Такие игры в NP, потому что «управление» поведением игрока в течение игры и проверка того, выиграл он или проиграл, может быть сделано эффективно (нам нужно, чтобы он был за полиномиальное время на протяжении всей игры, но, вероятно, это линейный или -ish).$O(n \log(n))$

Такие игры NP-трудны, потому что поведение игрока очень выразительно. Хотя в любой данный момент у игрока может быть только ограниченное, даже фиксированное, количество возможных действий, этого достаточно, чтобы создать пространство поведений или стратегий, экспоненциальных на протяжении всей игры; и хотя вы можете быть в состоянии предоставить простое условие или логическую формулу обоснованности / выгоды / правильности действий игрока локально, в глобальном масштабе вы получите эффект, аналогичный большому комбинаторному контуру или формуле k-CNF.

Надеемся, что это имеет некоторый интуитивный смысл, а также звонит достаточно колоколов теории CS.

PS - Некоторые игры намного сложнее (вычислительно). Например, настольные игры Hex , Go и Reversi являются PSPACE-полными. Это в основном потому, что формула, которую вы должны выполнить для выигрышной стратегии, - это формула многократно чередующегося квантификатора: существует ход игрока 1, так что на каждый ход игрока 2 существует ход игрока 1 и т. Д. И т. Д. И т. Д. таким образом, что после всех этих ходов либо ходы игрока 2 являются недействительными, либо мы имеем правильную последовательность, в которой игрок 1 выиграл. В NP играх это, как правило, поведение / стратегия / выбор ходов одного игрока.

В однопользовательских играх вы всегда можете задать вопрос «есть ли выигрышная стратегия для игрока», и на этот вопрос часто дается ответ «ДА», который можно проверить за полиномиальное время, и он вполне может быть закончен NP.

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

Ну, это, безусловно, в NP, потому что возможное решение - это просто конечное количество входов (в каждом входном кадре вы можете выбрать любую из кнопок k, мы представляем каждый выбор кнопок для каждого кадра буквой), что приводит вас к выигрышный экран. Мы знаем, что эта игра была побита раньше, поэтому мы знаем, что существует решение. NTM просматривает свою ленту и волшебным образом угадывает правильный сертификат длины n. Затем он имитирует Super Mario и проверяет его. Проверка может быть выполнена за полиномиальное время (на самом деле, линейное время, если решение правильное, для победы потребуется ровно n кадров).

Чтобы показать NP-полноту, мы могли бы уменьшить до 3-SAT, построив 3-Sat-чекер с генератором уровней (который создается путем выполнения произвольного кода https://www.youtube.com/watch?v=IOsvuEA2h4w ).

Таким образом, у нас есть вход 3-SAT CNF, который мы сначала проверяем на правильное форматирование. Если он плохо отформатирован, мы просто переводим его в один «прыжковый» вход (невозможно превзойти Super Mario в одном кадре, выполнив прыжок).

Мы называем длину входа 3-CNF n.

Если он правильно отформатирован, мы преобразуем его во множество входных данных, которые создают для нас программу проверки 3-CNF (всегда один и тот же код длины k), переводят 3-CNF в строку входных данных, которая создает конкретные 3- CNF в контролере (в O (n)), и проверяет все возможные решения грубой силой. Он бездействует и ничего не делает, если после прохождения всех решений ничего не найдено. Он перезапускает игру и использует известное решение для Super Mario, чтобы пройти игру (код для этого имеет длину j). Таким образом, наше преобразование находится в O (n), то есть в полиномиальном времени.

Если CNF плохо отформатирован, мы не выигрываем (по определению, наши входные данные не выигрывают, если мы не выиграли ни один кадр после его выполнения). Если CNF неудовлетворителен, мы не выигрываем (вы не можете выиграть, простаивая в течение одного кадра в генераторе уровней, мы обеспечили это в нашем коде). Если CNF является удовлетворительным, шашка находит решение перезапускается и выигрывает игру. Таким образом, полиномиальное приведение 3-Sat к Super Mario завершено, и мы доказали, что Super Mario является NP-полной.

(Надеюсь, я где-то не испортил это. Мы сталкиваемся с проблемой хранения, если 3-CNF слишком длинный, но ограниченное хранилище обычно игнорируется в этих контекстах, я полагаю)

Я переписал этот ответ, чтобы попытаться ответить на некоторые комментарии к предыдущей версии.

Я предполагаю, что вы прочитали определение Wikipedia для NP-полноты, которое действительно не фокусируется на играх. Я немного опишу точное значение NP-завершенности и теории игр и объясню суть игры NP-Complete.

Давайте рассмотрим игру с двумя игроками с альтернативными ходами, более ограниченно это по существу о комбинаторных играх . В основном это игра, в которой у вас есть определенное количество ходов, и вы должны выбрать один из них. Вы хотели бы играть «идеально», что означает, что вы никогда не сделаете «плохой» ход. Итак, из допустимых ходов вы бы хотели выбрать лучший. (Конечно, у вашего противника такая же цель ...)

Обратите внимание, что идеальная игра не означает, что вы всегда будете выигрывать. Правила игры могут быть такими, что первый или второй игрок должен выиграть. Также некоторые игры, такие как крестики-нолики, должны заканчиваться ничьей. Таким образом, «идеальная игра» означает в этом обсуждении:
(1) что вы никогда не будете в выигрышной позиции, а затем проиграете, потому что сделали «плохой» ход
(2) вы никогда не упустите возможность получить в выигрышную позицию, если такая возможность возникает.

Учитывая текущее состояние игры, вам нужно иметь возможность использовать «эффективный алгоритм» для расчета наилучшего хода. С другой стороны, отметим, что алгоритм, который должен искать по всему дереву игры, является «неэффективным алгоритмом».

Теперь давайте определим «эффективность» немного более формально. Я собираюсь немного упростить это, но суть верна. Рассмотрим количество вычислений , которое необходимо сделать, чтобы выбрать следующий ход, одно среднее значение каждого хода имеет возможностей ( коэффициент ветвления ) и что в игре осталось ходов. Понятие также , что каждое вычисление занимает столько же времени , так что усилия могут быть переведены на временной сложности , , вместо исходных расчетов.B n $C$$B$$n$$T$

• «Эффективный алгоритм» будет иметь: где - «маленькое целое число» и ах некоторые реальные цифры. Таким образом, эффективный алгоритм выполняется за полиномиальное время, поскольку это полиномиальное выражение.
  $T \varpropto aB^a + bB^{\alpha-1} + cB^{\alpha-2} + ... + hB^0$
  $\alpha$
• «Неэффективный алгоритм» будет иметь: и этот алгоритм выполняется за экспоненциальное время (т.е. за неполиноминальное время). Дело в том, что с увеличением комбинаторный взрыв.
  $T \varpropto aB^n$
  $n$

Важным моментом является то, что невозможно иметь эффективный алгоритм полиномиального времени, который идеально подходит для игры с NP-завершением. Для идеального воспроизведения NP-полной задачи, по определению, необходимо решить с помощью неэффективного алгоритма, который выполняется за неполиномиальное время.

Обратите внимание, что время выполнения зависит от количества вычислений, а не от времени отклика, воспринимаемого человеком. В такой маленькой игре, как Tic-Tac-Toe, компьютер может выполнять все возможные будущие действия и при этом быстро реагировать, как это воспринимает человек.

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

С другой стороны, давайте возьмем игру Qubic . (Вы пытаетесь построить линию 4 в 3D-сетке. Таким образом, это по сути крестики-нолики в сетке 4x4x4.) Qubic является NP-полной, поэтому нет алгоритма полиномиального времени для вычисления следующего совершенного движения. Единственный способ узнать, есть ли у вас выигрышный ход, состоит в том, чтобы попробовать все возможные ходы обоих игроков, чтобы убедиться, что тот или иной ход является победителем или, по крайней мере, не проигравшим.

По правде говоря, все дерево игр для Qubic достаточно маленькое, чтобы его можно было закодировать в компьютерную программу, которая может отлично играть. Что означает кодирование, так это то, что все дерево игры было исследовано, и все ходы проработаны заранее. Таким образом, программа может по существу выполнить быстрый вызов базы данных, используя текущее состояние доски, и получить лучший ход для этого состояния доски, не выполняя поиск по дереву каждый раз, когда должен быть сделан ход. Это действительно «чит» для наших целей здесь.

Теперь давайте обсудим шахматы, чтобы обсудить функцию оценки, игнорируя некоторые другие особенности программ игры в шахматы. Шахматы до сих пор не решены . Неизвестно, должен ли победить первый или второй игрок. Невозможно получить какую-либо позицию на доске и предсказать с уверенностью, кто победит. На самом деле шахматы имеют такое большое игровое дерево, что просто невозможно обыскать все игровое дерево. Вам понадобятся компьютеры, которые не только в 10 или 100 раз быстрее, но и в миллиарды миллиардов раз быстрее, чем любой другой компьютер. (Есть надежда, что квантовые вычисления могут пробиться через этот гордиев узел.)

Представьте себе, что функция оценки шахмат дает каждому возможному следующему ходу вероятность быть лучшим ходом. Шахматная программа сочетает в себе взгляды на будущее и функцию оценки. Таким образом, программа рассматривает все возможные будущие ходы, пока не достигнет точки, где «положительная» оценка может быть дана позиции доски. Таким образом, компьютер оценивает все возможные пути через дерево, а затем выбирает путь с наилучшей оценкой. Поскольку поиск по всем пройденным путям никогда не доходил до конца игры, все шахматные программы в конечном итоге используют несовершенную функцию оценки. (Если вы близки к концу игры, то компьютер может просматривать все возможные будущие ходы.) Это означает, что возможно победить программу, даже если в какой-то момент программа имела выигрышную позицию.