Computer Science Essay

GAME TREE
A game tree (also called the extensive form) is a graphical representation of a sequential game. It provides information about the players, payoffs, strategies, and the order of moves. The game tree consists of nodes (or vertices), which are points at which players can take actions, connected by edges, which represent the actions that may be taken at that node. An initial (or root) node represents the first decision to be made. Every set of edges from the first node through the tree eventually arrives at a terminal node, representing an end to the game. Each terminal node is labeled with the payoffs earned by each player if the game ends at that node.
Game Trees
by Yosen Lin (yosenl@ocf.berkeley.edu)

Consider the problem of implementing a computer program to play a game. To simplify things a bit, we will only consider games with the following two properties:
  * Two player - we do not deal with coalitions, etc.
  * Zero sum - one player's win is the other's loss; there are no cooperative victories
Examples of these kinds of games include many classic board games, such as tic tac toe, chess, checkers, and go. For these types of games, we can model the game using what is called a game tree:

Above is a section of a game tree for tic tac toe. Each node represents a board position, and the children of each node are the legal moves from that position. To score each position, we will give each position which is favorable for player 1 a positive number (the more positive, the more favorable). Similarly, we will give each position which is favorable for player 2 a negative number (the more negative, the more favorable). In our tic tac toe example, player 1 is 'X', player 2 is 'O', and the only three scores we will have are +1 for a win by 'X', -1 for a win by 'O', and 0 for a draw. Note here that the blue scores are the only ones that can be computed by looking at the current position. To calculate the scores for the other positions, we must look...