Is there a simple game with asymmetric complexity?

Question

Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves. The usual question is, how difficult it is to tell from a given position the winner. Another would be, how difficult it is to pick a winning move from a winning position. (Here I call a move winning, if the position remains winning after playing it.) To differentiate, I will call the former POSITION-COMPLEXITY and the latter MOVE-COMPLEXITY.

It is easy to see that if the MOVE-COMPLEXITY is in $P$ or $PSPACE$, then so is the POSITION-COMPLEXITY - we can calculate the optimal moves and check who wins at the end. (I have not really thought through what happens if the MOVE-COMPLEXITY is in $NP$, probably the POSITION-COMPLEXITY is in something like $P^{NP}$.) However, there are dummy examples when the MOVE-COMPLEXITY is trivial and the POSITION-COMPLEXITY is arbitrary hard - like the (not very interesting) game of checking what is the output of an algorithm, with the players making the next steps, being allowed only one move. I have digressed a bit, my main question is the following.

Is there a natural game, where the MOVE-COMPLEXITY of the two players is different?

For example, the game where the first player picks the values of the variables of a CNF (that might not have a solution), while the second player is trying to solve a SOKO-BAN puzzle (that might not have a solution), is such an example.

Answer 1

Perhaps a fairly natural game is the following:

Player 1 is placed in the middle of a maze and must reach the exit in order to win.

Player 2 is in the same maze and must collect a set of "components" to build a radio controller that lets him close the exit (and win).

Deciding the next move from a winning position is easy for Player 1: just follow the shortest path from his current position and the exit; but can be very hard for Player 2.
Indeed if the (remaining) components of the radio controller are on the vertices of a grid graph of $n$ nodes (suppose that Player 2 is himself on an adjacent vertex) and the distance between Player 1 and the exit is exactly $n$, then he must find an Hamiltonian path in order to move.

To make the game more "interactive", we can also add some extra actions to Player 2 that can only cause a polynomial slowdown in the calculation of the next move for Player 1; for example allowing him to block a fixed numbers of corridors of the maze.

Answer 2

By your constraints, we also have the stronger opposite relation: if POSITION-COMPLEXITY is in a class $C$, then so is MOVE-COMPLEXITY, since it suffices to test the finite number of available moves. (I assumed by "finite" you meant "constant", if it is arbitrary then the complexity might change).

Then it suffices to look at some natural games where POSITION-COMPLEXITY is asymmetric. We will always need some asymmetry between the players to create such situations, but hopefully it will be as natural as possible.

In my opinion partial observation games are a good example of this: they are played on finite arena, and one player knows the current vertex at all times while the other only knows in which group the current vertex is (they are arbitrarily grouped together). The most classical example of this is parity games, where the number of moves is infinite. There the POSITION-complexity is EXPTIME-complete for the partial player versus linear/quadratic/NP$\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$".

Answer 3

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