Consider the game of tic-tac-toe. 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 n O's and no X's. The utility function assigns +1 to any board states with X3 = 1 and -1 to any board state with O3 = 1. All other terminal states have utility 0. For nonterminal states, we use a linear evaluation function defined as
Eval(b) = 3X2(b) + X1(b) - 3O2(b) - O1(b).
(a) 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. That is, symmetric boards should be considered to be the same state. Two boards are symmetric if one can be transformed into the other by rotating one board clockwise or counterclockwise, or flipping the board vertically, horizontally, or along a diagonal. For example, all of the board states shown below are equivalent under symmetry:
| X | O | | | X | | | O | | | | O ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- | | | | | | | | X | | X X | | ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- ---+---+--- O | | | X | | | O O | | | | | |
(b) Mark on your tree the evaluations of all the board states at depth 2.
(c) Using the Minimax algorithm, mark on your tree the backed-up values for the boards at depths 1 and 0, and use those values to choose the best starting move.
(d) 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.
For the 8-puzzle, we defined the h3 heuristic to be
h3(n) = h2(n) + 2 × number of directly adjacent tile swaps
where h2 is the Manhattan distance heuristic. Suppose we remove the restriction that the swaps must be between adjacent tiles. That is, we count all pairs of tiles that are reversed with respect to the goal state, whether or not they are adjacent. Is this new heuristic admissible for the 8-puzzle? If so, give a proof. If not, give a specific counterexample that shows that it violates admissibility.
Write out your answers on paper and turn them in to me during class on Tuesday.