# MiniMax Game Trees

By Eric Suh

The **Minimax Game Tree** is used for programming computers
to play games in which there are two players taking turns to play
moves. In the most basic sense, the minimax tree is just a tree
of all possible moves. For instance, take a look at the following
minimax tree of **all the possible first two moves** of Tic-Tac-Toe
(the tree has been simplified by removing symmetrical positions).

(Click
this thumbnail to get the full-sized picture)

Notice that unlike other trees like binary trees, 2-3 trees, and
heap trees, a node in the minimax game tree can have any number
of children, depending on the game situation.

The tree above has three levels, but in programming, the levels
of a minimax tree are commonly referred to as **plies**. At each
ply, the opportunity to play (the "turn") switches to
the other player. The two different players are usually referred
to as Max and Min (this convention will be explained shortly).

With a full minimax tree, the computer could look ahead for each
move to determine the best possible move. Of course, as you can
see in the example diagram, the tree can get very big with only
a few moves, and to look even just five moves ahead can **quickly
overwhelm a simple computer**. Thus, for large games like Chess
and Go, computer programs are forced to estimate who is winning
or losing by sampling just a small portion of the entire tree. Also,
programmers have come up with **algorithms** such as Alpha-Beta
pruning, Negascout, and MTD(f) to try to limit the number of nodes
the computer must examine.

The minimax game tree, of course, cannot be used very well for
games in which the computer cannot see the possible moves. In poker,
for instance, the computer will have a very hard time judging what
the opponent will do because the computer can't see the opponent's
hand. So, minimax game trees can be used best for games in which
both players can see the entire game situation. These kinds of games,
such as checkers, Othello, chess, and go, are called **games of
perfect information**.

The reason this data structure is named the minimax game tree is
because of the logic behind the structure. Let us assign points
to the outcome of a game of Tic-Tac-Toe. If X wins, the game situation
is given the point value of 1. If O wins, the game has a point value
of -1. Now, X will be trying to **maximize** the point value,
while O will be trying to **minimize** the point value. So,
one of the first researchers on the minimax tree decided to name
player X as Max and player O as Min. Thus, the entire data structure
came to be called the **minimax game tree**.

**This minimax logic can also be extended to games like chess**.
In these more complicated games, however, the programs can only
look at the part of the minimax tree; often, the programs can't
even see the end of the game because it is so far down the tree.
So, the computer only look at a certain number of nodes and then
stops. Then the computer tries to **estimate who is winning and
losing** in each node, and these estimates result in a numerical
point value for that game position. If the computer is playing as
Max, the computer will try to maximize the point value of the position,
with a win (checkmate) being equal to the largest possible value
(positive 1 million, let's say). If the computer is playing as Min,
it will obviously try to minimize the point value, with a win being
equal to the smallest possible value (negative 1 million, for instance).

Part 2