  We introduce and study pawn games, a class of two-player zero-sum turn-based
graph games. A turn-based graph game proceeds by placing a token on an initial
vertex, and whoever controls the vertex on which the token is located, chooses
its next location. This leads to a path in the graph, which determines the
winner. Traditionally, the control of vertices is predetermined and fixed. The
novelty of pawn games is that control of vertices changes dynamically
throughout the game as follows. Each vertex of a pawn game is owned by a pawn.
In each turn, the pawns are partitioned between the two players, and the player
who controls the pawn that owns the vertex on which the token is located,
chooses the next location of the token. Control of pawns changes dynamically
throughout the game according to a fixed mechanism. Specifically, we define
several grabbing-based mechanisms in which control of at most one pawn
transfers at the end of each turn. We study the complexity of solving pawn
games, where we focus on reachability objectives and parameterize the problem
by the mechanism that is being used and by restrictions on pawn ownership of
vertices. On the positive side, even though pawn games are
exponentially-succinct turn-based games, we identify several natural classes
that can be solved in PTIME. On the negative side, we identify several
EXPTIME-complete classes, where our hardness proofs are based on a new class of
games called Lock & Key games, which may be of independent interest.
