If the same board configuration arises from two different sequences of moves, we create two separate nodes, so this really is a tree. Internal nodes at odd levels correspond to positions in which the second player is to move.
Leaves correspond to positions at which the game has ended.
One player or the other has won, or perhaps the game is drawn. Game Tree Evaluation Suppose we have an internal node for which all children are leaves, so that the game is certain to end in one more move. Then we can assume that the player to move is going to pick the best move. If there is a leaf giving a won position for him, he will move to it and win. If not, but some leaf gives a drawn position for him, he will move to it and draw.