Обобщённая география: PSPACE-полнота и связь с формульной игрой.

Введение

В теории вычислительной сложности обобщённая география — известная PSPACE-полная задача.

Введение

География – это детская игра, где игроки по очереди называют города из любой точки мира. Каждый выбранный город должен начинаться с той же буквы, которой заканчивается название предыдущего города. Повторять города нельзя. Игра начинается с любого стартового города и заканчивается, когда игрок не может назвать следующий город.

Модель графика

Для визуализации игры можно построить ориентированный граф, вершинами которого являются города мира. От вершины N1 к вершине N2 добавляется дуга тогда и только тогда, когда название города, соответствующего N2, начинается с буквы, которой заканчивается название города, соответствующего вершине N1. Иными словами, мы проводим дугу от одного города к другому, если по правилам игры из первого города можно назвать второй. Каждое альтернативное ребро в ориентированном графе соответствует одному из игроков (в игре для двух игроков). Игрок, который не может продолжить путь, проигрывает. Пример игры (включающий некоторые города штата Мичиган) показан на рисунке ниже. В обобщенной географической игре (GG) граф названий городов заменяется произвольным ориентированным графом. Приведенный ниже граф является примером обобщенной географической игры.

Играть в игру

Мы определяем P1 как игрока, ходящего первым, а P2 как игрока, ходящего вторым, и называем узлы от N1 до Nn. На приведенной выше схеме у P1 есть выигрышная стратегия: узел N1 указывает только на узлы N2 и N3. Следовательно, первый ход P1 должен быть одним из этих двух вариантов. P1 выбирает N2 (если P1 выберет N3, то P2 выберет N9, так как это единственный возможный ход, и P1 проиграет). Затем P2 выбирает N4, поскольку это единственный оставшийся вариант. P1 выбирает N5, а P2 в ответ выбирает N3 или N7. Независимо от выбора P2, P1 выбирает N9, и у P2 не остается ходов, что приводит к его поражению.

Комплексность вычислений

Проблема определения наличия выигрышной стратегии у игрока в обобщённой игре в географию является PSPACE-полной.

Обобщенная география является PSPACE-жесткой

Следующее доказательство принадлежит Дэвиду Лихтенштейну и Майклу Сипсеру. Чтобы установить PSPACE-трудность GG, мы можем свести задачу FORMULA GAME (которая, как известно, является PSPACE-трудной) к GG за полиномиальное время (P). Вкратце, экземпляр задачи FORMULA GAME состоит из квантованной булевой формулы φ = ∃x1 ∀x2 ∃x3 … Qxk(ψ), где Q — это либо ∃, либо ∀. В игру играют два игрока, Pa и Pe, которые поочередно выбирают значения для последовательных xi. Pe выигрывает игру, если формула ψ оказывается истинной, а Pa выигрывает, если ψ оказывается ложной. Формула ψ предполагается заданной в конъюнктивной нормальной форме. Для упрощения в этом доказательстве мы предполагаем, что список кванторов начинается и заканчивается экзистенциальным квантором, ∃. Следует отметить, что любое выражение можно привести к этой форме, добавив фиктивные переменные, которые не встречаются в ψ. Построив граф G, как показано выше, мы покажем, что любой экземпляр задачи FORMULA GAME можно свести к экземпляру Generalized Geography, где оптимальная стратегия для P1 эквивалентна стратегии Pe, а оптимальная стратегия для P2 эквивалентна стратегии Pa. Левая вертикальная цепочка узлов предназначена для имитации процедуры выбора значений для переменных в FORMULA GAME. Каждая структура в виде ромба соответствует квантованной переменной. Игроки по очереди выбирают пути в каждом узле ветвления. Поскольку мы предположили, что первый квантор будет экзистенциальным, P1 ходит первым, выбирая левый узел, если x1 истинно, и правый узел, если x1 ложно. Затем каждый игрок делает вынужденные ходы, после чего P2 выбирает значение для x2. Эти чередующиеся назначения продолжаются вниз по левой стороне. После того как оба игрока пройдут через все ромбы, снова наступает ход P1, поскольку мы предположили, что последний квантор является экзистенциальным. У P1 нет выбора, кроме как следовать по пути в правую сторону графа. Затем наступает ход P2. Когда игра доходит до правой стороны графа, это напоминает конец игры в FORMULA GAME. Вспомним, что в FORMULA GAME Pe выигрывает, если ψ истинно, а Pa выигрывает, если ψ ложно. Правая сторона графа гарантирует, что P1 выигрывает тогда и только тогда, когда выигрывает Pe, и что P2 выигрывает тогда и только тогда, когда выигрывает Pa. Сначала покажем, что P2 всегда выигрывает, когда выигрывает Pa. Если Pa выигрывает, то ψ ложно. Если ψ ложно, то существует неудовлетворимое предложение. P2 выберет неудовлетворимое предложение, чтобы выиграть. Когда наступит ход P1, он должен выбрать литерал в этом предложении, выбранном P2. Поскольку все литералы в предложении ложны, они не связаны с ранее посещенными узлами в левой вертикальной цепочке. Это позволяет P2 следовать по связи к соответствующему узлу в ромбе левой цепочки и выбрать его. Однако P1 теперь не может выбрать ни одного соседнего узла и проигрывает. Теперь покажем, что P1 всегда выигрывает, когда выигрывает Pe. Если Pe выигрывает, то ψ истинно. Если ψ истинно, то каждое предложение в правой части графа содержит истинный литерал. P2 может выбрать любое предложение. Затем P1 выбирает истинный литерал. И поскольку он истинный, его соседний узел в левой вертикальной цепочке уже выбран, поэтому P2 не может сделать ход и проигрывает.

The following proof is due to David Lichtenstein and Michael Sipser. To establish the PSPACE hardness of GG, we can reduce the FORMULA GAME problem (which is known to be PSPACE hard) to GG in polynomial time (P). In brief, an instance of the FORMULA GAME problem consists of a quantified Boolean formula φ = ∃x1 ∀x2 ∃x3 Qxk(ψ) where Q is either ∃ or ∀. The game is played by two players, Pa and Pe, who alternate choosing values for successive xi. Pe wins the game if the formula ψ ends up true, and Pa wins if ψ ends up false. The formula ψ is assumed to be in conjunctive normal form. In this proof, we assume that the quantifier list starts and ends with the existential qualifier, ∃, for simplicity. Note that any expression can be converted to this form by adding dummy variables that do not appear in ψ. By constructing a graph G like the one shown above, we will show any instance of FORMULA GAME can be reduced to an instance of Generalized Geography, where the optimal strategy for P1 is equivalent to that of Pe, and the optimal strategy for P2 is equivalent to that of Pa. The left vertical chain of nodes is designed to mimic the procedure of choosing values for variables in FORMULA GAME. Each diamond structure corresponds to a quantified variable. Players take turns deciding paths at each branching node. Because we assumed the first quantifier would be existential, P1 goes first, selecting the left node if x1 is true and the right node if x1 is false. Each player must then take forced turns, and then P2 chooses a value for x2. These alternating assignments continue down the left side. After both players pass through all the diamonds, it is again P1 's turn, because we assumed that the last quantifier is existential. P1 has no choice but to follow the path to the right side of the graph. Then it is P2 's turn to make a move. When the play gets to the right side of the graph, it is similar to the end of play in the formula game. Recall that in the formula game, Pe wins if ψ is true, while Pa wins if ψ is false. The right side of the graph guarantees that P1 wins if and only if Pe wins, and that P2 wins if and only if Pa wins. First we show that P2 always wins when Pa wins. If Pa wins, ψ is false. If ψ is false, there exists an unsatisfying clause. P2 will choose an unsatisfying clause to win. Then when it is P1's turn he must choose a literal in that clause chosen by P2. Since all the literals in the clause are false, they do not connect to previously visited nodes in the left vertical chain. This allows P2 to follow the connection to the corresponding node in a diamond of the left chain and select it. However, P1 is now unable to select any adjacent nodes and loses. Now we show that P1 always wins when Pe wins. If Pe wins, ψ is true. If ψ is true, every clause in the right side of the graph contains a true literal. P2 can choose any clause. Then P1 chooses the literal that is true. And because it is true, its adjacent node in the left vertical node has already been selected, so P2 has no moves to make and loses.

Плоская обобщенная география является PSPACE-комплектной

Обобщенная география является PSPACE-полной задачей, даже при игре на планарных графах. Доказательство приведено из теоремы 3.

Ненаправленная география

Можно также рассмотреть игру в «Географию» на неориентированном графе (то есть, по ребрам можно двигаться в обоих направлениях). Френкель, Шейнерман и Уллман показали, что «География вершин» на неориентированном графе может быть решена за полиномиальное время, в то время как «География ребер» на неориентированном графе является PSPACE-полной задачей, даже для планарных графов с максимальной степенью 3. Если граф является двудольным, то «География ребер» на неориентированном графе разрешима за полиномиальное время.

Последствия

Учитывая, что GG является PSPACE-полной, не существует алгоритма полиномиального времени для оптимальной игры в GG, если P = PSPACE. Однако доказать сложность других игр может оказаться сложнее, поскольку в некоторых играх (таких как шахматы) конечное число игровых позиций, что затрудняет (или делает невозможным) установление связи с PSPACE-полной задачей. Несмотря на это, сложность некоторых игр все еще можно анализировать путем обобщения (например, рассматривая поле n × n). Подробности доказательства для обобщенного Go можно найти в указанных ссылках, как следствие доказательства полноты GG.