Generalized game

Sudoku (4×4)

Sudoku (9×9)

Sudoku (25×25)

Generalized Sudoku includes puzzles of different sizes

In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an $n\times n$ board, with $2n$ pieces on each side. Generalized Sudoku includes Sudokus constructed on an $n\times n$ grid.

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. Generalized hex and reversi are PSPACE-complete.

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, and checkers are EXPTIME-complete.

See also

• Game complexity
• Combinatorial game theory