The goal of this homework assignment is to give you some experience formulating problems for algorithm development, and to have you implement and test two uninformed search strategies.

For this assignment, record your responses to the following activities in the README.md file in the homework01 folder of your assignments GitLab repository and push your work by 11:59 PM Monday, September 10.

Activity 0: Branching

As discussed in class, each homework assignment must be completed in its own git branch; this will allow you to separate the work of each assignment and for you to use the merge request workflow.

First, follow these instructions to setup your git environment.

To create a homework01 branch in your local repository, follow the instructions below:

$ cd path/to/cse-40171-fa18-assignments   # Go to assignments repository

$ git checkout master                     # Make sure we are in master branch

$ git pull --rebase                       # Make sure we are up-to-date with GitLab

$ git checkout -b homework01              # Create homework01 branch and check it out

$ cd homework01                           # Go into homework01 folder

Once these commands have been successfully performed, you are now ready to add, commit, and push any work required for this assignment.

Activity 1: Problem Formulation for Tic-Tac-Toe (25 Points)

Following the problem formulation scheme described in Sec. 3.2 of Russell and Norvig, write a formulation for the game Tic-Tac-Toe. Your formulation should include the six criteria that capture the relevant state and action information for a problem. If you haven't played this game in a while, and need a refresher, click the image below to go to Google's implementation:

Activity 2: Problem Formulation for Hunt the Wumpus (25 Points)

Hunt the Wumpus is a classic computer game where the objective is to shoot a dangerous monster (the Wumpus) that is hiding in a grid of rooms. Several variations of this game exist, from early text-based implementations to more modern web-based apps. For this activity, we will use the version available from osric.com:



On each turn, a player can either move or shoot. The rules for this version of the game are the following:

  1. There are 3 hazards: (1) A bottomless pit (you will feel a breeze nearby); (2) A colony of bats that will pick you up and drop you in a random space--including potentially deadly spaces (you will hear flapping nearby); (3) A fearsome, hungry, and unbathed Wumpus (you will smell it nearby).
  2. The Wumpus is heavy; bats cannot lift him.
  3. The Wumpus is covered in suckers; he won't fall down the bottomless pit.
  4. Firing an arrow that misses the Wumpus may cause it to move.
  5. You have 5 Wumpus-piercing arrows.
  6. You may find an arrow dropped by a previous hunter.

Click the image above to access the web app, and play a few games to get a feel for the problem space. Following the problem formulation scheme described in Sec. 3.2 of Russell and Norvig, write a formulation for Hunt the Wumpus. Your formulation should include the six criteria that capture the relevant state and action information for a problem.

Activity 3: Implement and Test Depth-First Search (25 Points)

Write a python method for depth-first search that takes three parameters as input: a graph, a starting vertex, and a target vertex (i.e., the vertex you are searching for). The method should return a valid search path from the starting vertex to the target vertex. Hint: Fig. 3.16 in Russell and Norvig demonstrates the operation of the algorithm. Include an if __name__ == '__main__': block that calls your search method and is able to pass two command line arguments to it: the starting vertex and the target vertex. Name your program depth-first-search.py.

The following graph, which will be used as a test case, can be coded directly into the program:

If your program is working as expected, you should be able to call it, for example, in the following manner: python depth-first-search.py A F, and receive the following output for the search path: [['A', 'B', 'E', 'F']].

Activity 4: Implement and Test Breadth-First Search (25 Points)

Write a python method for breadth-first search that takes three parameters as input: a graph, a starting vertex, and a target vertex (i.e., the vertex you are searching for). The method should return a valid search path from the starting vertex to the target vertex. Hint: Fig. 3.11 in Russell and Norvig presents pseudocode for the algorithm. Include an if __name__ == '__main__': block that calls your search method and is able to pass two command line arguments to it: the starting vertex and the target vertex. Name your program breadth-first-search.py.

The graph above from Activity 3 can be coded directly into the program. If everything is working with your breadth-first search program, you should get the same output as you did with depth-first search: calling python breadth-first-search.py A F results in the following search path: [['A', 'B', 'E', 'F']].

Feedback

If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your README.md.

Submission

Remember to put your name in the README.md file. To submit your assignment, please commit your work to the homework01 folder of your homework01 branch in your assignment's GitLab repository:

$ cd path/to/cse-40171-fa18-assignments   # Go to assignments repository
$ git checkout master                     # Make sure we are in master branch
$ git pull --rebase                       # Make sure we are up-to-date with GitLab
$ git checkout -b homework01              # Create homework01 branch and check it out
$ cd homework01                           # Go to homework01 directory
...
$ $EDITOR README.md                       # Edit appropriate README.md
$ git add README.md                       # Mark changes for commit
$ git commit -m "homework01: complete"    # Record changes
...
$ git push -u origin homework01           # Push branch to GitLab

Remember to create a merge request and assign the TAs (agraese and AndroidKitKat).