EECS 391/491: PROBLEM SET #5
Reading:
The answers to the following two problems should be typed:
Problem 5.1 [10 points]
[Nilsson] Why does search in game-playing programs usually proceed forward from the
current position rather than backward from the goal? Typeset your answer.
Problem 5.2 [10 points]
Problem 6.10 of R&N. Choose just one.
Do not implement, just briefly describe.
Typeset your answer.
These three problems require hand calculation and are much faster if you do not typeset them:
Problem 5.3 [10 points]
[Rich and Knight] Print out the linked game tree (twice).
- Fill in the minimax values on one copy. Beneath the tree note, note what move Player 1 should
make at Node A and the minimum payoff the player is assured if they make that move.
- Perform alpha-beta search on the second copy. Then, below the tree, list the nodes that
would not have been expanded if alpha-beta pruning had been used
(assuming nodes are expanded in left to right order).
Problem 5.4 [20 points]
Problem 6.1 of R&N.
Problem 5.5 [20 points]
Problem 6.3 of R&N.
The following problem requires programming:
Problem 5.6 [30 points]
Consider the 8-queens Problem from R&N again. (Hopefully, this will drastically amortize
the time you've spent on it last week.)
Solve it using
- Min-conflicts, choosing the variable (column) to minimize over at random
- Min-conflicts, choosing the variable to minimize in cyclic order: 1, 2, ..., 8, 1, 2, ..., 8, ...
Note: this is really the same algorithm, with just a slight difference in the way the variable
to "de-conflict" is picked.
Again, you will be maximizing "fitness," defined
as the number of non-attacking pairs of queens
(p. 117 of R&N), which is 28 minus "the number of pairs of queens that are attacking
each other, either directly or indirecty" (p. 112 of R&N). Thus, when you find a
configuration/state with fitness = 28, you have found a solution.
- Implement one program encompassing both algorithms above (the difference between them is
very slight; use a #define, global variable, command-line option, or user input to
switch between them). In each case, the algorithm should
exit as soon as a solution is found, print the solution (as a string of digits
like those depicted in Figure 4.15 of R&N), and print the total number of fitness
evaluations required from the start of the algorithm.
- Test your program enough to convince yourself that it works and that
solutions are being found appropriately. (Do not report on this.)
- Gather statistics regarding the operation of the two different algorithms,
recording
their performance. Here, you are to run each algorithm 100 times (from different
random starting positions/populations) and report only the average
of the number of evaluations until a solution is found.
Freely use the code you wrote in Problem Set #4 or the C++ I supplied for it in
our class's Code Repository:
http://dora.case.edu/msb/AI/code
Hints: Pseudo-code appears in Figure 5.8 (p. 151) of R&N.
Note that Min-conflicts is similar to hill-climbing, except you only test 8 successors,
not 56, so you can look at my supplied code for trying 56 successors and remembering the
best.
Turn in your code and a table summarizing your results.
How did this compare with your results from Problem 4.6.
The following problems are for graduate students only
Problem 5G.1 [10 points]
Problem 6.2 of R&N.
Problem 5G.2 [5 points]
Problem 6.13 of R&N.
Problem 5G.3 [5 points]
Problem 6.14 of R&N. By the way, another continuous-state
"game" to think of is the Urban Challenge, with
the other vehicles treated as adversaries.
Created: 2008-02-13.
Modified: 2008-02-13.