Generalized game information

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.^[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]

^ Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/bf00288964, S2CID 9125259
^ Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an $n\times n$ board is PSPACE-complete", Theoretical Computer Science, 123 (2): 329–340, doi:10.1016/0304-3975(94)90131-7
^ Mishiba, Shohei; Takenaga, Yasuhiko (2020-07-02). "QUIXO is EXPTIME-complete". Information Processing Letters. 162: 105995. doi:10.1016/j.ipl.2020.105995. ISSN 0020-0190.
^ Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$ ", Journal of Combinatorial Theory, Series A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9
^ Robson, J. M. (1983), "The complexity of Go", Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417
^ Robson, J. M. (May 1984), " $N$ by $N$ checkers is Exptime complete", SIAM Journal on Computing, 13 (2), Society for Industrial & Applied Mathematics ({SIAM}): 252–267, doi:10.1137/0213018

[1] Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/bf00288964, S2CID 9125259

[2] Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an $n\times n$ board is PSPACE-complete", Theoretical Computer Science, 123 (2): 329–340, doi:10.1016/0304-3975(94)90131-7

[3] Mishiba, Shohei; Takenaga, Yasuhiko (2020-07-02). "QUIXO is EXPTIME-complete". Information Processing Letters. 162: 105995. doi:10.1016/j.ipl.2020.105995. ISSN 0020-0190.

[4] Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for $n\times n$ chess requires time exponential in $n$ ", Journal of Combinatorial Theory, Series A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9

[5] Robson, J. M. (1983), "The complexity of Go", Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417

[6] Robson, J. M. (May 1984), " $N$ by $N$ checkers is Exptime complete", SIAM Journal on Computing, 13 (2), Society for Industrial & Applied Mathematics ({SIAM}): 252–267, doi:10.1137/0213018

Generalized game information

and 18 Related for: Generalized game information

Generalized game

Generalized game theory

Game complexity

Generalized other

Generalized anxiety disorder

Peg solitaire

FreeCell

Generalized geography

Game of the Amazons

Board game

Word chain

Generalized exchange

Potential game

Busy beaver

Social rule system theory

Aggregative game

Turing test

Match Game