Machine Learning (W4771)

Homework 4: Genetic Programming

Project: Othello

Due Date: Class time, Thursday March 30.

Reading: Chapter 9 ("Genetic Algorithms") of "Machine Learning" by Tom M. Mitchell. The math of Section 9.4.1 is optional. Also read the handout of three genetic programming chapters (all stapled into one; note that two of the three are only partial), not available on the web.

Writeups and results of 18 student projects on this assignment

Your assignment:

Follow the IMPORTANT ADDENDUM MATERIAL to familiarize yourself with the genetic programming (GP) implementation we are using for this project, and the application thereof to symbolic regression.

In class we are covering our implementation of the game Othello, and a specific approach to Othello using GP. Here are the GP and Othello Java code and READMEs.

Note: If you are an instructor and decide to use all or part of this assignment and/or these course materials, please email email: evs at cs dot columbia dot edu to let me know.

Our goals:

For the sake of coverage, we will distribute this project across the body of students in our class.

To avoid redundancy, we will be approving all projects. Select a project that you can do within two weeks and email to Your email description of the project should be 3 or 4 sentences at most -- we will ask if we need more details at that point. Note that you are allowed to work in teams. We may ask parties to communicate and come to an agreement on specific differences between experiments.

What is interesting to you about this problem and the use of machine learning to solve it? What aspect of the system needs further understanding and/or experimentation? What would result in better Othello players?

Below are a list of possible projects (also follow the link above to see what previous students have done for this). Note that your Java expertice is a pragmatic factor in your decision. You should select (or invent) only one project. One interesting thing to do is to vary something over a series of options, and record the performance of each.


You must hand in (electronically to an html write-up of your project, about 3-6 pages in length (including tables). (If you do not know html and do now want to learn, a text write-up will suffice.) There will not be in-class presentations of this project. Instead, we will compile an on-line compendium of the results. This compendium will be advertised to the machine learning community (including the GP mailing list). The compendium will optionally include applets that allow users to compete against evolved Othello players.

Your write-up should contain a written description of the experiments you conducted. In particular, the introduction should start with the motivation, and then give an overview of the solution. A seperate "approach" section gives the details of your modification/experiment. The results section gives the numerical results and some analysis. Finally, the conclusions section puts the capital P on "perspective".

email: evs at cs dot columbia dot edu