Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > 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 2n 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.

External links

David Eppstein's page on Computational Complexity of Games and Puzzles

<Hide>

Topics: Generalized Game, Generalized Mean, Generalized Riemann...

Generalized meanA generalized mean or power mean is an abstraction of the arithmetic, geometric and harmonic means. If t is a non-zero real number, we can define the generalized mean with exponent t of the positive real numbers a . a as : The case t 1 yields the arithmet	Generalized Riemann hypothesisAnalytic number theory Algebraic number theory Algebraic geometry Conjectures The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmeti	Generalized Fourier seriesIn mathematical analysis, there are many potentially useful generalizations of Fourier series. For a set of square-integrable, pairwise-orthogonal (with respect to some weight function w ''x ) functions : the generalized Fourier series of a square-integra
Generalized permutation matrixIn matrix theory, a generalized permutation matrix is a matrix with the same nonzero pattern as a permutation matrix, i. there is exactly one nonzero entry in each row and each column. An example of generalized permutation matrix is : An interesting theor	Generalized orthogonal groupIn mathematics, the generalized orthogonal group O p q is the Lie group of all linear transformations of a p + q n dimensional real vector space which leave invariant a nondegenerate, symmetric, bilinear form of signature p q . The dimension of the group	Generalized System of PreferencesThe Generalized System of Preferences (or GSP is a program managed by the USTR to grant trade advantages (such as reduced tariff levels) to particular developing countries, in cases where the United States is pleased with policy directions taken by those
Generalized Gauss-Bonnet theorem	Generalized nondeterministic finite state machine	Generalized star height problem
Generalized taxicab number	Generalized continued fraction	Generalized game
Generalized linear model	Generalized other	Generalized theory of gravitation

Non User