EECS 391/491: PROBLEM SET #5 FAQ
Problem 5.3
b. See the following new
Alpha-Beta Examples eHandout
for more information. In it, I keep track of alpha-beta
by hand for the top example (we did the >=, <= reasoning
in class). For the bottom figure, I do the <=, >= reasoning
in place on the diagram
and also provide a very detailed alpha-beta algorithm simulation
on page 2.
Problem 5.4
a. The s in Eval(s) refers to the current state
(or configuration). Note that you only have to approximate
the number of games.
b. Please take symmetry into account, as noted. Thus, instead of
four initial boards with an X in each corner, you only have to deal with
one in the upper left corner, e.g., because of the rotational symmetry.
Problem 5.5
For the proof of part d.,
consider arguments based on the game of size n=4 (which you
analyzed), the game of size n=3, and for larger n, the relationship
between the game of size n and the game of size n-2.
Problem 5.6
I placed my code for Random-Restart Hill-Climbing in the Code
Repository:
http://dora.case.edu/msb/AI/code/
The file is called
rrhc.cc
NEW!
A Java version of the code now also appears in the same directory:
rrhc.java
Created: 2008-02-13.
Modified: 2008-02-18.