  We consider combinatorial avoidance and achievement games based on graph
Ramsey theory: The players take turns in coloring still uncolored edges of a
graph G, each player being assigned a distinct color, choosing one edge per
move. In avoidance games, completing a monochromatic subgraph isomorphic to
another graph A leads to immediate defeat or is forbidden and the first player
that cannot move loses. In the avoidance+ variants, both players are free to
choose more than one edge per move. In achievement games, the first player that
completes a monochromatic subgraph isomorphic to A wins. Erdos & Selfridge
(1973) were the first to identify some tractable subcases of these games,
followed by a large number of further studies. We complete these investigations
by settling the complexity of all unrestricted cases: We prove that general
graph Ramsey avoidance, avoidance+, and achievement games and several variants
thereof are PSPACE-complete. We ultra-strongly solve some nontrivial instances
of graph Ramsey avoidance games that are based on symmetric binary Ramsey
numbers and provide strong evidence that all other cases based on symmetric
binary Ramsey numbers are effectively intractable.
  Keywords: combinatorial games, graph Ramsey theory, Ramsey game,
PSPACE-completeness, complexity, edge coloring, winning strategy, achievement
game, avoidance game, the game of Sim, Polya's enumeration formula,
probabilistic counting, machine learning, heuristics, Java applet
