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 $n\backslash times\; n$ board, with $2n$ pieces on each side. Generalized Sudoku includes Sudokus constructed on an $n\backslash 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.{{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

}}{{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 $n\backslash times\; n$ board is PSPACE-complete

| volume = 123| doi-access =

}}

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,{{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}} and checkers are EXPTIME-complete.{{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 $n\backslash times\; n$ chess requires time exponential in $n$

| volume = 31| doi-access =

}}{{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}}{{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 = $N$ by $N$ checkers is Exptime complete

| volume = 13}}