Assignment 3: State Space Search in Style, Plus Inference with Images
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2007
Due Tuesday, January 30, Python code submitted through Catalyst E-Submit at 11:59 PM.
 

Part 1 (Programming)

Do either the Eight-Puzzle program or the Tic-Tac-Toe program described below:
 
The "Eight Puzzle" consists of a board with a 3 x 3 array of spaces, together with eight tiles containing the numbers 1 through 8 on them. Initially, they are in a random order on the board. The player can slide any tile into the blank space, provided it is adjacent to the blank space. The objective is to get the tiles in numerical order on the board: from 1 to 8, left-to-right, top-to-bottom.

Write a program EightPuzzle.py similar to the MissAndCann.py that adapts the TStar state-space search software for the Eight Puzzle.
 
(Or) Adapt the T-Star software for the Tic-Tac-Toe games, creating a Python file TicTacToe.py. Your program does not have to play the game automatically, just respond to commands to grow the tree or apply operators.
Optional: Create a new menu option called "Play O" that causes the program to automatically respond to each of X's moves with an O move.
 
The T-Star software is available at the T-Star website.

A list of steps for adapting the T-Star software to your own purposes is this guide page.

Part 2 (Written answers)

  • Suppose you could have a "seeing" computer system in a mobile robot or a desktop facility. What abilities would you want it to have?
  • Suppose that a 128 by 128 pixel image contains an illustration of a dark house behind a white picket fence. What is the maximum number of pickets that could be distinguished given this resolution? Why?
  • Suppose a binary image has 4 rows and 4 colums of pixels. What is the maximum number of 4-connected components there could be in the image? What is the maximum number of 8-connected components in the image?
  • At the end of the PDF file "Edge and Line Detection", do exercise 3 comparing the Hough transform with least squares line fitting.