EECS 391/491: PROBLEM SET #6

Reading:

Note: There is no need to typeset any of your answers.

Problem 6.1 [10 points]

Problem 7.2 of R&N. If you like, you can use the linked grids, kindly provided by former 391 student Joseph Zarycki.

Problem 6.2 [5 points]

Problem 7.3(b) of R&N. Do not reuse any example from class.

Problem 6.3 [10 points]

Problem 7.5 of R&N.

Problem 6.4 [10 points]

Problem 7.7 of R&N. But only do contraposition and De Morgan's two laws.

Problem 6.5 [15 points]

Problem 7.8, parts (a)-(f) only, of R&N.

Problem 6.6 [10 points]

Problem 7.11, parts (a), (b), and (f) only, of R&N.

Problem 6.7 [10 points]

Problem 7.13, parts (a) and (b) only, of R&N.

Problem 6.8 [10 points]

Problem 7.17 of R&N.
The following problem requires a little programming:

Problem 6.9 [20 points]

In Lecture #9 (see also pages 3 and 4 of the ehandout adversarialHO.pdf) we provided a program for Minimax search for Tic-Tac-Toe.
  1. Implement this program by typing it in or translating it to another language of your choice. Test it on the seven examples provided and convince yourself it works. Turn in drawings of the seven initial boards. The representation used is as follows: 1 means X, -1 means O, and zero means blank. Thus, each board is given by 9 integers, starting with the second index (1) in C++, and corresponding to the board positions in successive rows from top to bottom and from left to right: 
    1 | 2 | 3
---------
4 | 5 | 6
---------
7 | 8 | 9

    There is no need to turn in any code for this portion.

  2. Modify your program so that it keeps tracks of the number of nodes expanded (merely the sum of the number of calls to min_value() and max_value()). Report the answer (value) and the number of nodes expanded for each of the 7 examples given separately. Again, there is no need to turn in any code.

  3. Modify your program once more so that it performs Alpha-Beta Search (see Figure 6.7, page 170 of R&N). Re-run it on the seven example boards, again reporting the value and number of nodes expanded for each of the seven boards. Comment on your results. Turn in your code, highlighting that code that was added to the minimimax program provided to count/print nodes expanded and to perform the alpha-beta search.

The following problem is for graduate students only; it requires some programming:

Problem 6G.1 [20 points]

Implement WalkSAT (see Figure 7.17 on p. 223 of R&N). Try it out on the formula on page 224 of R&N and some others of your choosing. Run your program several times on each formula, keeping appropriate statistics. Comment on your results. Turn in your code.