Generalized game: Difference between revisions

Revision as of 16:59, 10 July 2004

Latest revision as of 07:36, 21 July 2025

(22 intermediate revisions by 14 users not shown)

Line 1:

In{{short [[computational complexity theory]], a '''generalized game''' is a game that has beendescription|Game 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''-by-''n'' board, with 2''n'' pieces on each side.}}

{{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|article-number=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>

==ExternalSee linksalso==

*[[Game complexity]]

* David Eppstein's page on [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]

*[[Combinatorial game theory]]

==References==

{{reflist}}

[[Category:Computational complexity theory]]

[[Category:Combinatorial game theory]]

{{gametheory-stub}}

{{comp-sci-theory-stub}}