Есть ли простая игра с асимметричной сложностью?

Рассмотрим полную информацию о комбинаторных играх для двух игроков, которые заканчиваются после полиномиального числа ходов, и поочередно игроки выбирают из конечного числа разрешенных ходов. Обычный вопрос в том, насколько сложно с определенной позиции отличить победителя. Другой будет, как трудно выбрать выигрышный ход из выигрышной позиции. (Здесь я называю ход выигрышным, если позиция остается выигрышной после игры.) Чтобы провести различие, я назову первую СЛОЖНОСТЬ ПОЗИЦИИ, а последнюю - СЛОЖНОСТЬ ПЕРЕМЕЩЕНИЯ.

$P$ $PSPACE$ $NP$ $P^{NP}$

Существует ли естественная игра, в которой СВОЙСТВО ПЕРЕМЕЩЕНИЯ двух игроков отличается?

Например, игра, в которой первый игрок выбирает значения переменных CNF (которые могут не иметь решения), а второй игрок пытается решить головоломку SOKO-BAN (которая может не иметь решения), такой пример.

cc.complexity-theory np board-games pspace domotorp
источник

Мне очень нравится этот вопрос.

Tayfun Pay

Я не знаю, если игра QBF удовлетворяет вашим условиям, один игрок - экзистенциальный игрок, другой - универсальный игрок. Ну, многие игры в похожей форме. Я думаю, что если между игроками нет зависимости, то игра не является игрой для двух игроков, но если между ними есть зависимость, то (смутно говоря) есть некоторые интерпретации, похожие на стиль QBF.

Саид

Это побочное замечание, но большинство естественных игр (в том смысле, что в них играют в реальном мире, таких как шахматы, иди ...) не заканчиваются после полиномиального числа ходов, а скорее экспоненциально (в худшем случае). Есть ли у вас особая причина для добавления этого ограничения, помимо получения полиномиальной связи между MOVE-COMPLEXITY и POSITION-COMPLEXITY?

Денис

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

Марцио Де Биаси

Если в игре нет ничьих (и разумно ограниченное количество возможных ходов за ход), означает ли следующий факт ответ «нет»? Ход выигрывает тогда и только тогда, когда ни один из ответов оппонента на него не выигрывает.

Усул

Ответы:

Возможно, довольно естественная игра заключается в следующем:

Игрок 1 находится в середине лабиринта и должен достичь выхода, чтобы выиграть.

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

$n$ $n$

Чтобы сделать игру более «интерактивной», мы также можем добавить некоторые дополнительные действия для игрока 2, которые могут вызвать только полиномиальное замедление в расчете следующего хода для игрока 1; например, разрешив ему заблокировать фиксированное количество коридоров лабиринта.

Марцио де Биаси
источник

$C$

Тогда достаточно взглянуть на некоторые естественные игры, в которых ПОЗИЦИОННО-СЛОЖНОСТЬ асимметрична. Нам всегда понадобится некоторая асимметрия между игроками, чтобы создать такие ситуации, но, надеюсь, это будет настолько естественно, насколько это возможно.

$\cap$ coNP for the full player, depending on the complexity of the winning condition. See here for a reference on the subject.

I think from this we can design a game played in finite time where one player has partial observation, and the other full observation, and the POSITION-complexity as well as MOVE-complexity are very different. Natural try is partitioning vertices in $P_1$ and $P_2$ and setting the winning condition to "play $p(n)$ moves, Player $i$ wins if we end in partition $P_i$ ".

Denis
источник

I would argue it's unlikely that "finite" means "constant" here.

Kyle

In fact, in the so-called Picker-Chooser or Chooser-Picker games it is easy to construct examples for which one player's best strategy is a simple pairing strategy, while the other has to solve a 3-SAT on any CNF specified before, that is an NP-complete problem.

Say, a Picker-Chooser games is an asymmetric game on an hypergraph H=(V, E): Picker picks two unselected elements of V, then Chooser takes one of these, and returns the other to Picker. Chooser wins iff he gets all elements of an A from E. Now given a CNF formula F from 3-SAT, V is the set of literals, and E realizes some gadget. All in all, Picker must always offer x_i and x_i negate in all steps (otherwise loses immediately), while Chooser selection is an arbitrary 0-1 input for any x_i, and he wins by satisfying F.

See the details in: A. Csernenszky, R. Martin and A. Pluhár, On the Complexity of Chooser-Picker Positional Games. Integers 11 (2011).

or at: http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf

Andras Pluhar
источник