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.)