Tree Search: Guest Lecture and Lab 9 by Simon Levy
Part I: Write Depth-First-Search
Create a lab9 directory. Copy the code from the last page of the lecture, save it in a file called search.py in your lab9 directory, and follow along with Prof. Levy to complete the DFS function. (You will fill in the XXX code in the third part, so you don’t have to do it now.) You can invoke the following methods on a problem object:
- initialState() returns the initial state of the problem
- goalTest(state) returns True if state is a goal state, False otherwise
- successorFn(state) returns a list of the successors of a state
- wasVisited(state) returns True if state has already been visited, False otherwise (you won’t need this for Eight-Queens)
Here are some very useful things you can do with lists.
Part II: Test DFS on the Eight-Queens Problem
Save this program as queentest.py in the same directory as search.py. Then type python queentest.py at the Linux prompt. When you have it working, show Prof. Sprenkle so she can give you credit for this part.
Part III: Test DFS on maze navigation
First, download quagents.py, quagent_client.py, and mazetest.py, into your lab9 directory. Then, at your Linux prompt, type
python mazetest.py 3
The Quake game window should pop up, followed a few seconds later by the appearance of an agent (bot / enemy soldier). Note that if you move the mouse cursor into the game window, the window traps the cursor. Holding down the shift key will allow you to move cursor back outside the window. The proper way to exit the game is to hit ESCAPE, use the arrow keys to get to QUIT, and then reply y (for yes) at the final screen. Or you can just close the window.
Does the agent get to the gold or not? If not, why? (Recall our discussion of the “rabbit-hole” problem with DFS from the lecture.) It’s time to fill in the XXX code to avoid repeated states. When everyone has reached this stage, follow along with Prof. Levy to make this work. The agent should eventually get to the gold in the maze and pick it up. When you have it working you can also try python mazetest.py 4 to run a larger maze.