Generalized game

Generalized game

In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board 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.

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.

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 and checkers are EXPTIME-complete.

ee also

*Game complexity
*Combinatorial game theory
*Connect6
*Go (board game)

External links

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Generalized game theory — is an extension of game theory to incorporate social theory concepts such as norm, value, belief, role, social relationship, and institution. The theory was developed by Tom R. Burns and has not had great influence beyond his immediate associates …   Wikipedia

  • Game complexity — Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state space complexity, game tree size, decision complexity, game tree complexity, and computational complexity. Contents 1 Measures of… …   Wikipedia

  • Generalized geography — In computational complexity theory, generalized geography is a problem that can be proven to be PSPACE Complete.IntroductionGeography is a childs game, which is good for a long car trip, where players take turns naming cities from anywhere in the …   Wikipedia

  • Game of the Amazons — Infobox Game subject name=The Game of the Amazons image link=Chess diagram 10x10|= tright = 10| | | |qd| | |qd| | | |= 9 | | | | | | | | | | |= 8 | | | | | | | | | | |= 7 |qd| | | | | | | | |qd|= 6 | | | | | | | | | | |= 5 | | | | | | | | | | |=… …   Wikipedia

  • List of game topics — The list of game topics aims to list articles related to games.#8 bit era 16 bit era 32 bit and 64 bit era 128 bit eraAAbalone (board game) Abandonware Abstract strategy game Acquire Advanced Dungeons Dragons Advanced Squad Leader Adventure game… …   Wikipedia

  • number game — Introduction       any of various puzzles and games that involve aspects of mathematics.       Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… …   Universalium

  • M,n,k-game — An m,n,k game is an abstract board game in which two players take turns in placing a stone of their color on an m times; n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or… …   Wikipedia

  • IBM Generalized Markup Language — Infobox file format name = IBM Generalized Markup Language icon = logo = extension = mime = type code = uniform type = magic = owner = IBM genre = container for = contained by = extended from = extended to = SGML standard = Generalized Markup… …   Wikipedia

  • Board game — A board game is a game in which counters or pieces that are placed on, removed from, or moved across a board (a premarked surface usually specific to that game). As do other form of entertainment, board games can represent nearly any subject.… …   Wikipedia

  • Conway's Game of Life — Conway game , which redirects to here, can also refer to games as defined by surreal numbers, which John Conway also developed …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”