Assignment 2: Problem Formulation
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2018
Due Wednesday, January 17 at 23:59 PM.
 
Introduction

This assignment follows up on Assignment 1 by taking the same number-guessing game and putting it into framework of the classical theory of problem solving. When you have completed this assignment, you will be aware of the differences between a problem formulation for the classical theory and a simple game that does not take the theory into account. This will prepare the way to study algorithms for state-space search in Assignment 3.

Procedure

1. Begin this assignment by reading the 1st chapter of "Applying AI in Problem Solving" (linked from the Readings page).

2. Next, download the starter code for this assignment. Un-tar it using a standard file archiving tool such as tar, WinZip, Windows Compressed Folders, etc.
3. Examine each of the two problem formulation files provided. One is the Missionaries and Cannibals problem. The other is the Towers of Hanoi problem. Each is in its own folder. Two additional folders are provided, and you will be writing two new problem formulations -- one in each.

In the given formulation files, pay particular attention to how the State class is defined and how the operators are established. We will be talking about this code in class.

4. An interactive solving client is provided. This is implemented in the file Int_Solv_Client.py. Try running the client with Towers of Hanoi by using the following command in a Linux, Darwin, or Cygwin command shell. To do this, cd into the TowersOfHanoi folder, and then issue the command: 
python3 ../Int_Solv_Client.py TowersOfHanoi 3
5. As a warmup, create your own problem formulation file for the "Farmer, Fox, Chicken, and Grain" problem covered in class on Jan. 5. Using the interactive solving client, demonstrate the use of your formulation to create a solving-session log. You can simply capture your screen to show the log.
6. For your main formulation, create your own problem formulation file for a special version of the guess-my-number game, related to the game you implemented for Assignment 1. Here is a description of the new version of the game. Instead of randomly choosing a number, read the number from the command line, and store this in a variable in the COMMON_DATA part of your code. The user, who will be using the interactive solving client, will not be trying to guess the number directly. Instead, the user will be applying operators that correspond to particular (k,m) questions of the original game. Each applicable operator takes the game to a new state, and generally, the new state will be closer to a goal state. Each state will contain a list of numbers that might still be "the answer" meaning they have not been ruled out yet by answers to questions. The goal state is the state containing a singleton set whose sole element is the special number.
In the original game, the secret number was allowed to be in the range 1 to 1000. In the new problem, we will parameterize this range and you can set it to be small when you are debugging your program and then somewhat larger later. For example, you could start with MAX_NUMBER = 10, and later set MAX_NUMBER = 100, when your program is working well.

To see how a sample session might go for this new kind of problem, examine this demo session.

Keep in Mind

Here are some ideas to keep in mind for this assignment. The format we are using will not only permit the "manual solving" that you do with the Interactive Solving Client. It will also permit automatic solving that we cover later on in the course. Thus it is important that you follow the problem structure correctly. Certain methods are required in the State class, including __init__, __eq__, __hash__, __str__, and copy. The operators must have the correct structure, as well. The nice thing about the Interactive Solving Client is that it provides a pretty good means to test whether your formulation will be OK.

Even if you are familiar with Python, there may be some constructs in the formulation files that you are not familiar with. We will discuss some of these in class, including list comprehensions and lambda expressions.

What to Turn In

Turn in two four files: (a) <YourUWNetID>_Farmer_Fox_etc.py and (b) <YourUWNetID>_Find_the_Number.py. and two text files described later.

Each of the Python files should start with a multiline comment in the following format with your own information rather than the sample information given here: 

'''jnsmith321_Farmer_Fox_etc.py
by John Nathan Smith

Assignment 2, in CSE 415, Winter 2018.

This file contains my problem formulation for the problem of
the Farmer, Fox, Chicken, and Grain.
'''
In addition to the two .py files, turn in a pair of .txt files: YourUWNetID_Ffcg_demo.txt containing a transcript of a session with your Farmer-Fox-Chicken-Grain problem formulation, and YourUWNetID_FtN_demo.txt containing a transcript of a session with your Find-the-Number formulation. Each session should show one game from initial state to goal state.

The turn-in method will be Google Forms, and the URL of the submission page is here.

Updates and Corrections
 
Instructions for turning in the two demo session files were added Jan. 15 at 2:36 PM. The link to the survey was added at 12:08 AM, Jan. 16.
 
If needed, additional updates and corrections will be posted here, and/or in GoPost.
Feedback Survey

After submitting your solution, please answer this survey