In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, 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
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
is the game of
chess
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
played on an
board, with
pieces on each side. Generalized
Sudoku
Sudoku (; ; originally called Number Place) is a logic puzzle, logic-based, combinatorics, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and ...
includes Sudokus constructed on an
grid.
Complexity theory studies the
asymptotic
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates Limit of a function#Limits at infinity, tends to infinity. In pro ...
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
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...
. 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
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
,
go (with Japanese ko rules),
Quixo, and
checkers
Checkers (American English), also known as draughts (; English in the Commonwealth of Nations, Commonwealth English), is a group of Abstract strategy game, strategy board games for two players which involve forward movements of uniform game ...
are EXPTIME-complete.
See also
*
Game complexity
Combinatorial game theory measures game complexity in several ways:
#State-space complexity (the number of legal game positions from the initial position)
#Game tree size (total number of possible games)
#Decision complexity (number of leaf nod ...
*
Combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
References
Computational complexity theory
Combinatorial game theory
{{comp-sci-theory-stub