Game complexity

In combinatorial game theory, there are several ways to measure the game complexity. In the following, the following metrics are described below:

• State-space complexity
• Game tree size
• Decision-making complexity
• Game tree complexity
• Computational effort

Metrics of the game complexity

• The state-space complexity of a game is the number of reachable positions from the starting position of the game from. If this is too difficult to calculate an upper bound can often be determined by improper positions or those that can not be achieved in the game you count.
• The game tree size is the total number of possible game histories. It corresponds to the number of leaf nodes of the game tree.
• The game tree is usually considerably larger than the state space, as the same positions occur here in different games by trains running in a different order (eg when Tic -Tac- Toe game, with two X and one O, the position in two different species can be achieved, depending on where the first X was placed ). An upper bound for the size of the game tree can sometimes by simplifying the game, which only increase the game tree size ( eg illegal moves allow ), are calculated. However, the game tree for games where the number of moves is not limited ( eg because of the size of the board, or if position repetitions are allowed), infinite.

The next two metrics are based on the idea of a decision tree. A decision tree is a subtree of the game tree in which each position with "Player A wins ", " Player B wins " or " another train " was highlighted. End positions are then marked directly. A position, with the player A is a " Player A wins" can achieve position is also indicated by " Player A wins" highlighted. Similarly, B is moved for players.

• The decision complexity of a game, the number of leaf nodes in the decision tree smallest, wherein the marking of the initial position maintaining (such as " player A wins "). Such a tree contains all the choices for the second player, but only one possibility for the player who starts the game.
• The game tree complexity of a game is the number of leaf nodes in the smallest decision tree in full width, which maintains the value of the starting position. ( A tree full width always contains all nodes of depth. ) This is the number of positions you have to search in a minimax method to determine the value of the starting position. It is difficult to evaluate the game tree complexity. But for some games may be a reasonable lower bound can be found by the branching factor exponentially with the number of half-moves an average game.
• The complexity-theoretic computational complexity of a game describes the asymptotic difficulty of a game when it is arbitrarily large. This is expressed in the O- notation or as belonging to a complexity class. This concept is not applicable everywhere, but there are games that have been generalized so that they can be arbitrarily large. Typically, n- board is played on an n ×. (From the point of view of complexity theory is a game whose board size is fixed, a finite state machine, which can be solved in O (1), such as standing by a table in which, for each position of the best train.

Example: Tic Tac Toe

For Tic Tac Toe a simple upper bound on the size of the state space is 39 = 19,683. ( There are 3 states for each box and box 9. ) This figure includes many illegal positions, such as Positions with five crosses and no zeros or positions in which both players have a series full. For a more accurate estimate can therefore reduce the number to 5,478. If you look at reflections and rotations to be identical, only 765 fundamentally different positions are available.

A simple upper bound for the game tree is 9! = 362,880 (9 possibilities for the first train, 8 for the second, 7 for the third, etc. ). If one excludes impermissible trains obtained a maximum of 255 168 possible games. By taking into account the reflections and rotations reduces the number at 26,830.

The complexity-theoretic computational complexity of Tic Tac Toe depends on how it has been generalized. A simple generalization is the m, n, k game. On an n × m - board, the player who can be the first k boxes to fill in a row wins. It is directly clear that it can be solved in DSPACE (mn) by searching the entire game tree. Thus it is in the complexity class PSPACE. It can be shown that it is PSPACE - Complete.

Complexities of some famous games

Because of the enormous size of some game complexities, the following table only their logarithm to the base 10. All figures should be treated with caution because seemingly small changes to the rules could lead to major changes in the numbers, which are in any case often only rough estimates.

( as log to the base 10 )

( as log to the base 10 )