Page 200 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

Figure 10.22 depicts game tree for (1,2,2) NIM.

Figure 10.22: Game Tree for (1, 2, 2) NIM

In figure 10.22, the number in the root shows that at first, there are five toothpicks which consist of three
sets, 1, 2, and 2. Assume A is the player who makes the first move. A may take one or two toothpicks.
After A’s move, it is B’s turn and the numbers in the nodes represent the toothpicks left. Then B moves
one or two toothpicks and the status is shown in the next nodes and so on until there is one toothpick
left.
We can use this game tree to analyze the best possible move. For each player, the best move is to make
the opponent lose in order to win. So, one must make the move to get the MAX score and force their
opponent to get the MIN score. A loss is presented by "0" and a win is presented by "1". The MAX nodes
denote the position of the current player and the MIN nodes denote the position of the opponent. Since
the goal of this game is that the player who removes the last toothpick loses, the scores are assigned to
"0" if the leaves are at MAX nodes and the scores are assigned to "1" if the leaves are MIN. Then, the
scores are totaled from the bottom nodes and assigned to the internal nodes. At MAX nodes, choose the
MAXIMUM score of the children and at MIN nodes, choose the MINIMUM score of the children. In this
manner, we may compute the scores of the non-leaf nodes from the bottom up. In the example shown in
figure 10.22, the root node is "1" and thus, corresponds to a win for the first player. The first player must
choose a child position that corresponds to a "1".

The depth of a game tree is the length of a longest instance of the game. Similarly, it is easy to construct
game trees for other finite games such as chess, Tic-tac-toe, Kalah, and so on. Chess is not a finite game
because it is possible to repeat board configurations in the game. Chess can be considered as a finite
game when this possibility is not allowed. In games with large game trees, the decision as to which
move to make next can be made only by looking at the game tree for the next few levels. A game tree is
useful in determining the next move a player should make.

LOVELY PROFESSIONAL UNIVERSITY 193