Rudy Rucker's CS 156 Artificial Intelligence




Paintings & Links



CS 156 Green Sheet, Spring 2002


Prof. Rudy Rucker, MH 213, 924-5147,
Office Hours: 10:30 - 11:45, T and Th

Class meets 12:00 - 1:15 PM T and Th.
Midterm: Thursday, March 21.
Final Exam: Thursday, May 23, 9:45 - 12:00.

This course will study the history, theory, and the prospects of artificial intelligence. We will cover a number of topics, including search algorithms, alpha-beta pruning for game-playing, machine learning, neural nets, genetic algorithms, machine vision, and robotics.

Most of the programming projects can be done in C++ (first choice) or Java (second choice). Our neural nets assignment will require use of C++, but not in any deep way. We are not going to use Scheme or LISP. With respect to C and C++, the best bet is to use Microsoft Visual Studio; you may rent the installation disks for $30.00 for four days from the SJSU bookstore and legally install the software on your machine. Information about Java programming environments can be found off the home page for this course. If you have trouble with C++, or are rusty with it, you can find a quick review of C++ on this site.

The texts for the course are:
Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, 1995.
Hans Moravec, Robot¸ Oxford U. Press, 1999.

Russell and Norvig is too big a book to cover completely. We intend to concentrate on four areas.
Basics, Searching, and Games: Chapters 1, 2, 3, 4, 5,
Logic and Knowledge Bases: Chapters 6, 7, 8, 9,
Machine Learning with Neural Nets and Genetic Algorithms: Chapters 18, 19 20, and 21
Vision and Robotics: Chapters 24, 24, 26 and Moravec's book..

Grades will be based on homework (~60 pts), on the midterm (50 pts), and on the final (75 pts). Homework later than 7 days will not be accepted. WARNING: Skipping a homework assignment can lower your final grade by as much as a full grade point.

Assignments are due at the START OF CLASS on the due dates. Assignments will be graded down 20% for 1-7 days late. Assignments later than 7 days will not be accepted.

The prerequisite for this course is a C- grade or higher in CS 145A.

Cheating policy: Copying on an exam will result in a score of 0 on that exam for both parties.

Home page for Russell & Norvig, Artificial Intelligence

We may write some programs in Java in this course. Information about Using Java.

But mostly we’ll use C++.

We may also simulate some intelligent creatures in a videogame environment developed by Rucker.  Videogame Projects.

The Turing Test is the problem of writing a computer program (a chatbot) that people will mistake for a live person when they “converse” with it online.  There is a standing prize of $100,000 for the first one to succeed.  Every year the Loebner Contest looks for the best Turing Test program; the best among the entries gets a prize.  So far, though, nobody has won the big hundred K prize for actually fooling something like ten judges for a half hour’s worth of talk.  Some Turing Test Links.

A Turing Test

Loebner Contest Home

Report on the Loebner Contest (Turing Test) 2000

Here's an online Wumpus game!

Russell and Norvig use Wumpus as an example where a logic agent might be a useful kind of AI. Consider the Windows | Accessory | Games | Minesweeper game as well.

Hmwk 1 Blind Search

Download and complete the two projects linked below and make three executables:
queen8.exe, vacsearch.exe, vacsearchbreadth.exe.

Hand in a floppy with the three *.exe and your two altered *.cpp files. Due Thursday, Feb 14. Also hand in a printed solution to the Cannibal and Missionaries problem. You can either work the Cannibal and Missionaries problem solution out by hand or by writing a program to do it. Next to the written solution state the NUMBER OF STEPS that it takes.

You should be able to unzip these using WinZip. They will unzip into individual directories. You can open up the projects by double clicking on the *.dsw files in Windows Explorer. F7 should build the project, I've tested them and they do build using my version of Visual C++ 6.0 which has service patches up through patch 5.

If you have an older Visual C++ that doesn't have at least Service Patch 2, you will get a compler error relating to the use of the overloaded operator<<. In this case you should (a) get the service patch from or (b) replace the code's use of the << operator by, say, a member print(...) function that you write.

Edit your homework by using File | Open dialog to open queen8.cpp or vacsearch.cpp and editing it. Press F7 to build. The *.exe will be in the Debug or the Release subdirectory depending on which kind of build you are doing.

Run the programs from the command line interface by opening up a DOS window. The *.cpp files explain the usage.

Your exe will run faster if you build the Release version, this is selected by opeinng the Build | Set Active Configuration... and choosing the Release version and then rebuilding.

If you close Visual Studio and click the clean.bat file in Windows Explorer, it will remove the extra junk from the directory.

Hmwk 2 Search Projects. Due Thursday Feb 28.

You need to pick one of these projects and carry it out.  More details and specifications on the problems will be posted from time to time, so check this page every now and then. 

Do one of projects A, B, C, D.  Most of you will do A, B, or C.

My preferred programming language is C++, but if you prefer Java that’s OK.  I don’t want to deal with any projects done in Lisp or Scheme, as I’m so rusty at those languages.

It will be a useful learning experience for you to THINK about even those projects that you aren’t planning to do.  We’ll be discussing all of them.

Step one (in class on Feb 21): give me your first two choices of problem .  We’ll finalize problems in classs.

Step two: Give me a disk with a program and a page or two with (a) a description of the design, (b)  a guide to using the program and (c) a report on what results you found.

(A) Hundred Queens Project. 

We want to have some alternate search algorithms so we can handle larger boards such as 100 queens.  We should have command line parameters to select the size of the problem and (possibly) the search method used.

Treat the N-Queens problem with an IIA (Iterative Improvement Algorithm) as described in section 4.4.  As described in problem 4.12, try the hill-climbing with random restart, and for max credit, an annealing method.  Make a little chart of comparing how well these methods work (in terms of the number of candidate solutions examined) for various sizes of N. Here's an interesting link on annealing.

Note that you only have to fine ONE solution, not all of them (there are too MANY to list anyway).

It woudl be nice if the output was (ASCII?) graphical so you could see the symmetry of the solution...

(B) Eight Puzzle.  Here we want a textmode graphic output (picture of the problem using ASCII) and we want A* search.

Write a search algorithm to use A* search to solve the 8 puzzle.  Allow three kinds of input: (a) With no input the program starts in a random configuration,
(b) with one integer input, the start state is scrambled n steps from the answer.
(c) but you are also allowed to input a configuration in the a form like a b c d e f g h i, where these are the values like this
a b c
d e f
g h i

We will use the number 0 to stand for the blank tile.
Unlike the book, let's say goal state is
0 1 2
3 4 5
6 7 8

Use the Manhattan heuristic.

For max credit do the 15 puzzle as well, with goal:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

(C) Big Vac Search. Write a bigvacsearch.exe takes as input two kinds of input, with the third argument flaggin which kind.

Cols Rows 0 Dirt 1, Dirt2, dirt3, ....
same as before AND the format

Cols Rows 1 Percent_of_dirty_cells
So bigvacsearch 100 100 0.005 would be ten thousand cells with fifty of them dirty.

To simplify, don't track vac direction, and let operator simply be E, N, W, S, to move to one of the neighboring cells.

Use an A* search. Possible heuristics might be

h1(n) is the shortest Manhattan metric from n to a cell with an uncollected piece of dirt or, if there's no dirt left the shortest Manhattan metric to the home cell.

h2(n) is the sum of the Manhattan metrics to the cells that have uncollected dirt. I think you would include the Manhattan metric to the home cell in this sum as well.

(D) Polygon “Maze.”  This one needs Windows graphics, but uses a fairly simple search.

Solve problem 4.13 as a Windows program.  Perhaps use the Pop framework if you’ve had CS 160 with me, or maybe at least use the cPolygon2 class and cVector2 classes from there.  The virtue of the Pop framework is that it lets you use floating point values for the polygon vertices, which makes the algebra work better.

What I imagine here is a program that draws some standard polygons like in the book illo or perhaps has an ability to create a random scene with polygons.  It might be espeically nice if the polygons were long thin rectangles arranged to make a maze.

A start point S and an end point E are randomly selected (or optionally by user mouse click).  These points aren’t inside any polygon.  Your program does an A* search to find the shortest path that runs from S to E.  It is possible to prove that this path must be a series of line segments that runs from S to a polygon vertex (or to E, if possible) and then on to a succession of polygon vertices and eventually to E.  The one hard part of this (besides drawing the scene) is to write a BOOL Polygon::Blocks(Point p1, Point p2) that will return FALSE if and only if the line from p1 to p2 doesn’t cross any of the caller Polygon’s edges.

Program should probably allow user to randomize the polygon layout rather than working for only one.  But you can allow also to read polygons in from a file.

Hmwk 3 Search Tree. Due Tuesday April 9.

Here are some links to commercial Decision Tree software products. Look through the sites and see some of their example trees.

Take the Play Tennis cases I handed out in class and construct the most efficient Search Tree, doing the entropy calculations we describe in class, as in Section 18.4 or more informally as in Figure 18.6. Make a table or diagram showing your calculations, and draw a picture of the tree. (10 Points)

Hmwk 4 Neural Nets for Face Recognition. Due Thursday, April 28.

20 pts.

(Last updated Tue April 23, 2002, 12 noon ).

This example is taken from Tom Mitchell, Machine Learning, McGraw-Hill 1997.
We have taken Mitchell's Neural Networks for Face Recognition code, which is for a Unix environment, and have ported it to a Windows environment using Visual C++. The code itself was written for Mitchell by Jeff Shufelt of Carnegie Mellon University in Fall 1994. Rucker ported it to the Visual Studio/DOS envoronment, and then now-graduated SJSU student Chris Nojima worked on it, and now Rucker is working on it again.

To get the ported code and examples for Windows, download Rucker's file, make a directory called facenet on your hard drive and uncompress into your facenet directory. Then get the code files, and decompress into the facenet directory as well. The facenetsupport zip file won't change very often, but the facenetcode zip file is still being improved from time to time.

The Mitchell code trains a neural net to recognize features of faces that are stored in a very portable byte per pixel *.PGM format. So that you want to actually see what the faces look like, the SJSU facenet?.zip package includes the executable of a program called iview32.exe for viewing *.PGM files in Windows. This program is by Irfan Skiljan and is copyright to him. The complete Iview package can be obtained online from Irfan's website at the Technical University of Vienna. This is a very cool freeware program, and it's worthwhile eventually getting the whole thing. But for now you can get the viewer as part of the SJSU facenet?.zip download.

The first thing to do is for you to (a) get the facenetsupport and facenetcode files and (b) figure out how to use the code to build the default facetrain.exe Visual C++, by clicking on facenet.dsw and (c) how to run facetrain.exe from the DOS command line. The facetrain.exe application is currently set to try to learn to recognize the face of a student named Glickman. I've provided some batch files have examples of command lines which will work in our Windows environment. Note that you have to be in the directory ABOVE the training and faces directory, not down in the code directory. Also note that the facenet.dsw project is set to place executables into the directory above it where the batch files are.

When you run trainall.bat it creates an with binary info about the weights for a net to distinguish things about the faces. The default task is to recognize non-sunglasses. See below.

In order to make the neural nets do different things, you have to edit some of the files and rebuild facetrain.exe. Search in the code files for the phrase "CUSTOMIZE HERE" to find the three places you may need to change, there are comments there explaining what to do. Here is the most important spot, in imagenet.cpp

There is now a #define CHECKPOSE of some such in facetrain.h to make the net try and recognize the pose.

if (!strcmp(eyes, "open")) //strcmp returns 0 if two strings are equal.
net->setTargetUnit(0, TARGET_HIGH); //Want a high value to mean TRUE
net->setTargetUnit(0, TARGET_LOW); //Want a low value to mean FALSE
/* You change this test to tailor what your net learns. You can keep
a simple condition on the output unit number 0 if you are just looking for
a TRUE or FALSE answer.
Our default test looks for people not wearing sunglasses. If the net
always answers TRUE or always answers FALSE, it will get about a 50% success rate, as half the pictures are with and half without sunglasses.
Try trainng and testing on straight ahead poses with trainstraight.bat and teststraight.bat, then try on all poses with trainall.bat and testall.bat.
With our default 3 hidden units, for the sunglasses, you'll get a test success of
about 97% on the straight face, and on the harder problem with varying poses of all faces, you'll get about 75% success.
To train for other tasts, change the test. If you want to test to recognize Glickman for instance, you could use this for your first condition.
if (!strcmp(userid, "glickman"))
Careful, as a Glickman-seeking net can seem to do well if you look at the
percentage of success, but this can be an illusion. A badly trained net will
just say "NOT GLICKMAN" for every face, and it will USUALLY be right, as most
faces aren't Glickman! You can see this is what's happening if when the test
batch file lists all the incorrect answers and they are all pictures of Glickman
that you said no on!
If you want to just decide if someone is looking up, you could change the first line to this:
if (!strcmp(pose, "up"))
Again, be careful, as a badly trained net will in fact just say "NO" for every face, and it'll look like you have 75% success rate, and if you look at the mistaken
cases you'll in fact find they were all "UP" that you said no on. Also make sure to train the looking up net on ALL faces, not on just straight faces as none of those are looking up.
If you are doing a pick one of N answer, you will need to work with the N output units here.
Make sure you keep in synch the changes at the three possible methods
that you may customize:
(a) the success condition in load_target in imagenet.cpp
(b) the args to new BackPropNN(...) in backprop_face in facetrain.cpp
(c) the evaluate_perormance function in facetrain.cpp
Change only (a) to simply change the type of TRUE/FALSE test you consider,
but consider maybe using more hidden units, which means changing (b).
Change (b) if you want to change the number of hidden or output units.
Change (a), (b), and (c) if you want to change to a one-of-N decision.

Problem 1: Train a net to recognize sunglasses.(a) change the code and make a new version of facetrain.exe suitable for this task and name it shades.exe. Move the new exe into the right location, (b) run our trainshades.bat file to make a for recognizing shades, (c) test it with testshade.bat. Some students say the program works better if you give it two output units instead of just one and pick the higher valued one, so you may want to do that.

Problem 2: Make a yes/no pose recoginzer to recognize if the peson is looking up.

Problem 3: Make a mood recognizer: normal, happy, sad, angry.

Problem 4:. Make a 1-of-20 face recognizer; i.e. implement a neural net that accepts an image as input, and outputs the userid of the person. (a) Change the code and make a new recognize.exe and move it to the testing directory. You will need to implement a different output encoding so as to distinguish among 20 people. (Hint: use 20 hidden units). (b) Run our trainrecognize.bat file to make a file. You can probably edit the bat file to train for a longer number of iterations than the default. (c) Use our testrecognize.bat file to test the net. One student said he got 65% accuracy after something like 1200 training steps. Consider MItchless notion of preprocessign for pose.

Your homework will be to creat the shades.exe, and recognize.exe, and files, and pose.exe, and mood.exe see if they work and hand them in on a disk. I will evaulate them by using some bat files named grade*.bat files. Also hand in short report (two pages at least) summarizing your conclusions or any comments you have about additional tests you've done. Your grade will be based on (a) if your nets work, and, more important, (b) if your report is clear and (c) you tell me anything interesting. For higher grade include some pictures and analysis of the weights, using the two extra programs hidtopgm and outtopgm. To really do a super report, select one of the addional problems Mitchell mentions and do some work on it and tell me about it. Or make up one of your own.

LAST FIX. In the file hidtopgm.cpp, Code VErsion 9 has


It should be