A game-tree is a mathematical term that refers to a directed graph illustrating the total number of possible "positions" in a particular game, diagramming the way the game moves from position to position as it is played. Games with a larger graph have higher game-tree complexity, and are considered "harder" in game theory, chess and Go being classic examples of very complex games with huge game trees.
Most games, or at least turn-based games, have a limited number of "states", or possible positions. For instance, in tic-tac-toe players take turns placing their mark (the X or O) on a board with nine positions. After both players have placed their mark the game is said to have progressed by one move.
A game tree for tic-tac-toe starts with nine branches, because the first player can pick any one of the nine open spaces. For each of their nine branches the second player can place their mark in the eight remaining spaces, so the tree has eight branches leading from each of the original nine. Thus the game tree for the first full move of tic-tac-toe has 9 x 8 = 72 leaves, 9 branches for the first ply (half-move) and eight for the next. Following this to its conclusion builds a tree with 9! = 362,880 leaves, some of which are won for the first player, some for the second, and the rest tied.
However things are never this simple. Tic-tac-toe can be won in as little as 5 ply, if the first player can place all their marks in a row right off. For this reason the game tree contains many branches that are "cut off" shorter than the full depth of nine. In fact if one considers additional trimmings for "dumb moves" and the "real" starting positions (corners or middle, not any of the nine locations) the total number of branches is actually just over 34,000.
And if one takes into account that the board for Noughts and Crosses is equal no matter which way a person looks at it, it diminishes the number of moves by a three quarters.
In order to refer to the difference in possible moves vs. those that actually can occur, game-tree complexity is defined (typically) as the product of the game's average branching factor and the number of plies (half-moves) in an average game.
A tremendous amount of research has been put into figuring out what the "best possible move" is given the tree and the current state, an outcome referred to as the minimax algorithm. The alpha-beta pruning algorithm is most widely used for this, but a number of variations and new systems are starting to generate interest, one of the newer ones being SSS.
The three hundred thousand possible states of tic-tac-toe is too many to be remembered by most players, but this is a trivial exercise for a modern computer. For this reason the game is not considered "hard" by game theoretic standards. Most "interesting" games, like chess, have game trees with a number of states much greater than the number of particles in the universe. Such games are considered "hard" mathematically, as there is no way, even in theory, to remember every possible chess position.
The general solution to these sorts of games is to build partial trees on the fly, given the current state. For instance, a chess-playing program might build a tree of a million possible future outcomes reachable from the current board layout, and then apply alpha-beta to this partial tree. Of course this might result in the system picking a move where all of the possible outcomes on the next level of the tree below those million leaves are all losses. This is known as the horizon effect, where significant changes exist just beyond the depth the tree was searched, which is why most chess programs try to build the biggest trees possible given memory and time constraints.
Even then the "rules based" approach used by humans, which in many cases is largely free of any state ("don't bring your queen out early"), will often outperform programs for this reason. The speed of modern computers has almost eliminated this effect however, even non-elite chess programs can win against any but the best human players. Today it is more difficult to make a program play "intelligently bad" to give the human a chance, than to program a strong game.
Number of legal positions and game-tree complexity for some games
