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.
- Show how you can derive the ratio (b+1)/(b-1).
- Does this formula hold for b = 1? Compute the ratio for this
- 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
- Mark on your tree the evaluations of all the positions at
- 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*.
- Convert the following sentences into clausal form.
(A V B) => C
Use resolution refutation to show that C is true.
D => B V Q
D & ~Q