All Topics  
Game complexity

 

 
   Email Print
   Bookmark   Link
 

 

Game complexity
 
 
  Topics Game complexity Topic Home

Combinatorial game theory
Combinatorial game theory

Combinatorial game theory is a mathematics theory that only studies two-player games which have a position which the players take turns changing in defined ways or moves to achieve a defined winning condition....
 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.


Useful when this is too hard to calculate, an upper bound
Upper bound

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S....
 can often be computed by including illegal positions or positions that can never arise in the course of a game.



The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe
Tic-tac-toe

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a paper and pencil game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first....
 game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed).






Discussion
Ask a question about 'Game complexity'
Start a new discussion about 'Game complexity'
Answer questions from other users
Full Discussion Forum



Encyclopedia


Go Game Ear Reddening
Combinatorial game theory
Combinatorial game theory

Combinatorial game theory is a mathematics theory that only studies two-player games which have a position which the players take turns changing in defined ways or moves to achieve a defined winning condition....
 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.

Measures of game complexity

  • The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game.


Useful when this is too hard to calculate, an upper bound
Upper bound

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S....
 can often be computed by including illegal positions or positions that can never arise in the course of a game.

  • The game tree size is the total number of possible games that can be played: it's the number of leaf nodes in the game tree
    Game tree

    In combinatorial game theory, a game tree is a directed graph whose node s are positions in a game and whose edge s are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position....
     rooted at the game's initial position.


The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe
Tic-tac-toe

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a paper and pencil game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first....
 game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.

However, for games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is infinite.

The next two measures use the idea of a decision tree. A decision tree is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.)

  • The decision complexity of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position. Such a tree includes all possible decisions for the player to move second, but only one possibility for each decision for the player who starts the game.


  • The game-tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that establishes the value of the initial position. A full-width tree includes all nodes at each depth.


This is an estimate of the number of positions we would have to evaluate in a minimax
Minimax

Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the maximum possible loss function....
 search to determine the value of the initial position.

It's hard even to estimate the game-tree complexity, but for some games a reasonable lower bound can be given by raising the game's average branching factor
Branching factor

In computing, tree data structures, and game theory, the branching factor is the number of child node at each node . If this value is not uniform, an average branching factor can be calculated....
 to the power of the number of plies in an average game.

  • The computational complexity
    Computational Complexity

    Computational Complexity may refer to:*Computational complexity theory*Computational Complexity ...
     of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation
    Big O notation

    In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions....
     or as membership in a complexity class
    Complexity class

    In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:...
    . This concept doesn't apply to particular games, but rather to games that have been generalized
    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....
     so they can be made arbitrarily large, typically by playing them on an n-by-n board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)


Example: tic-tac-toe

For tic-tac-toe
Tic-tac-toe

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a paper and pencil game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first....
, a simple upper bound for the size of the state space is 39 = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is generalized
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....
. A natural generalization is to m,n,k-games: played on an m by n board with winner being the first player to get k in a row. It is immediately clear that this game can be solved in DSPACE
DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine....
(mn) by searching the entire game tree. This places it in the important complexity class PSPACE
PSPACE

PSPACE is all the problems which can be solved by programs which only need a polynomial amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e....
. With some more work it can be shown to be PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
.

Complexities of some well-known games

Due to the large size of game complexities, this table gives the ceiling of their logarithm
Logarithm

In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number....
 to base 10. All of the following numbers should be considered with caution: seemingly-minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the numbers shown.

GameBoard size (cells)State-space complexity (as log
Logarithm

In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number....
 to base 10)		Game-tree complexity (as log
Logarithm

In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number....
 to base 10)		Average game length (plies
Ply (game theory)

In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
)		Complexity class
Complexity class

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:...
 of suitable 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 2n pieces on each side....
Tic-tac-toe
Tic-tac-toe

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, hugs and kisses, and many other names, is a paper and pencil game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first....
9359PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Pentomino
Pentomino

A pentomino is a polyomino composed of five congruence squares, connected orthogonality.There are twelve different pentominoes, often named after the letters of the Latin alphabet that they vaguely resemble....
es		64121810 ?, but in PSPACE
PSPACE

PSPACE is all the problems which can be solved by programs which only need a polynomial amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e....
Connect Four
Connect Four

Connect Four is a two-player game in which the players take turns in dropping alternating colored discs into a seven-column, six-row vertically-suspended grid....
42142136?, but in PSPACE
PSPACE

PSPACE is all the problems which can be solved by programs which only need a polynomial amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e....
English draughts (8x8)
English draughts

English draughts, known simply as draughts in the United Kingdom and some other countries, and also called American checkers, straight checkers, or simply checkers, is a form of the draughts board game played on an 8?8 board with 12 pieces on each side that may only initially move and capture diagonally forwards....
3220 or 183170EXPTIME-complete
Awari
Oware

Oware is an abstract strategy game and is the variant of mancala most widely considered suitable for serious adult competition. Oware is the national game of Ghana, and the particular name "?ware" is that given by the Akan speaking people there....
12123260Generalization is unclear
Qubic
Qubic

Qubic is the brand name of a four-in-a-row game played in a 4×4×4 matrix sold by Parker Brothers in the late 1960s. The original box, and the 1972 reissue, described the game as "Parker Brothers 3D Tic Tac Toe Game." Players take turn placing pieces to get four in a row horizontally or diagonally on a single board -- or vertically...
64303420PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Fanorona
Fanorona

Fanorona is a board game indigenous to Madagascar and derived from Alquerque....
4521 46 22?, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
Nine Men's Morris
Nine Men's Morris

Nine Men's Morris is an Abstract strategy game Board games for two players that emerged from the Roman Empire. The game is also known as Nine Man Morris, Mill, Mills, Merels, Merelles, and Merrills in English....
241050??, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
International draughts (10x10)
International draughts

International draughts is a board game, one of the variants of draughts. It is played on a 10?10 board with alternatingly dark and light squares, of which only the 50 dark ones are used....
5030?5490EXPTIME-complete
Chinese checkers
Chinese checkers

Chinese Checkers is a board game that can be played by two to six people. It is a variant of Halma; the objective of the game is to place one's pieces in the corner opposite their starting position of a pitted hexagram by single moves or jumps over other pieces....
 (2 sets)		12123???, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
Chinese checkers
Chinese checkers

Chinese Checkers is a board game that can be played by two to six people. It is a variant of Halma; the objective of the game is to place one's pieces in the corner opposite their starting position of a pitted hexagram by single moves or jumps over other pieces....
 (6 sets)		12135???, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
Lines of Action
Lines of Action

Lines of Action is a two-player abstract strategy board game invented by Claude Soucie....
64245663?, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
Reversi
Reversi

Reversi is an abstract strategy game board game which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides....
64285858PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Hex (11x11)
Hex (board game)

Hex is a board game played on a hex map, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go ....
12156?40PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Gomoku
Gomoku

Five in a Row is an abstract strategy board game and is also called Gomoku, Gobang. It is traditionally played with Go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a Paper and pencil game....
 (15x15, freestyle)		225105?7030PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Chess
Chess

Chess is a recreational and competitive game played between two Player . Sometimes called Western chess or international chess to distinguish it from History of chess and other chess variants, the current form of the game emerged in Southern Europe during the second half of the 15th century after evolving from similar, much older...
645012380EXPTIME-complete
Connect6
Connect6

Connect6 introduced by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a two-player game similar to Gomoku....
36117270 or 14015 or 30PSPACE-complete
PSPACE

PSPACE is all the problems which can be solved by programs which only need a polynomial amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e....
Backgammon
Backgammon

Backgammon is a board game for two players in which the playing pieces are moved according to the roll of dice. A player wins by removing all of his pieces from the board....
282014450-60Generalization is unclear
Xiangqi
Xiangqi

Xiangqi is a two-player China board game in the same family as Chess, chaturanga, shogi and janggi. The present-day form of Xiangqi originated in China and is therefore commonly called Chinese chess in English language....
904815080??, believed to be EXPTIME-complete
Quoridor
Quoridor

Quoridor is a 2?4-player abstract strategy game designed by Mirko Marchesi and published by Gigamic Games. Quoridor received the Mensa International Mind Game award in 1997 and the Game of the year USA, France, Canada and Belgium....
8142162??, but in PSPACE
PSPACE

PSPACE is all the problems which can be solved by programs which only need a polynomial amount of memory to run. In the term "PSPACE", the P stands for polynomial, and SPACE refers to the amount of space, i.e....
Amazons (10x10)
Game of the Amazons

The Game of the Amazons is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina. It is a member of the territorial game family, a distant relative of Go and chess....
10040 (upper bound)??PSPACE-complete
PSPACE-complete

In computational complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be polynomial-time many-one reduction ....
Shogi
Shogi

, in English, also known as Japanese chess, is a two-player board game in the same family as Western world chess, chaturanga, Chinese chess, and janggi, and is the most popular of a family of chess variants native to Japan....
8171226110?EXPTIME-complete
Arimaa
Arimaa

Arimaa is a two-player abstract strategy board game that can be played using the same equipment as chess. Arimaa has so far proven to be more difficult for artificial intelligences to play than chess....
644329670?, but in EXPTIME
EXPTIME

In computational complexity theory, the complexity class EXPTIME is the Set of all decision problems solvable by a deterministic Turing machine in big O notation time, where p is a polynomial function of n....
Go (19x19)
Go (board game)

Go is a strategic board game for two players. It is known as w?iq? in Chinese , or in Japanese, and baduk in Korean language ....
361171360150EXPTIME-complete


See also

  • Go complexity
  • Solved board games
  • list of NP-complete games and puzzles
    List of NP-complete problems

    Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive . Most of the problems in this list are taken from Garey and Johnson's seminal book Computers and Intractability: A Guide to the Theory of NP-Completeness, and are here presented in the same order and...
  • list of PSPACE-complete games and puzzles
    List of PSPACE-complete problems

    Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive....


External links

  • David Eppstein
    David Eppstein

    David Arthur Eppstein is an English-born American professor of computer science at University of California, Irvine and a mathematician. His is known for his work in computational geometry, Graph theory and recreational mathematics....
    's