AI Homework 1

Out: 8 Feb 2007
Due : 13 Feb 2007

It can be shown that asymptotically, iterative deepening depth first search expands (b+1)/(b-1) nodes more than depth first search, when given a uniform tree of depth d and branching factor b.

Consider a version of A* where we use as evaluation function
f(n) = (2 - w) g(n) + w h(n)
where w is between 0 and 2; and h is an admissible heuristic. Consider the case where w=2. What sort of search is this? Is it guaranteed to be optimal? Will it be optimal if h=h*? How does it compare to hill-climbing search with a goodness function h(n)?
Indicate whether the following statement is true or false, and give a brief but precise justification for your answer.
"The time and memory requirements of IDA* can be improved by using A* algorithm to do search in individual iterations."
This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. We define Xn as the number of rows, columns or diagnonals 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 evaluation function defined as
Eval(s) = 3X2(s)+X1(s)- (3O2(s)+O1(s)).

Show the whole game tree starting from an empty board down to depth 2 (.e. one X and one O on the board), taking symmetry into account.
Mark on your tree the evaluations of all the positions at depth 2.
Using the min-max algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those value to choose the best starting move.
Circle the nodes at depth 2 that would *not* be evaluated if alpha-beta puring were applied, assuming the nodes are generated in *the optimal order for alpha-beta pruning*.