Project Othello Machine Learning Home Page

"Put money in thy purse." - Shakespeare's Othello

"A minute to learn, a lifetime to master." - Milton Bradley

This page describes the results of Project Othello, one of four homework projects for the machine learning course at Columbia University (Professor: Eric Siegel, TA: Eleazar Eskin).

A SIGCSE (cs education) paper on this assignment is available. Note that there is also an intro to computer science version of this assignment.

For Project Othello, students applied the machine learning method genetic programming (GP) to the game Othello. Each student or student team selected a unique experimental project investigating variations on the learning method, hypothesis representation, or both. To evaluate results, students had to deal with many machine learning issues such as overlearning, temporal credit assignment, local optima, hypothesis representation bias, learning speed and noisy fitness measurements (cf. GP Brainstorming Archive for a more comprehensive list of learning issues). The projects were mutually complementary. The bottom of this web page contains a hierarchical index of the 18 experimental projects with links to writeups of their approaches and results. Some have applets that allow you to play Othello against learned players.

The homework assignment and all needed code are available for interested researchers or machine learning instructors. This includes ideas for GP-Othello projects from which students could select. It also includes Java implementations of GP (jpgpp) and of Othello, which are hooked up; to perform many non-trivial experiments, this code can be modified easily by students who are not fluent with Java.

GP is used to induce a board evaluation function to select each move made during the game. In this approach, there was no search beyond the next immediate move in the game, except for one student project (Truta, below). The students started from this rudimentary approach and evaluated variations.

The idea to use Othello as a machine learning homework project was Astro Teller's, and he provided some of the code used in the project, as well as another automatically-learned Othello player, Edgar. Edgar trained with a different learning paradigm, so students also performed cross-paradigm comparisons.

The goal of each student project was not necessarily to beat Edgar. Rather the goals included:

One interesting result demonstrated over a few reports, below, is that while some strategies learned to beat Edgar, it proved more difficult for learning to develop a strategy that beats a "noisy" Edgar, that is, Edgar with some randomness added.

Introduction (from Suk's writeup, below)

In this project, we are given an Othello game written in Java with a genetic programming implementation already in place. This original implementation consists of 13 primitives, + - * / 10 black black_corners black_near_corners black_edges white white_corners white_near_corners white_edges. The first four primitives are standard arithmetic operators while the rest of the primitives are terminals, all but one corresponding to positions on the board. All the standard genetic programming population control constructs such as crossover, mutation, and ADFs are included in the given Java package, gpjpp. In addition to this genetic programming setup, a computer player, Edgar, is provided. Though not a genetically programmed player, Edgar boasts a superior playing ability, easily dispatching most Othello players in short time. It is the purpose of this project to modify and extend the current genetic programming setup in hopes of discovering new approachs in implementation and representation that will facilitate the creation and evolution of GP players that can play well against both Edgar and the general othello playing population.

In general, fitness over five games only is not precise, very noisy.

Student Othello Projects:

Other, non-Othello GP projects