Is there a simple game with asymmetric complexity? 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.
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.