# Question: This problem exercises the basic concepts of game playing using

This problem exercises the basic concepts of game playing, using tic-tac-toe (noughts and crosses) as an example. We define Xn as the number of rows, columns, or diagonals with exactly n X’s and no O’s Similarly, On is the number of rows, columns, or diagonals with just n O’s. The utility function assigns + 1 to any position with X3 = 1 and – 1 to any position with O3 = 1. All other terminal positions have utility 0. For non-terminal positions, we use a linear evolution function defined as Eval(s) = 3X2(s) + X1 (s) – (3O2(s) + O1(s)).

a. Approximately how many possible games of tic-tac-toe arc there?

b. Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account.

c. Mark on your tree the evaluations of all the positions at depth 2.

d. Using the mini max algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.

e. Circle the nodes at depth 2 that would not be evaluated if alpha—beta pruning were applied, assuming the nodes are generated in the optimal order for alpha—beta pruning.

a. Approximately how many possible games of tic-tac-toe arc there?

b. Show the whole game tree starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account.

c. Mark on your tree the evaluations of all the positions at depth 2.

d. Using the mini max algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move.

e. Circle the nodes at depth 2 that would not be evaluated if alpha—beta pruning were applied, assuming the nodes are generated in the optimal order for alpha—beta pruning.

## Answer to relevant Questions

Prove the following assertion: for every game tree, the utility obtained by MAX using mini max decisions against a suboptimal MIN will be never be lower than the utility obtained playing against an optimal MIN. Can you come ...Describe or implement state descriptions, move generators, terminal tests, utility functions, and evaluation functions for one or more of the following games: Monopoly, Scrabble, bridge (assuming a given contract), and poker ...Describe the wumpus world according to the properties of task environments listed.(Adapted from Bar wise and Etchemendy (1993)) Given the following, can you prove that the unicorn is mythical? How about magical? Horned? If the unicorn is mythical, then it is immortal, hut if it is not mythical, then it is ...Consider a knowledge base containing just two sentences: P(α) and P(h). Does this knowledge base entail V x P(x)? Explain your answer in terms of models.Post your question