Generalized game: Difference between revisions
imported>OAbot m Open access bot: doi updated in citation with #oabot. |
imported>Citation bot Added article-number. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Computational complexity theory | #UCB_Category 53/110 |
||
| Line 38: | Line 38: | ||
}}</ref> | }}</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| | 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. | | last1 = Fraenkel | first1 = Aviezri S. | ||
| last2 = Lichtenstein | first2 = David | | last2 = Lichtenstein | first2 = David | ||
Latest revision as of 07:36, 21 July 2025
Template:Short description Script error: No such module "Multiple image". 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.
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
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".