Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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

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.

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

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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

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.

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

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths