Overview

One of the earliest investigations of machine learning was Arthur Samuel's work with Checkers, developing a program that learned a board evaluation function through the experience of playing many games. Starting from Samuel's approach, students will develop Checkers programs that learn to play by competing with other students' programs. Competitions will take place over the internet using a simple server that communicates moves between clients, checks for the validity of moves, keeps track of (and limits) the time spent by each player, and reports the winners and losers.

In addition to the reinforcement learning aspects, the project deals with the problems of search, efficient representation of knowledge, and reasoning about time as a resource. Using the same server guarantees that each checkers program learns and can compete within the same environment. At the end of the semester, the project teams compete in a tournament, which adds yet another level of excitement and provides a straightforward, if relative, comparison of the resulting programs.
The aim of this project is to investigate approaches to learning in the context of a two-player game. This will be done by developing a checkers client that can learn from its experience, train it to develop an effective board-evaluation function, and then competing with other teams' clients in an end-of-semester tournament.

The learning objectives of the project are:
  • Learning about limited lookahead search in a two-player game.
  • Learning about machine learning from previous work, literature, and experimentation.
  • Better understanding of fundamental AI concepts such as Search, Learning, and Knowledge Representation.
  • Gaining more experience on a team software project with open-ended goals.
Students should have a basic knowledge of software development and testing. Knowledge of algorithms and data structures, while not completely necessary, is helpful.

The project involves writing a client that can interact with a server using a protocol based on telnet. Sample clients (that illustrate the process of connecting to the server and initiating a game) are provided in Java and Lisp in RmCheckersClient.java and rmClient.lsp respectively.

This is a fairly large-scale project. Six weeks for teams of 3-4 would be a reasonable time frame to do a good job, although a non-learning player could be developed rather quickly.
For an introduction to adversarial search and machine learning, students can read the corresponding chapters in any good AI book. For example, one might assign chapters 6, 17, and 21 of: The most directly applicable source for this project is: The Samuel paper provides a lot of useful information and describes his experiments on this task. It may be worthwhile to look at some other descriptions of what Samuel did to get a better picture on where it fits in with subsequent work.

The rules for Checkers are available at a number of web sites. The server expects you to follow the rules at English Draughts Association site, http://home.clara.net/davey/ with the following exceptions: none of the rules having to do with the physical board will apply, as each player will need to have his or her own board representation and only interact via transmitted moves; a player that makes an illegal move loses immediately without warning; and we will play using a clock if you go over your allotted time you lose the game.

The description of the protocol for interacting with the server is available at protocol.pdf.
The detailed project description is available in the PDF file project.pdf. The description of the protocol for interacting with the server is available in the PDF file protocol.pdf. You will need the free Adobe Acrobat Reader to view these files.
The server code is available in CheckersServer.zip. All of the server code is licensed under the GNU General Public License.

This project is customizable to accommodate different approaches to teaching and different implementations. Additional exercises are also included for students seeking more extended challenges.
A sample syllabus used at the University of Connecticut when this project was assigned is available at:
Syllabus for AI Course at the University of Connecticut

Additional readings are included in the Background section above.