Complexity theory studies the asymptotic difficulty of problems, so generalizations of games are needed, as games on a fixed size of board are finite problems.
For many generalized games which last for a number of moves polynomial in the size of the board, the problem of determining if there is a win for the first player in a given position is PSPACE-complete.
[1][2] For many generalized games which may last for a number of moves exponential in the size of the board, the problem of determining if there is a win for the first player in a given position is EXPTIME-complete.
Generalized chess, go (with Japanese ko rules), Quixo,[3] and checkers are EXPTIME-complete.
You can help Wikipedia by expanding it.This theoretical computer science–related article is a stub.