This paper studies provenance in databases from a game-theoretic perspective. In particular, we address provenance for first-order logic (FO) queries that involve negation but do not involve recursion. We model query evaluation as a two-player game, where players argue over which tuples are included in the query result. This game-theoretic approach provides a natural provenance model that integrates how and why-not provenance tracing. We study the detailed structure of this game provenance tracing, and identify seven types of edges that occur during the game's resolution, proposing new types of provenance tracing: latent, actual, and prime provenance tracing. We show that "not all moves are equivalent," describe the new provenance tracing types, present a computational methodology, and discuss applications such as an abstract argumentation framework.