Do the following exercises from the text:

  1. Exercise 3.6.d - Give a one-paragraph specification here.

  2. Download this Romania search module and consider the problem of searching from Fagaras to Dobreta.

    1. Work the search for the A* algorithm out on paper. Save your solution either as a low-resolution image or a text file. Be sure to specify the expansion order of the nodes.
    2. Reconfigure the command file to compute the results for this problem by calling the A* (only) search directly.

    Remember that using the search metaphor, even for a physical domain like the Romanian search domain, is somewhat of a stretch. The real Romania is more complex (and beautiful).

  3. Exercise 3.9 - Replace the well-known missionaries and cannibals problem with the lesser known Fox-Goose-Beans problem.

    Notes on each part of the problem:
    1. You don’t need to draw out the complete state space, just draw its opening moves and give the solution path.
    2. Choose an appropriate search algorithm and explain why you chose it.
    3. Do this part as specified.

    If you’re looking to simplify your life, you can do the problem as stated on the missionaries and cannibals problem for most, but not all, of the homework points.

Final project suggestion - Students tend, by default, to build game players for a particular game of their choice (e.g., Go). This can be historically interesting and includes useful technologies from adversarial search (see Chapter 5), but often starts with a pre-built game playing environment that the student struggles to understand and to control and the project ends up being of limited value. We intend to accept only a small number of projects of this sort. Consider, instead, applications of game theory (see Norvig’s “Game Theory” lecture.)

Checking in

Submit the files specified above in Moodle under homework 2. We will grade your work according to the following criteria: