 |
Business | Industries | Finance | Tax |
| 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 |
|
|||||
| First Prev [ 1 2 ] Next Last |
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 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).
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.
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 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.)
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 gives 5,478. When rotations and reflections of positions are considered the same, 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. 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(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.
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.
| Game | log(State space) | log(Game tree) | Complexity class of suitable generalized game |
|---|---|---|---|
| Tic-tac-toe | 3 | 5 | PSPACE-complete |
| Nine Men's MorrisNine men's morris also known as Mills Merrills is a two-player strategy game with a long history in Europe. Each player has nine pieces which move between the twenty-four intersections of three interlocking squares. The object of the game is to remove all | 10 | 50 | ? |
| Awari | 12 | 32 | ? |
| PentominoesA pentomino is a flat shape constructed of five squares that each touch one or more of their neighbours along any or all of the four sides. There are 12 unique pentominoes (under rotations and reflections); and one of each of these can be fitted (often wi | 12 | 18 | ? |
| Connect FourConnect Four (also known as Plot Four is a two-player board game in which the objective is to be the first to get four of one's own discs in a line. The game was published by Milton Bradley in 1974; a non-proprietary version is known as "The Captain's Mis | 14 | 21 | ? |
| BackgammonBackgammon is a board game for two players. Each player has fifteen pieces checkers which move between twenty-four triangles points according to the roll of two dice. The objective of the game is to be first to bear off i. move all fifteen checkers off th | 20 | 144 | ? |
| Checkers | 21 | 31 | EXPTIME-complete |
| Lines of Action | 24 | 56 | ? |
| Othello | 28 | 58 | PSPACE-complete |
| Chess | 46 | 123 | EXPTIME-complete |
| Xiangqi | 75 | 150 | probably EXPTIME-complete |
| Shogi | 71 | 226 | EXPTIME-complete |
| Go | 172 | 360 | EXPTIME-complete |
See also: Solved board games
| Politics | Business | Finance |
 |
 |
 |
|