• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q34E

Expert-verified
Found in: Page 771

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Draw a game tree for him if the starting position consists of three piles with one, two, and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that result from the same move. Find the value of each vertex of the game tree. Who wins the game if both players follow an optimal strategy?

See the step by step solution

Step 1: Define 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.

Step2: One shall draw the tree for him game where the game starts with $$\left\{ {{\bf{1,2,3}}} \right\}$$ position and find the value of each vertex and finally who will win the game.

To draw the game tree for the problem with start position $$\left\{ {{\bf{1,2,3}}} \right\}$$ the first player has six options viz,

$$\begin{array}{l}\left\{ {{\bf{122}}} \right\}{\bf{, }}\left\{ {{\bf{112}}} \right\}{\bf{, }}\left\{ {{\bf{23}}} \right\}\\\left\{ {{\bf{113}}} \right\}{\bf{, }}\left\{ {{\bf{13}}} \right\}{\bf{ }}\left\{ {{\bf{12}}} \right\}\end{array}$$

Box indicates even plays and circles indicate odd plays.

For leaf nodes with only one stone in odd plays (comes in circles), but the value as $${\bf{ + 1}}$$ (in figure simply $${\bf{1}}$$) and for leaf nodes with one stone in even plays (comes in the box), put the worth as $${\bf{ - 1}}$$.

For an internal node an even level the value is the maximum of the values of its children. For an internal node in the odd level, the value is the minimum of values of its children.

Root nude (the initial position of the game) Is considered an even level in the figure.

The repeated branching of nodes is eliminated for avoiding the clumsy look of the tree (example: - is expanded only one time, that is the first time).

Step 3: The diagram for the tree is as follows:

Hence, the root has got $${\bf{ - 1}}$$ value, one can conclude that player $${\bf{2}}$$ wins the game.