# 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 ${\displaystyle n\times n}$ board, with ${\displaystyle 2n}$ pieces on each side. Generalized Sudoku includes Sudokus constructed on an ${\displaystyle 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.[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.[4][5][6]

2. ^ Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an ${\displaystyle n\times n}$ board is PSPACE-complete", Theoretical Computer Science, 123 (2): 329–340, doi:10.1016/0304-3975(94)90131-7
4. ^ Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for ${\displaystyle n\times n}$ chess requires time exponential in ${\displaystyle n}$", Journal of Combinatorial Theory, Series A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9
6. ^ Robson, J. M. (May 1984), "${\displaystyle N}$ by ${\displaystyle N}$ checkers is Exptime complete", SIAM Journal on Computing, Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi:10.1137/0213018