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 board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an 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]

See also

References
  1. Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica, 15 (2): 167–191, doi:10.1007/bf00288964
  2. Iwata, Shigeki; Kasai, Takumi (January 1994), "The Othello game on an 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: 105995. doi:10.1016/j.ipl.2020.105995. ISSN 0020-0190.
  4. Fraenkel, Aviezri S.; Lichtenstein, David (September 1981), "Computing a perfect strategy for chess requires time exponential in ", 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), " by checkers is Exptime complete", SIAM Journal on Computing, Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi:10.1137/0213018
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.