Game Trees

Game Tree structure:
Game trees are a data structure where all the possible moves of a game are stored. This can be done in 2 distinct whay's:

The first is to create the entire game tree at the start af the game For large games this can be very time and memory consuming.The second way is more efficient and thus widly used.
The second way is to create the tree while playing and only create it a couple of levels down. A good implementation of a game tree, would be one where a parameter would define the deepness of the game tree, on which the computer bases (see min-max method) his next move. A deeper level will result in a better move for the computer. But it is proven that this isn't always true.

The game tree at start:
The first level of the tree is the empty board.
The second level contains every possible move by the first player.
The third level contains every possible counter move for all the moves possible at the second level. This goes on until every possible position is set. And a winner or loser is know.

Use:
Implementing a game tree is a straightforward solution for 2 player games where the computer is playing.

Applications:
TicTacToe: For games like chess or go the game tree can be ENORMOUS.
This is why our example is the simple game tictactoe instead of for example. checkers

A.I.: The Artificial Inteligence of a player, is often indirectly equal to the depth of the gametree.
But Game trees are just one step behind decision trees which are used in AI research. Here instead of winning a game it needs to decide which way is better to complete the given task. Ultematly the computer guesses (if the tree is not completly calculated) the best possible move using the partial tree.