  We initiate the study of the algorithmic complexity of Maker-Breaker games
played on the edge sets of general graphs. We mainly consider the perfect
matching game and the $H$-game. Maker wins if she claims the edges of a perfect
matching in the first, and a copy of a fixed graph $H$ in the second. We prove
that deciding who wins the perfect matching game and the $H$-game is
PSPACE-complete, even for the latter in small-diameter graphs if $H$ is a tree.
Toward finding the smallest graph $H$ for which the $H$-game is
PSPACE-complete, we also prove that such an $H$ of order 51 and size 57 exists.
  We then give several positive results for the $H$-game. As the $H$-game is
already PSPACE-complete when $H$ is a tree, we mainly consider the case where
$H$ belongs to a subclass of trees. In particular, we design two linear-time
algorithms, both based on structural characterizations, to decide the winners
of the $P_4$-game in general graphs and the $K_{1,\ell}$-game in trees. Then,
we prove that the $K_{1,\ell}$-game in any graph, and the $H$-game in trees are
both FPT parameterized by the length of the game, notably adding to the short
list of games with this property, which is of independent interest.
  Another natural direction to take is to consider the $H$-game when $H$ is a
cycle. While we were unable to resolve this case, we prove that the related
arboricity-$k$ game is polynomial-time solvable. In particular, when $k=2$,
Maker wins this game if she claims the edges of any cycle.
