Problem 1 (4 points):

Part A: Read Chapter 3 of the text. This chapter discusses two types of search problems where the agent has incomplete knowledge of states or actions: sensorless and contingency. Give an example of both that is not mentioned in the text. The examples can be a toy problems, like a game, or a real world problem.

Example problems needed to be search problems, i.e. problems with initial, intermediate, and goal states where at each step of the process there was some information that was not available to the agent. For example playing Poker is a contingency problem, because there are definite steps from the initial state to the goal states. Also the agent is not allowed to know what the other players have in their hand (partial information), but there are strategies that can be used to narrow the possibilities (sensing). The question in part B is also a contingency problem because sensing is not global and the result of a given action (suck) is not 100% deterministic.

Sensorless problems also involve partial information, but in this case the agent has no means of getting the missing information (sensing) so they must create a plan which works regardless of the actual value of the missing information. A good example is a car wash that takes multiple passes over the car to ensure that all surfaces are clean. It does not actually have sensors that check for dirt, but that does not matter because, regardless of the state of the car when it enters, it will be clean when it exits.

Part B: Assume that the vacuum agent described in the text must operate under the conditions described in page 86 (first full paragraph) of the text. Specifically:

• Murphy's Law (see Exercise 2.12 on page 58 for a definition)
• Two-room world
• Can sense dirt locally but not globally
• Can tell which room its in

Draw a belief state diagram similar to Figure 3.21 for the agent. Assume that the agent begins knowing nothing except that it is in the right-hand room. Hint: Draw the diagram as if sensing for dirt was an action, like sucking, which changes the belief state.

Here is my solution. Your solution did not necessarily need to be as complete, provided that it reflected an understanding of the conditions outlined in the description above.

Problem 2 (6 points):

A solution to the problem requires the following:

• Creating a structure to keep track of the game state.
• Creating a successor function.
• Creating a procedure to check if a state is a terminal state.
• Implementing an algorithm to find the best move, Alpha-Beta recommended.
• Creating a procedure for determining the utility of each terminal state.
• Creating a procedure to print moves and prompt the user for their moves.

These are the elements I expected to find in your code. For full points your code had to lose no earlier than 12 moves when played against my (not optimal) implementation.

To see for your self how your program did you can download the following: HexagonGame and Netbeans specific jar. You will need to store both in the same directory to run the first jar, which contains the program.

You will need the latest Java Virtual Machine installed (download from here). Once you have that then you can run the program by typing the following at a command line:
<java install directory>/bin/java -jar HexagonGame.jar (Linux) or
<java install directory>\bin\java -jar HexagonGame.jar (Windows).