Editing Generalized game

{{short description|Game generalized so that it can be played on a board or grid of any size}}
{{multiple image
 | width = 180
 | footer = Generalized [[Sudoku]] includes puzzles of different sizes
 | image1 = Minisudoku1.png
 | alt1 = Sudoku (4×4)
 | caption1 = Sudoku (4×4)
 | image2 = Sudoku_Puzzle_(Tourmaline)R2.png
 | alt2 = Sudoku (9×9)
 | caption2 = Sudoku (9×9)
 | image3 = 25by25sudoku.png
 | alt3 = Sudoku (25×25)
 | caption3 = Sudoku (25×25)
 }}
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 <math>n\times n</math> board, with <math>2n</math> pieces on each side. Generalized [[Sudoku]] includes Sudokus constructed on an <math>n\times n</math> 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 (board game)|hex]] and [[reversi]] are PSPACE-complete.<ref>{{citation
 | last = Reisch | first = Stefan
 | doi = 10.1007/bf00288964
 | issue = 2
 | journal = Acta Informatica
 | pages = 167–191
 | title = Hex ist PSPACE-vollständig
 | volume = 15
 | year = 1981| s2cid = 9125259
 }}</ref><ref>{{citation
 | last1 = Iwata | first1 = Shigeki
 | last2 = Kasai | first2 = Takumi
 | date = January 1994
 | doi = 10.1016/0304-3975(94)90131-7
 | issue = 2
 | journal = Theoretical Computer Science
 | pages = 329–340
 | title = The Othello game on an <math>n\times n</math> board is PSPACE-complete
 | volume = 123| doi-access = 
 }}</ref>

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 (board game)|go]] (with Japanese ko rules), [[Quixo]],<ref>{{Cite journal|last1=Mishiba|first1=Shohei|last2=Takenaga|first2=Yasuhiko|date=2020-07-02|title=QUIXO is EXPTIME-complete|journal=Information Processing Letters|volume=162 |language=en|pages=105995|doi=10.1016/j.ipl.2020.105995|issn=0020-0190|doi-access=free}}</ref> and [[checkers]] are EXPTIME-complete.<ref>{{citation
 | last1 = Fraenkel | first1 = Aviezri S.
 | last2 = Lichtenstein | first2 = David
 | date = September 1981
 | doi = 10.1016/0097-3165(81)90016-9
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series A
 | pages = 199–214
 | title = Computing a perfect strategy for <math>n\times n</math> chess requires time exponential in <math>n</math>
 | volume = 31| doi-access = 
 }}</ref><ref>{{citation
 | last = Robson | first = J. M.
 | journal = Proceedings of the IFIP 9th World Computer Congress on Information Processing
 | pages = 413–417
 | title = The complexity of Go
 | year = 1983}}</ref><ref>{{citation
 | last = Robson | first = J. M.
 | date = May 1984
 | doi = 10.1137/0213018
 | issue = 2
 | journal = SIAM Journal on Computing
 | pages = 252–267
 | publisher = Society for Industrial & Applied Mathematics ({SIAM})
 | title = <math>N</math> by <math>N</math> checkers is Exptime complete
 | volume = 13}}</ref>

==See also==
*[[Game complexity]]
*[[Combinatorial game theory]]

==References==
{{reflist}}

[[Category:Computational complexity theory]]
[[Category:Combinatorial game theory]]

{{gametheory-stub}}
{{comp-sci-theory-stub}}