Solution for Hw-2 Problem 4 - Alpha-Beta Pruning

A:

The correct move is A -> C (with an estimated value of 3)

B:

For this part I accepted two answers as correct:

if you assumed that we only prune x if the value that we already
have (y) is *strictly* better than x then the pruned leaves are {S,W,AA}.

if you assumed a non-strict better than relation then the pruned
leaves are {S,V,W,AA,DD,EE} where pruning cuts off K and O..

the difference between the two approaches is that in the second one,
you prune x even if x is as good as the value we have now..for example,
the left branch of B evaluates to 2 and when we go down the right branch
we know that E should return something lower than 2 for B to choose E..then
we visit J and T and see that it has value 2.. some people stopped here
saying that we prune U also.. this is not correct since if you make U,V and W
-infinity, then E *has* to pick -inf since J and K are min nodes, so B picks
-inf which changes everything.. so we have to look at U and see that it is 7 so
J picks 2, now we can see that E will have a value of at least 2 since it is a 
max node.. so it is not necessary to visit K.. so we prune it.. in the first
approach since 2 = 2 (that is E is as good as D so far) we dont prune it and continue
exploring K..FOR FUTURE PROBLEMS IN MIDTERM/FINAL PLEASE USE THE SECOND APPROACH
since that is usually how people implement alpha-beta pruning..

i dont suggest you use this kind of reasoning when coming up with a solution
since it can get you confused.. look at the book to see the algorithm with
alpha-beta values and execute that step-by-step.. it will get you to the
solution faster..

The winning path is the same.

c:

The answer doesnt change for this part no matter which approach you choose..

D is pruned.. so P,Q,R,S are not evaluated.. BB is also pruned..

The winning path is the same..

D:

As you can see the order of evalueation changes the behavior of
pruning. It is not that obvious in this example since the number of
leaves pruned are almost the same if you took the second approach for
part b.. yet if you think about it a big branch is pruned off with right-to-left
evaluation and dont forget that this game tree is probably not a complete 
one so when we prune B, we also prune all possible nodes that are below B (and who
knows may be the branching factor is huge if we try to expand P,Q,R,S)..

A domain independent heuristic is the following: given a node D first apply
the static evaluation function to all of its children and expand in decreasing
order if D is a max node and increasing order if D is a min node.. you can
see the benefit of this pretty easily: if D is a max node and the first node
that we evaluate is indeed the max of D's children, then the chances are that
we will prune most of D's other children (or at least their sub-branches)..

Many people gave a heuristic for evaluating the board status (which is essentially
the static evaluation function) but did not say how this would affect the
order of evaluation..

The savings for "perfect" evaluation order is O(b^(d/2)) since the branching factor is
sqrt(b).. a lot of people said that perfect evaluation would take us straight
to the goal which gives us exponential savings.. but this is not true, since 
perfect evaluation order is different from perfect static evalution function, if we
used a perfect static evalution function then you are right, we would just go to
the node that gives us the most benefits and not worry about other nodes at all..
but in perfect evaluation order, you still have to visit other branches to do pruning,
..see the book for more explanation..

E: 

There are basically two reasons for this:

1. It is not feasible to start from the goal for most games since there are
many goal states and the branching factor would make it computationally too expensive..

2. The information that we need is mostly about our current state!! because we need 
to know our next move!!

It was surprising that a lot of people omitted 2 which is more trivial than 1.. 
If you saw a -2 for part E, it was probably because you didnt say we needed to
reach to current state.. if you lost 1 point, then you said it but you didnt state
the reason..