Question

How many children does the root of the game tree for checkers have? How many grandchildren does it have?

Short answer

The number of possible moves for the first player is 7. So, the root of the game tree has 7 children & the roots of the game tree has 49 grandchildren.

Step-by-step solution

defining the values of all vertices in a game tree in a way that enables us to determine the outcome of this game when both players follow optimal strategies,

By a strategy mean a set of rules that tells a player how to select moves to win the game. An optimal strategy for the first player is a strategy that maximizes the payoff to this player and for the second player is a strategy that minimizes this payoff. We now recursively define the value of a vertex.

One needs to find how many children the root of the game tree for checkers has.

In a game of checkers, each player has twelve pieces of checkers placed on the dark squares of the three rows of 8 x 8 chessboard, nearer to that player’s side.

The row nearer to the player is called the king's row.

A checker moves one square diagonally to an adjacent dark square towards the opponent.

Thus, only the front row of checkers can move at the start.

The checkers in the first two rows move only diagonally forward; whereas, the king's row checkers can move in any diagonal direction.

From the board, observe that there are four checkers in the row at the start. For the first checker, there is only one possible move, and the remaining three have two possible moves.

Thus, the number of possible moves for the first player is 7. So, the root of the game tree has 7 children.

For the next move,

The second player is free to move the front row for each move of the first move.

We observe that each vertex of the first move has 7 free moves.

As there are 7 free moves for the first player, the number of possible moves for the second player is, \({\bf{7x7 = 49}}\).

Hence, the root of the game tree has 49 grandchildren.