Generalized game

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.

Sudoku (4×4)

Sudoku (9×9)

Sudoku (25×25)

Generalized Sudoku includes puzzles of different sizes

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]

References

^ 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

This game theory article is a stub. You can help Wikipedia by expanding it.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[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

[1]

[2]

[3]

[4]

[5]

[6]

Generalized game

See also

References