StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q34E

Expert-verifiedFound in: Page 771

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?**

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.

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).

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

94% of StudySmarter users get better grades.

Sign up for free