Game complexity: Difference between revisions

Revision as of 16:18, 22 June 2004

Revision as of 12:18, 8 July 2004

Line 1:

In [[computergame sciencetheory]], '''board game complexity''' is a measure of the complexity of a [[game]]. ItThis comesarticle incovers atthree leastmeasures fourof formscomplexity: [[state-space complexity]], [[game-tree complexity]], [[numberand of move-sequences]], [[computational complexity]].

==Measures of game complexity==

State-space complexity refers to the number of different game-positions that can exist in a game.

'''State-space complexity''' is the number of different possible positions that may arise in the game.

When this is too hard to calculate, an upper bound can often be computed by including illegal positions or positions that can never arise in the course of a game.

Game-tree complexity is normally defined as the product of the games average branching factor and the number of plies (given as half-moves in Chess and as moves in "Go") in an average game. The game-tree complexity is normally higher than the state space complexity due to the fact that the same position can occur in multiple games.

'''Game-tree complexity''' is the size of the [[game tree]]: that is, the total number of possible games that can be played. The game tree is typically vastly larger than the state space because the same positions can occur in many games (for example, the initial position appears in all games).

A "move-sequence" is the succession of moves from the "game start" to the "game end". A "move" (Go term) is the action of a player performed during his turn and thereby transforming one "game state" to its successor, its next "game state". The "number of move-sequences" is the total number of move-sequences that might occur legally according to a game's rules. It is expressed as a function in a parameter. A typical parameter is the number of objects that form the board of a game. E.g., N = 64 squares in Chess or N = 361 intersections in Go. Since determining a "number of move-sequences" M(N) is a difficult mathematical problem for many interesting games, one uses bounds to limit the unknown, precise functions: a "lower bound" L(N) or an "upper bound" U(N). The following holds: L(N) < M(N) < U(N). E.g., for Go (with simple rules) trivial bounds are: L(N) = N! and U(N) = N^(3^N). So for the precise "computational complexity" M(N) of Go we can say: N! < M(N) < N^(3^N).

It is usually impossible to work out the size of the game tree exactly, but in some games a reasonable estimate can be made by raising the game's average [[branching factor]] to the power of the number of [[plies]] in an average game. 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.

For [[computational complexity]], see the link. In short, there are two types of "computational complexity". One describes the size of required storage space, the other describes the size of required computation time.

'''[[Computational complexity]]''' describes the [[asymptotic]] difficulty of a game as it grows arbitrarily large, expressed in [[big O notation]] or as membership in a [[complexity class]]. This concept doesn't apply to particular games, but rather to games that have been [[generalized game|generalized]] 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.)

What follows is trivia. The really crucial information about a game is its "computational complexity". - Due to the large size of complexities often their logarithms (base 10) are given instead of their actual value. All of the following numbers should be considered with extremely great care. Tiny changes on 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 shown numbers.

==Example: [[tic-tac-toe]]==

<table border="1" cellpadding="2">

A simple upper bound for the size of the state space is 3⁹ = 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 gives 5,478. When symmetrical positions are considered the same, there are only 765 essentially different positions.

<caption>Logs of Complexities</caption>

<tr><th>Game</th><th>State-space</th><th>Game Tree</th></tr>

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 symmetrical positions are considered the same, there are only 26,830 possible games.

<tr><th>[[Nine Men's Morris]]</th><td>10</td><td>50</td></tr>

<tr><th>[[Awari]]</th><td>12</td><td>32</td></tr>

The computational complexity of tic-tac-toe depends on how it is [[generalized game|generalized]]. A natural generalization is to [[mnk-games|''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]](''mn'') by searching the entire game tree. This places it in the important complexity class [[PSPACE]]. With some more work it can be shown to be [[PSPACE-complete]].

<tr><th>[[Pentominoes]]</th><td>12</td><td>18</td></tr>

<tr><th>[[Connect Four]]</th><td>14</td><td>21</td></tr>

==Complexities of well-known games==

<tr><th>[[Backgammon]]</th><td>20</td><td>144</td></tr>

Due to the large size of game complexities this table gives the ceiling of their logarithms (to base 10). All of the following numbers should be considered with great care. Tiny changes on 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.

<tr><th>[[Checkers]]</th><td>21</td><td>31</td></tr>

<tr><th>[[Lines of Action]]</th><td>24</td><td>56</td></tr>

{|

<tr><th>[[Reversi|Othello]]</th><td>28</td><td>58</td></tr>

!align="left"|Game

<tr><th>[[Chess]]</th><td>46</td><td>123</td></tr>

!align="left"|log(State space)

<tr><th>[[Xiangqi]]</th><td>??</td><td>150</td></tr>

!align="left"|log(Game tree)

<tr><th>[[Shogi]]</th><td>71</td><td>226</td></tr>

!align="left"|Complexity class of suitable [[generalized game]]

<tr><th>[[Go (board game)|Go]]</th><td>172</td><td>360</td></tr>

|-

</table>

|[[Tic-tac-toe]]

|align="right"|3

|align="right"|5

|[[PSPACE-complete]]

|-

|[[Nine Men's Morris]]

|align="right"|10

|align="right"|50

|?

|-

|[[Awari]]

|align="right"|12

|align="right"|32

|?

|-

|[[Pentominoes]]

|align="right"|12

|align="right"|18

|?

|-

|[[Connect Four]]

|align="right"|14

|align="right"|21

|?

|-

|[[Backgammon]]

|align="right"|20

|align="right"|144

|?

|-

|[[Checkers]]

|align="right"|21

|align="right"|31

|[[EXPTIME-complete]]

|-

|[[Lines of Action]]

|align="right"|24

|align="right"|56

|?

|-

|[[Reversi|Othello]]

|align="right"|28

|align="right"|58

|[[PSPACE-complete]]

|-

|[[Chess]]

|align="right"|46

|align="right"|123

|[[EXPTIME-complete]]

|-

|[[Xiangqi]]

|align="right"|???

|align="right"|150

|probably [[EXPTIME-complete]]

|-

|[[Shogi]]

|align="right"|71

|align="right"|226

|[[EXPTIME-complete]]

|-

|[[Go (board game)|Go]]

|align="right"|172

|align="right"|360

|[[EXPTIME-complete]]

|}

See also: [[Solved board games]]

==External links==

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

==References==

* Stefan Reisch, Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.

[[Category:Board games]]