Question

Draw the subtree of the game tree for tic-tac-toe beginning at each of these positions. Determine the value of each of these subtrees.

Short answer

(a)

(b)

(c)

(d) The value of the game is \({\bf{ + 1}}\).

Step-by-step solution

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.

Firstly, determine the value of subtrees of part (a).

(a)

Consider the tic-tac-toe game,

Complete the sport by drawing the sub trees so determine the worth of the tree also. Here, the moves of \({\bf{x}}\) are \({\bf{4}}\) and move \({\bf{0}}\) are \({\bf{3}}\), then the next move is for \({\bf{0}}\).

Hence, the value zero within the figure indicates the worth of the tree and it’s zero because the sport attracts both cases.

Now, determine the value of subtrees of part (b).

Consider the tic-tac-toe game,

Complete the sport by drawing the sub trees so determine the worth of the tree also. Here, the moves of \({\bf{x}}\) are \({\bf{4}}\) and moves \({\bf{0}}\) are \({\bf{3}}\). then the next move is for \({\bf{0}}\).

Therefore, the value\({\bf{ + 1}}\)in the figure indicate the value of the tree and it is\({\bf{ + 1}}\)because\({\bf{x}}\)wins the game.

Now, determine the value of subtrees of part (c).

(c)

Consider the tic-tac-toe game,

Complete the sport by drawing the sub trees so determine the worth of the tree also. Here, the moves of \({\bf{x}}\) are 3 and moves 0 are 3 . Then the next move is for x .

Hence, the value +1 in the figure indicate the value of the tree. This is because following the min max criteria x wins.

Now, determine the value of subtrees of part (d).

Consider the tic-tac-toe game

Complete the sport by drawing the sub trees so determine the worth of the tree also. The game needs no other move because three appeared diagonally on a line so wins the game.

Therefore, the value of the game is +1 .