CS 151: Programming Assignment 1

Introduction to Python and Search [60 points]
due Wednesday, January 26, 11:55pm

Part 1: Getting Started

• Python uses colons and indentation to indicate blocks.  Indentation is critical in Python.  The colon at the end of a line indicates the start of a block of code, all of which must be indented to the same degree.  For example, the "return False" line is outside the for-loop because it is indented at the level of the function body, not the for-loop body.
• Variables are not declared in Python.  The L is understood to be a list and the x an element in the list, but it's up to the user to enforce this.  Return values are also not specified.  If a function includes a return statement, that's what it returns.  If it does not, then it returns nothing.
• The for-loop in Python is a little different from what you might be used to.  It specifies that the variable i should take on each value in the list L.  The "range" function is very useful in getting for-loops in Python to behave like "normal" for-loops.  (See the documentation on for-loops).
  
• The line in quotes at the top of the function is a special comment called a "docstring".  It is displayed when the user asks for documentation about this function by typing help(listSearch) at the Python prompt.  (Try this below).  The parts of the line starting with the symbol # are regular comments.

>> import search ; reload(search) ; from search import *

Part 2: Programming in Python

1. Objects and Games [20 points]. Complete this problem in a file called pa1pr1.py
   In this problem you will develop an object for managing a game of Tic Tac Toe.  While we covered the basics of creating objects in Python in class, you will probably want to refer to Python's documentation on creating classes.  Create a class called TTTBoard that defines the following functions:
   
   • __init__(self): Initialize a 3x3 tic tac toe board (remember to avoid magic numbers in your code)
   • __repr__(self): Returns a string representation of the board
   • makeMove(self,player,pos): Places a move for player in the position pos on the board if possible.  Note that the board positions are numbered starting with 0 in the upper left and proceeding left to right, then down the board, as follows:

      0 | 1 | 2
     ---|---|---
      3 | 4 | 5
     ---|---|---
      6 | 7 | 8
     

      player is a character ("X" or "O") pos is an integer.  Returns True if the move was made and False if not (because the spot was full, or outside the boundaries of the board).
   • hasWon(self,player): Returns True if player has won the game, and False if not
   • gameOver(self): Returns True if someone has won or if the board is full, False otherwise
   • clear(self): Clears the board to reset the game
   You may represent the board however you like.  You may define other functions as well.  You may wish also to define a function that allows two players to play the game to make sure your above functions are working correctly.
   
   
2. Missionaries and Cannibals [40 points] (Based on AIMA Ex 3.9) Complete this problem is a file called pa1pr2.py.
   In this problem you will formulate and solve the famous "Missionaries and Cannibals" problem.  (You'll remembe a similar homework from CS60, but this time we won't use Prolog, so the search is explicit).  The problem goes like this:
   
   There are 3 missionaries and 3 cannibals on one side of a river.  They have 1 boat, that can hold 1 or 2 people.  The goal is to get everyone across the river without ever leaving more cannibals than missionaries alone on one side at a time (if there are 0 missionaries, that's OK).  
   
   This problem is famous in AI because it was used in the first paper that presented problem formulation from an analytical viewpoint (AIMA, 115).
   
   a. Formulate this problem precisely as a search problem. First write a class named MissionariesAndCannibals that defines the state space.  This class must include (among any other functions you wish to define):
   
   • Data members for everything necessary to represent the state (you need to decide how to do this).  Include a comment at the top of your file describing your state space.
   • __init__(self): creates an object representing the initial state
   • goalTest(self): returns True if the state represents the goal, and False otherwise
   • successors(self): returns a list of (action, cost, state) tuples representing all of the legal states that are reachable using valid actions from the current state (self).  action is a string representing the action taken (e.g. '2M and 0C from 1 to 2'), cost is the cost of taking this ONE action, and state is a state object representing the new state reached.
   • __repr__(self):  method that returns a human readable string representation of the state.
      
   b. Now write a class named SearchNode that keeps track of the information needed to search for the solution.  This class should be flexible, and should not be tied to a specific search algorithm.  It should include the following:
   
   • the following data members:
   • state: the node's state (a MissionariesAndCannibals object)
   • parent: the node's parent node (a SearchNode object)
   • action: a string representing the action that was taken to reach this node
   • pathCost: an int representing the total path cost to reach the node
   • depth: an int representing the depth of the node
   • __init__(self, state, parent=None, action=None, pathCost=0, depth=0): A function that initializes a new node.  Each of the parameters corresponds to one thing the node must keep track of (note you can give them default values like I have).
   • expand(self): A function that returns a list of nodes reachable from the current node.   
   • pathFromStart(self): A function that retuns a list containing all of the (action, state) pairs to reach the current node from the root node.
   
   c. Finally, outside of your two classes, write a function named SearchForSolution() that starts at the initial state for the Missionaries and Cannibals problem, and searches until it reaches the goal state.  Your function should return the SearchNode object that contains the first goal state that you reach in your search.  You may implement any search algorithm you like.  In a comment above your function, state which algorithm you chose and why.
      Hint: If you are using DFS, you'll need to keep track of states you've already seen to avoid going into an infinite loop.